MultiMap.java

  1. /**
  2.  *
  3.  * Copyright © 2015-2021 Florian Schmaus
  4.  *
  5.  * Licensed under the Apache License, Version 2.0 (the "License");
  6.  * you may not use this file except in compliance with the License.
  7.  * You may obtain a copy of the License at
  8.  *
  9.  *     http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.jivesoftware.smack.util;

  18. import java.util.ArrayList;
  19. import java.util.Collections;
  20. import java.util.LinkedHashMap;
  21. import java.util.LinkedHashSet;
  22. import java.util.List;
  23. import java.util.Map;
  24. import java.util.Set;

  25. /**
  26.  * A lightweight implementation of a MultiMap, that is a Map that is able to hold multiple values for every key.
  27.  * <p>
  28.  * This MultiMap uses a {@link LinkedHashMap} together with a {@link ArrayList} in order to keep the order of its entries.
  29.  * </p>
  30.  *
  31.  * @param <K> the type of the keys the map uses.
  32.  * @param <V> the type of the values the map uses.
  33.  */
  34. public class MultiMap<K, V> {

  35.     /**
  36.      * The constant value {@value}.
  37.      */
  38.     public static final int DEFAULT_MAP_SIZE = 6;

  39.     private static final int ENTRY_LIST_SIZE = 3;

  40.     private final Map<K, List<V>> map;

  41.     /**
  42.      * Constructs a new MultiMap with a initial capacity of {@link #DEFAULT_MAP_SIZE}.
  43.      */
  44.     public MultiMap() {
  45.         this(DEFAULT_MAP_SIZE);
  46.     }

  47.     /**
  48.      * Constructs a new MultiMap.
  49.      *
  50.      * @param size the initial capacity.
  51.      */
  52.     public MultiMap(int size) {
  53.         this(new LinkedHashMap<>(size));
  54.     }

  55.     private MultiMap(Map<K, List<V>> map) {
  56.         this.map = map;
  57.     }

  58.     public int size() {
  59.         int size = 0;
  60.         for (List<V> list : map.values()) {
  61.             size += list.size();
  62.         }
  63.         return size;
  64.     }

  65.     public boolean isEmpty() {
  66.         return map.isEmpty();
  67.     }

  68.     public boolean containsKey(K key) {
  69.         return map.containsKey(key);
  70.     }

  71.     public boolean containsValue(V value) {
  72.         for (List<V> list : map.values()) {
  73.             if (list.contains(value)) {
  74.                 return true;
  75.             }
  76.         }
  77.         return false;
  78.     }

  79.     /**
  80.      * Get the first value for the given key, or <code>null</code> if there are no entries.
  81.      *
  82.      * @param key TODO javadoc me please
  83.      * @return the first value or null.
  84.      */
  85.     public V getFirst(K key) {
  86.         List<V> res = getAll(key);
  87.         if (res.isEmpty()) {
  88.             return null;
  89.         } else {
  90.             return res.iterator().next();
  91.         }
  92.     }

  93.     /**
  94.      * Get all values for the given key. Returns the empty set if there are none.
  95.      * <p>
  96.      * Changes to the returned set will update the underlying MultiMap if the return set is not empty.
  97.      * </p>
  98.      *
  99.      * @param key TODO javadoc me please
  100.      * @return all values for the given key.
  101.      */
  102.     public List<V> getAll(K key) {
  103.         List<V> res = map.get(key);
  104.         if (res == null) {
  105.             res = Collections.emptyList();
  106.         }
  107.         return res;
  108.     }

  109.     public boolean put(K key, V value) {
  110.         return putInternal(key, list -> list.add(value));
  111.     }

  112.     public boolean putFirst(K key, V value) {
  113.         return putInternal(key, list -> list.add(0, value));
  114.     }

  115.     private boolean putInternal(K key, Consumer<List<V>> valueListConsumer) {
  116.         boolean keyExisted;
  117.         List<V> list = map.get(key);
  118.         if (list == null) {
  119.             list = new ArrayList<>(ENTRY_LIST_SIZE);
  120.             map.put(key, list);
  121.             keyExisted = false;
  122.         } else {
  123.             keyExisted = true;
  124.         }

  125.         valueListConsumer.accept(list);

  126.         return keyExisted;
  127.     }

  128.     /**
  129.      * Removes all mappings for the given key and returns the first value if there where mappings or <code>null</code> if not.
  130.      *
  131.      * @param key TODO javadoc me please
  132.      * @return the first value of the given key or null.
  133.      */
  134.     public V remove(K key) {
  135.         List<V> res = map.remove(key);
  136.         if (res == null) {
  137.             return null;
  138.         }
  139.         assert !res.isEmpty();
  140.         return res.iterator().next();
  141.     }

  142.     /**
  143.      * Remove the mapping of the given key to the value.
  144.      * <p>
  145.      * Returns <code>true</code> if the mapping was removed and <code>false</code> if the mapping did not exist.
  146.      * </p>
  147.      *
  148.      * @param key TODO javadoc me please
  149.      * @param value TODO javadoc me please
  150.      * @return true if the mapping was removed, false otherwise.
  151.      */
  152.     public boolean removeOne(K key, V value) {
  153.         List<V> list = map.get(key);
  154.         if (list == null) {
  155.             return false;
  156.         }
  157.         boolean res = list.remove(value);
  158.         if (list.isEmpty()) {
  159.             // Remove the key also if the value set is now empty
  160.             map.remove(key);
  161.         }
  162.         return res;
  163.     }

  164.     /**
  165.      * Remove the given number of values for a given key. May return less values then requested.
  166.      *
  167.      * @param key the key to remove from.
  168.      * @param num the number of values to remove.
  169.      * @return a list of the removed values.
  170.      * @since 4.4.0
  171.      */
  172.     public List<V> remove(K key, int num) {
  173.         List<V> values = map.get(key);
  174.         if (values == null) {
  175.             return Collections.emptyList();
  176.         }

  177.         final int resultSize = values.size() > num ? num : values.size();
  178.         final List<V> result = new ArrayList<>(resultSize);
  179.         for (int i = 0; i < resultSize; i++) {
  180.             result.add(values.get(0));
  181.         }

  182.         if (values.isEmpty()) {
  183.             map.remove(key);
  184.         }

  185.         return result;
  186.     }

  187.     public void putAll(Map<? extends K, ? extends V> map) {
  188.         for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
  189.             put(entry.getKey(), entry.getValue());
  190.         }
  191.     }

  192.     public void clear() {
  193.         map.clear();
  194.     }

  195.     public Set<K> keySet() {
  196.         return map.keySet();
  197.     }

  198.     /**
  199.      * Returns a new list containing all values of this multi map.
  200.      *
  201.      * @return a new list with all values.
  202.      */
  203.     public List<V> values() {
  204.         List<V> values = new ArrayList<>(size());
  205.         for (List<V> list : map.values()) {
  206.             values.addAll(list);
  207.         }
  208.         return values;
  209.     }

  210.     public Set<Map.Entry<K, V>> entrySet() {
  211.         Set<Map.Entry<K, V>> entrySet = new LinkedHashSet<>(size());
  212.         for (Map.Entry<K, List<V>> entries : map.entrySet()) {
  213.             K key = entries.getKey();
  214.             for (V value : entries.getValue()) {
  215.                 entrySet.add(new SimpleMapEntry<>(key, value));
  216.             }
  217.         }
  218.         return entrySet;
  219.     }

  220.     public MultiMap<K, V> asUnmodifiableMultiMap() {
  221.         LinkedHashMap<K, List<V>> mapCopy = new LinkedHashMap<>(map.size());
  222.         for (Map.Entry<K, List<V>> entry : map.entrySet()) {
  223.             K key = entry.getKey();
  224.             List<V> values = entry.getValue();

  225.             mapCopy.put(key, Collections.unmodifiableList(values));
  226.         }

  227.         return new MultiMap<K, V>(Collections.unmodifiableMap(mapCopy));
  228.     }

  229.     @Override
  230.     public MultiMap<K, V> clone() {
  231.         Map<K, List<V>> clonedMap = new LinkedHashMap<>(map.size());

  232.         // TODO: Use Map.forEach() once Smack's minimum Android API is 24 or higher.
  233.         for (Map.Entry<K, List<V>> entry : map.entrySet()) {
  234.             List<V> clonedList = CollectionUtil.newListWith(entry.getValue());
  235.             clonedMap.put(entry.getKey(), clonedList);
  236.         }

  237.         return new MultiMap<>(clonedMap);
  238.     }

  239.     private static final class SimpleMapEntry<K, V> implements Map.Entry<K, V> {

  240.         private final K key;
  241.         private V value;

  242.         private SimpleMapEntry(K key, V value) {
  243.             this.key = key;
  244.             this.value = value;
  245.         }

  246.         @Override
  247.         public K getKey() {
  248.             return key;
  249.         }

  250.         @Override
  251.         public V getValue() {
  252.             return value;
  253.         }

  254.         @Override
  255.         public V setValue(V value) {
  256.             V tmp = this.value;
  257.             this.value = value;
  258.             return tmp;
  259.         }
  260.     }

  261. }