    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.map;
    018
    019import java.io.IOException;
    020import java.io.ObjectInputStream;
    021import java.io.ObjectOutputStream;
    022import java.io.Serializable;
    023import java.util.AbstractCollection;
    024import java.util.ArrayList;
    025import java.util.Collection;
    026import java.util.HashMap;
    027import java.util.Iterator;
    028import java.util.Map;
    029import java.util.Set;
    030
    031import org.apache.commons.collections4.CollectionUtils;
    032import org.apache.commons.collections4.Factory;
    033import org.apache.commons.collections4.FunctorException;
    034import org.apache.commons.collections4.MultiMap;
    035import org.apache.commons.collections4.Transformer;
    036import org.apache.commons.collections4.iterators.EmptyIterator;
    037import org.apache.commons.collections4.iterators.IteratorChain;
    038import org.apache.commons.collections4.iterators.LazyIteratorChain;
    039import org.apache.commons.collections4.iterators.TransformIterator;
    040
    041/**
    042 * A MultiValueMap decorates another map, allowing it to have
    043 * more than one value for a key.
    044 * <p>
    045 * A {@code MultiMap} is a Map with slightly different semantics.
    046 * Putting a value into the map will add the value to a Collection at that key.
    047 * Getting a value will return a Collection, holding all the values put to that key.
    048 * </p>
    049 * <p>
    050 * This implementation is a decorator, allowing any Map implementation
    051 * to be used as the base.
    052 * </p>
    053 * <p>
    054 * In addition, this implementation allows the type of collection used
    055 * for the values to be controlled. By default, an {@code ArrayList}
    056 * is used, however a {@code Class} to instantiate may be specified,
    057 * or a factory that returns a {@code Collection} instance.
    058 * </p>
    059 * <p>
    060 * <strong>Note that MultiValueMap is not synchronized and is not thread-safe.</strong>
    061 * If you wish to use this map from multiple threads concurrently, you must use
    062 * appropriate synchronization. This class may throw exceptions when accessed
    063 * by concurrent threads without synchronization.
    064 * </p>
    065 *
    066 * @param <K> the type of the keys in this map
    067 * @param <V> the type of the values in this map
    068 * @since 3.2
    069 * @deprecated since 4.1, use {@link org.apache.commons.collections4.MultiValuedMap MultiValuedMap} instead
    070 */
    071@Deprecated
    072public class MultiValueMap<K, V> extends AbstractMapDecorator<K, Object> implements MultiMap<K, V>, Serializable {
    073
    074    /**
    075     * Inner class that provides a simple reflection factory.
    076     */
    077    private static final class ReflectionFactory<T extends Collection<?>> implements Factory<T>, Serializable {
    078
    079        /** Serialization version */
    080        private static final long serialVersionUID = 2986114157496788874L;
    081
    082        private final Class<T> clazz;
    083
    084        ReflectionFactory(final Class<T> clazz) {
    085            this.clazz = clazz;
    086        }
    087
    088        @Override
    089        public T create() {
    090            try {
    091                return clazz.getDeclaredConstructor().newInstance();
    092            } catch (final Exception ex) {
    093                throw new FunctorException("Cannot instantiate class: " + clazz, ex);
    094            }
    095        }
    096
    097        private void readObject(final ObjectInputStream is) throws IOException, ClassNotFoundException {
    098            is.defaultReadObject();
    099            // ensure that the de-serialized class is a Collection, COLLECTIONS-580
    100            if (clazz != null && !Collection.class.isAssignableFrom(clazz)) {
    101                throw new UnsupportedOperationException();
    102            }
    103        }
    104    }
    105
    106    /**
    107     * Inner class that provides the values view.
    108     */
    109    private final class Values extends AbstractCollection<V> {
    110        @Override
    111        public void clear() {
    112            MultiValueMap.this.clear();
    113        }
    114
    115        @Override
    116        public Iterator<V> iterator() {
    117            final IteratorChain<V> chain = new IteratorChain<>();
    118            for (final K k : keySet()) {
    119                chain.addIterator(new ValuesIterator(k));
    120            }
    121            return chain;
    122        }
    123
    124        @Override
    125        public int size() {
    126            return totalSize();
    127        }
    128    }
    129    /**
    130     * Inner class that provides the values iterator.
    131     */
    132    private final class ValuesIterator implements Iterator<V> {
    133        private final Object key;
    134        private final Collection<V> values;
    135        private final Iterator<V> iterator;
    136
    137        ValuesIterator(final Object key) {
    138            this.key = key;
    139            this.values = getCollection(key);
    140            this.iterator = values.iterator();
    141        }
    142
    143        @Override
    144        public boolean hasNext() {
    145            return iterator.hasNext();
    146        }
    147
    148        @Override
    149        public V next() {
    150            return iterator.next();
    151        }
    152
    153        @Override
    154        public void remove() {
    155            iterator.remove();
    156            if (values.isEmpty()) {
    157                MultiValueMap.this.remove(key);
    158            }
    159        }
    160    }
    161
    162    /** Serialization version */
    163    private static final long serialVersionUID = -2214159910087182007L;
    164
    165    /**
    166     * Creates a map which decorates the given {@code map} and
    167     * maps keys to collections of type {@code collectionClass}.
    168     *
    169     * @param <K>  the key type
    170     * @param <V>  the value type
    171     * @param <C>  the collection class type
    172     * @param map  the map to wrap
    173     * @param collectionClass  the type of the collection class
    174     * @return a new multi-value map
    175     * @since 4.0
    176     */
    177    public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
    178                                                                                    final Class<C> collectionClass) {
    179        return new MultiValueMap<>(map, new ReflectionFactory<>(collectionClass));
    180    }
    181
    182    /**
    183     * Creates a map which decorates the given {@code map} and
    184     * creates the value collections using the supplied {@code collectionFactory}.
    185     *
    186     * @param <K>  the key type
    187     * @param <V>  the value type
    188     * @param <C>  the collection class type
    189     * @param map  the map to decorate
    190     * @param collectionFactory  the collection factory (must return a Collection object).
    191     * @return a new multi-value map
    192     * @since 4.0
    193     */
    194    public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
    195            final Factory<C> collectionFactory) {
    196        return new MultiValueMap<>(map, collectionFactory);
    197    }
    198
    199    /**
    200     * Creates a map which wraps the given map and
    201     * maps keys to ArrayLists.
    202     *
    203     * @param <K>  the key type
    204     * @param <V>  the value type
    205     * @param map  the map to wrap
    206     * @return a new multi-value map
    207     * @since 4.0
    208     */
    209    @SuppressWarnings({ "unchecked", "rawtypes" })
    210    public static <K, V> MultiValueMap<K, V> multiValueMap(final Map<K, ? super Collection<V>> map) {
    211        return MultiValueMap.<K, V, ArrayList>multiValueMap((Map<K, ? super Collection>) map, ArrayList.class);
    212    }
    213
    214    /** The factory for creating value collections. */
    215    private final Factory<? extends Collection<V>> collectionFactory;
    216
    217    /** The cached values. */
    218    private transient Collection<V> valuesView;
    219
    220    /**
    221     * Creates a MultiValueMap based on a {@code HashMap} and
    222     * storing the multiple values in an {@code ArrayList}.
    223     */
    224    @SuppressWarnings({ "unchecked", "rawtypes" })
    225    public MultiValueMap() {
    226        this(new HashMap<>(), new ReflectionFactory(ArrayList.class));
    227    }
    228
    229    /**
    230     * Creates a MultiValueMap which decorates the given {@code map} and
    231     * creates the value collections using the supplied {@code collectionFactory}.
    232     *
    233     * @param <C>  the collection class type
    234     * @param map  the map to decorate
    235     * @param collectionFactory  the collection factory which must return a Collection instance
    236     */
    237    @SuppressWarnings("unchecked")
    238    protected <C extends Collection<V>> MultiValueMap(final Map<K, ? super C> map,
    239                                                      final Factory<C> collectionFactory) {
    240        super((Map<K, Object>) map);
    241        if (collectionFactory == null) {
    242            throw new IllegalArgumentException("The factory must not be null");
    243        }
    244        this.collectionFactory = collectionFactory;
    245    }
    246
    247    /**
    248     * Clear the map.
    249     */
    250    @Override
    251    public void clear() {
    252        // If you believe that you have GC issues here, try uncommenting this code
    253//        Set pairs = getMap().entrySet();
    254//        Iterator pairsIterator = pairs.iterator();
    255//        while (pairsIterator.hasNext()) {
    256//            Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
    257//            Collection coll = (Collection) keyValuePair.getValue();
    258//            coll.clear();
    259//        }
    260        decorated().clear();
    261    }
    262
    263    /**
    264     * Checks whether the map contains the value specified.
    265     * <p>
    266     * This checks all collections against all keys for the value, and thus could be slow.
    267     *
    268     * @param value  the value to search for
    269     * @return true if the map contains the value
    270     */
    271    @Override
    272    @SuppressWarnings("unchecked")
    273    public boolean containsValue(final Object value) {
    274        final Set<Map.Entry<K, Object>> pairs = decorated().entrySet();
    275        if (pairs != null) {
    276            for (final Map.Entry<K, Object> entry : pairs) {
    277                if (((Collection<V>) entry.getValue()).contains(value)) {
    278                    return true;
    279                }
    280            }
    281        }
    282        return false;
    283    }
    284
    285    /**
    286     * Checks whether the collection at the specified key contains the value.
    287     *
    288     * @param key  the key to search for
    289     * @param value  the value to search for
    290     * @return true if the map contains the value
    291     */
    292    public boolean containsValue(final Object key, final Object value) {
    293        final Collection<V> coll = getCollection(key);
    294        if (coll == null) {
    295            return false;
    296        }
    297        return coll.contains(value);
    298    }
    299
    300    /**
    301     * Creates a new instance of the map value Collection container
    302     * using the factory.
    303     * <p>
    304     * This method can be overridden to perform your own processing
    305     * instead of using the factory.
    306     *
    307     * @param size  the collection size that is about to be added
    308     * @return the new collection
    309     */
    310    protected Collection<V> createCollection(final int size) {
    311        return collectionFactory.create();
    312    }
    313
    314    /**
    315     * {@inheritDoc}
    316     * <p>
    317     * NOTE: the returned Entry objects will contain as value a {@link Collection}
    318     * of all values that are mapped to the given key. To get a "flattened" version
    319     * of all mappings contained in this map, use {@link #iterator()}.
    320     *
    321     * @see #iterator()
    322     */
    323    @Override
    324    public Set<Entry<K, Object>> entrySet() { // NOPMD
    325        return super.entrySet();
    326    }
    327
    328    /**
    329     * Gets the collection mapped to the specified key.
    330     * This method is a convenience method to typecast the result of {@code get(key)}.
    331     *
    332     * @param key  the key to retrieve
    333     * @return the collection mapped to the key, null if no mapping
    334     */
    335    @SuppressWarnings("unchecked")
    336    public Collection<V> getCollection(final Object key) {
    337        return (Collection<V>) decorated().get(key);
    338    }
    339
    340    /**
    341     * Gets an iterator for all mappings stored in this {@link MultiValueMap}.
    342     * <p>
    343     * The iterator will return multiple Entry objects with the same key
    344     * if there are multiple values mapped to this key.
    345     * <p>
    346     * NOTE: calling {@link java.util.Map.Entry#setValue(Object)} on any of the returned
    347     * elements will result in a {@link UnsupportedOperationException}.
    348     *
    349     * @return the iterator of all mappings in this map
    350     * @since 4.0
    351     */
    352    public Iterator<Entry<K, V>> iterator() {
    353        final Collection<K> allKeys = new ArrayList<>(keySet());
    354        final Iterator<K> keyIterator = allKeys.iterator();
    355
    356        return new LazyIteratorChain<Entry<K, V>>() {
    357            @Override
    358            protected Iterator<? extends Entry<K, V>> nextIterator(final int count) {
    359                if ( ! keyIterator.hasNext() ) {
    360                    return null;
    361                }
    362                final K key = keyIterator.next();
    363                final Transformer<V, Entry<K, V>> transformer = input -> new Entry<K, V>() {
    364                    @Override
    365                    public K getKey() {
    366                        return key;
    367                    }
    368                    @Override
    369                    public V getValue() {
    370                        return input;
    371                    }
    372                    @Override
    373                    public V setValue(final V value) {
    374                        throw new UnsupportedOperationException();
    375                    }
    376                };
    377                return new TransformIterator<>(new ValuesIterator(key), transformer);
    378            }
    379        };
    380    }
    381
    382    /**
    383     * Gets an iterator for the collection mapped to the specified key.
    384     *
    385     * @param key  the key to get an iterator for
    386     * @return the iterator of the collection at the key, empty iterator if key not in map
    387     */
    388    public Iterator<V> iterator(final Object key) {
    389        if (!containsKey(key)) {
    390            return EmptyIterator.<V>emptyIterator();
    391        }
    392        return new ValuesIterator(key);
    393    }
    394
    395    /**
    396     * Adds the value to the collection associated with the specified key.
    397     * <p>
    398     * Unlike a normal {@code Map} the previous value is not replaced.
    399     * Instead, the new value is added to the collection stored against the key.
    400     *
    401     * @param key  the key to store against
    402     * @param value  the value to add to the collection at the key
    403     * @return the value added if the map changed and null if the map did not change
    404     */
    405    @Override
    406    @SuppressWarnings("unchecked")
    407    public Object put(final K key, final Object value) {
    408        boolean result = false;
    409        Collection<V> coll = getCollection(key);
    410        if (coll == null) {
    411            coll = createCollection(1);  // might produce a non-empty collection
    412            coll.add((V) value);
    413            if (!coll.isEmpty()) {
    414                // only add if non-zero size to maintain class state
    415                decorated().put(key, coll);
    416                result = true;  // map definitely changed
    417            }
    418        } else {
    419            result = coll.add((V) value);
    420        }
    421        return result ? value : null;
    422    }
    423
    424    /**
    425     * Adds a collection of values to the collection associated with
    426     * the specified key.
    427     *
    428     * @param key  the key to store against
    429     * @param values  the values to add to the collection at the key, null ignored
    430     * @return true if this map changed
    431     */
    432    public boolean putAll(final K key, final Collection<V> values) {
    433        if (values == null || values.isEmpty()) {
    434            return false;
    435        }
    436        boolean result = false;
    437        Collection<V> coll = getCollection(key);
    438        if (coll == null) {
    439            coll = createCollection(values.size());  // might produce a non-empty collection
    440            coll.addAll(values);
    441            if (!coll.isEmpty()) {
    442                // only add if non-zero size to maintain class state
    443                decorated().put(key, coll);
    444                result = true;  // map definitely changed
    445            }
    446        } else {
    447            result = coll.addAll(values);
    448        }
    449        return result;
    450    }
    451
    452    /**
    453     * Override superclass to ensure that MultiMap instances are
    454     * correctly handled.
    455     * <p>
    456     * If you call this method with a normal map, each entry is
    457     * added using {@code put(Object,Object)}.
    458     * If you call this method with a multi map, each entry is
    459     * added using {@code putAll(Object,Collection)}.
    460     *
    461     * @param map  the map to copy (either a normal or multi map)
    462     */
    463    @Override
    464    @SuppressWarnings("unchecked")
    465    public void putAll(final Map<? extends K, ?> map) {
    466        if (map instanceof MultiMap) {
    467            for (final Map.Entry<? extends K, Object> entry : ((MultiMap<? extends K, V>) map).entrySet()) {
    468                putAll(entry.getKey(), (Collection<V>) entry.getValue());
    469            }
    470        } else {
    471            for (final Map.Entry<? extends K, ?> entry : map.entrySet()) {
    472                put(entry.getKey(), entry.getValue());
    473            }
    474        }
    475    }
    476
    477    /**
    478     * Read the map in using a custom routine.
    479     *
    480     * @param in  the input stream
    481     * @throws IOException if an error occurs while reading from the stream
    482     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    483     * @since 4.0
    484     */
    485    @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect
    486    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    487        in.defaultReadObject();
    488        map = (Map<K, Object>) in.readObject(); // (1)
    489    }
    490
    491    /**
    492     * Removes a specific value from map.
    493     * <p>
    494     * The item is removed from the collection mapped to the specified key.
    495     * Other values attached to that key are unaffected.
    496     * <p>
    497     * If the last value for a key is removed, {@code null} will be returned
    498     * from a subsequent {@code get(key)}.
    499     *
    500     * @param key  the key to remove from
    501     * @param value the value to remove
    502     * @return {@code true} if the mapping was removed, {@code false} otherwise
    503     */
    504    @Override
    505    public boolean removeMapping(final Object key, final Object value) {
    506        final Collection<V> valuesForKey = getCollection(key);
    507        if (valuesForKey == null) {
    508            return false;
    509        }
    510        final boolean removed = valuesForKey.remove(value);
    511        if (!removed) {
    512            return false;
    513        }
    514        if (valuesForKey.isEmpty()) {
    515            remove(key);
    516        }
    517        return true;
    518    }
    519
    520    /**
    521     * Gets the size of the collection mapped to the specified key.
    522     *
    523     * @param key  the key to get size for
    524     * @return the size of the collection at the key, zero if key not in map
    525     */
    526    public int size(final Object key) {
    527        final Collection<V> coll = getCollection(key);
    528        if (coll == null) {
    529            return 0;
    530        }
    531        return coll.size();
    532    }
    533
    534    /**
    535     * Gets the total size of the map by counting all the values.
    536     *
    537     * @return the total size of the map counting all values
    538     */
    539    public int totalSize() {
    540        int total = 0;
    541        for (final Object v : decorated().values()) {
    542            total += CollectionUtils.size(v);
    543        }
    544        return total;
    545    }
    546
    547    /**
    548     * Gets a collection containing all the values in the map.
    549     * <p>
    550     * This returns a collection containing the combination of values from all keys.
    551     *
    552     * @return a collection view of the values contained in this map
    553     */
    554    @Override
    555    @SuppressWarnings("unchecked")
    556    public Collection<Object> values() {
    557        final Collection<V> vs = valuesView;
    558        return (Collection<Object>) (vs != null ? vs : (valuesView = new Values()));
    559    }
    560
    561    /**
    562     * Write the map out using a custom routine.
    563     *
    564     * @param out  the output stream
    565     * @throws IOException if an error occurs while writing to the stream
    566     * @since 4.0
    567     */
    568    private void writeObject(final ObjectOutputStream out) throws IOException {
    569        out.defaultWriteObject();
    570        out.writeObject(map);
    571    }
    572
    573}