    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     * @param <T> the type of results supplied by this supplier.
    078     */
    079    private static final class ReflectionFactory<T extends Collection<?>> implements Factory<T>, Serializable {
    080
    081        /** Serialization version */
    082        private static final long serialVersionUID = 2986114157496788874L;
    083
    084        private final Class<T> clazz;
    085
    086        ReflectionFactory(final Class<T> clazz) {
    087            this.clazz = clazz;
    088        }
    089
    090        @Override
    091        public T create() {
    092            try {
    093                return clazz.getDeclaredConstructor().newInstance();
    094            } catch (final Exception ex) {
    095                throw new FunctorException("Cannot instantiate class: " + clazz, ex);
    096            }
    097        }
    098
    099        /**
    100         * Deserializes an instance from an ObjectInputStream.
    101         *
    102         * @param in The source ObjectInputStream.
    103         * @throws IOException            Any of the usual Input/Output related exceptions.
    104         * @throws ClassNotFoundException A class of a serialized object cannot be found.
    105         */
    106        private void readObject(final ObjectInputStream is) throws IOException, ClassNotFoundException {
    107            is.defaultReadObject();
    108            // ensure that the de-serialized class is a Collection, COLLECTIONS-580
    109            if (clazz != null && !Collection.class.isAssignableFrom(clazz)) {
    110                throw new UnsupportedOperationException();
    111            }
    112        }
    113    }
    114
    115    /**
    116     * Inner class that provides the values view.
    117     */
    118    private final class Values extends AbstractCollection<V> {
    119        @Override
    120        public void clear() {
    121            MultiValueMap.this.clear();
    122        }
    123
    124        @Override
    125        public Iterator<V> iterator() {
    126            final IteratorChain<V> chain = new IteratorChain<>();
    127            for (final K k : keySet()) {
    128                chain.addIterator(new ValuesIterator(k));
    129            }
    130            return chain;
    131        }
    132
    133        @Override
    134        public int size() {
    135            return totalSize();
    136        }
    137    }
    138    /**
    139     * Inner class that provides the values iterator.
    140     */
    141    private final class ValuesIterator implements Iterator<V> {
    142        private final Object key;
    143        private final Collection<V> values;
    144        private final Iterator<V> iterator;
    145
    146        ValuesIterator(final Object key) {
    147            this.key = key;
    148            this.values = getCollection(key);
    149            this.iterator = values.iterator();
    150        }
    151
    152        @Override
    153        public boolean hasNext() {
    154            return iterator.hasNext();
    155        }
    156
    157        @Override
    158        public V next() {
    159            return iterator.next();
    160        }
    161
    162        @Override
    163        public void remove() {
    164            iterator.remove();
    165            if (values.isEmpty()) {
    166                MultiValueMap.this.remove(key);
    167            }
    168        }
    169    }
    170
    171    /** Serialization version */
    172    private static final long serialVersionUID = -2214159910087182007L;
    173
    174    /**
    175     * Creates a map which decorates the given {@code map} and
    176     * maps keys to collections of type {@code collectionClass}.
    177     *
    178     * @param <K>  the key type
    179     * @param <V>  the value type
    180     * @param <C>  the collection class type
    181     * @param map  the map to wrap
    182     * @param collectionClass  the type of the collection class
    183     * @return a new multi-value map
    184     * @since 4.0
    185     */
    186    public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
    187                                                                                    final Class<C> collectionClass) {
    188        return new MultiValueMap<>(map, new ReflectionFactory<>(collectionClass));
    189    }
    190
    191    /**
    192     * Creates a map which decorates the given {@code map} and
    193     * creates the value collections using the supplied {@code collectionFactory}.
    194     *
    195     * @param <K>  the key type
    196     * @param <V>  the value type
    197     * @param <C>  the collection class type
    198     * @param map  the map to decorate
    199     * @param collectionFactory  the collection factory (must return a Collection object).
    200     * @return a new multi-value map
    201     * @since 4.0
    202     */
    203    public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
    204            final Factory<C> collectionFactory) {
    205        return new MultiValueMap<>(map, collectionFactory);
    206    }
    207
    208    /**
    209     * Creates a map which wraps the given map and
    210     * maps keys to ArrayLists.
    211     *
    212     * @param <K>  the key type
    213     * @param <V>  the value type
    214     * @param map  the map to wrap
    215     * @return a new multi-value map
    216     * @since 4.0
    217     */
    218    @SuppressWarnings({ "unchecked", "rawtypes" })
    219    public static <K, V> MultiValueMap<K, V> multiValueMap(final Map<K, ? super Collection<V>> map) {
    220        return MultiValueMap.<K, V, ArrayList>multiValueMap((Map<K, ? super Collection>) map, ArrayList.class);
    221    }
    222
    223    /** The factory for creating value collections. */
    224    private final Factory<? extends Collection<V>> collectionFactory;
    225
    226    /** The cached values. */
    227    private transient Collection<V> valuesView;
    228
    229    /**
    230     * Creates a MultiValueMap based on a {@code HashMap} and
    231     * storing the multiple values in an {@code ArrayList}.
    232     */
    233    @SuppressWarnings({ "unchecked", "rawtypes" })
    234    public MultiValueMap() {
    235        this(new HashMap<>(), new ReflectionFactory(ArrayList.class));
    236    }
    237
    238    /**
    239     * Creates a MultiValueMap which decorates the given {@code map} and
    240     * creates the value collections using the supplied {@code collectionFactory}.
    241     *
    242     * @param <C>  the collection class type
    243     * @param map  the map to decorate
    244     * @param collectionFactory  the collection factory which must return a Collection instance
    245     */
    246    @SuppressWarnings("unchecked")
    247    protected <C extends Collection<V>> MultiValueMap(final Map<K, ? super C> map,
    248                                                      final Factory<C> collectionFactory) {
    249        super((Map<K, Object>) map);
    250        if (collectionFactory == null) {
    251            throw new IllegalArgumentException("The factory must not be null");
    252        }
    253        this.collectionFactory = collectionFactory;
    254    }
    255
    256    /**
    257     * Clear the map.
    258     */
    259    @Override
    260    public void clear() {
    261        // If you believe that you have GC issues here, try uncommenting this code
    262//        Set pairs = getMap().entrySet();
    263//        Iterator pairsIterator = pairs.iterator();
    264//        while (pairsIterator.hasNext()) {
    265//            Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
    266//            Collection coll = (Collection) keyValuePair.getValue();
    267//            coll.clear();
    268//        }
    269        decorated().clear();
    270    }
    271
    272    /**
    273     * Checks whether the map contains the value specified.
    274     * <p>
    275     * This checks all collections against all keys for the value, and thus could be slow.
    276     * </p>
    277     *
    278     * @param value  the value to search for
    279     * @return true if the map contains the value
    280     */
    281    @Override
    282    @SuppressWarnings("unchecked")
    283    public boolean containsValue(final Object value) {
    284        final Set<Map.Entry<K, Object>> pairs = decorated().entrySet();
    285        if (pairs != null) {
    286            for (final Map.Entry<K, Object> entry : pairs) {
    287                if (((Collection<V>) entry.getValue()).contains(value)) {
    288                    return true;
    289                }
    290            }
    291        }
    292        return false;
    293    }
    294
    295    /**
    296     * Checks whether the collection at the specified key contains the value.
    297     *
    298     * @param key  the key to search for
    299     * @param value  the value to search for
    300     * @return true if the map contains the value
    301     */
    302    public boolean containsValue(final Object key, final Object value) {
    303        final Collection<V> coll = getCollection(key);
    304        if (coll == null) {
    305            return false;
    306        }
    307        return coll.contains(value);
    308    }
    309
    310    /**
    311     * Creates a new instance of the map value Collection container
    312     * using the factory.
    313     * <p>
    314     * This method can be overridden to perform your own processing
    315     * instead of using the factory.
    316     * </p>
    317     *
    318     * @param size  the collection size that is about to be added
    319     * @return the new collection
    320     */
    321    protected Collection<V> createCollection(final int size) {
    322        return collectionFactory.get();
    323    }
    324
    325    /**
    326     * {@inheritDoc}
    327     * <p>
    328     * Note: the returned Entry objects will contain as value a {@link Collection}
    329     * of all values that are mapped to the given key. To get a "flattened" version
    330     * of all mappings contained in this map, use {@link #iterator()}.
    331     * </p>
    332     *
    333     * @see #iterator()
    334     */
    335    @Override
    336    public Set<Entry<K, Object>> entrySet() { // NOPMD
    337        return super.entrySet();
    338    }
    339
    340    /**
    341     * Gets the collection mapped to the specified key.
    342     * This method is a convenience method to typecast the result of {@code get(key)}.
    343     *
    344     * @param key  the key to retrieve
    345     * @return the collection mapped to the key, null if no mapping
    346     */
    347    @SuppressWarnings("unchecked")
    348    public Collection<V> getCollection(final Object key) {
    349        return (Collection<V>) decorated().get(key);
    350    }
    351
    352    /**
    353     * Gets an iterator for all mappings stored in this {@link MultiValueMap}.
    354     * <p>
    355     * The iterator will return multiple Entry objects with the same key
    356     * if there are multiple values mapped to this key.
    357     * </p>
    358     * <p>
    359     * Note: calling {@link java.util.Map.Entry#setValue(Object)} on any of the returned
    360     * elements will result in a {@link UnsupportedOperationException}.
    361     * </p>
    362     *
    363     * @return the iterator of all mappings in this map
    364     * @since 4.0
    365     */
    366    public Iterator<Entry<K, V>> iterator() {
    367        final Collection<K> allKeys = new ArrayList<>(keySet());
    368        final Iterator<K> keyIterator = allKeys.iterator();
    369
    370        return new LazyIteratorChain<Entry<K, V>>() {
    371            @Override
    372            protected Iterator<? extends Entry<K, V>> nextIterator(final int count) {
    373                if (!keyIterator.hasNext()) {
    374                    return null;
    375                }
    376                final K key = keyIterator.next();
    377                final Transformer<V, Entry<K, V>> transformer = input -> new Entry<K, V>() {
    378                    @Override
    379                    public K getKey() {
    380                        return key;
    381                    }
    382
    383                    @Override
    384                    public V getValue() {
    385                        return input;
    386                    }
    387
    388                    @Override
    389                    public V setValue(final V value) {
    390                        throw new UnsupportedOperationException();
    391                    }
    392                };
    393                return new TransformIterator<>(new ValuesIterator(key), transformer);
    394            }
    395        };
    396    }
    397
    398    /**
    399     * Gets an iterator for the collection mapped to the specified key.
    400     *
    401     * @param key  the key to get an iterator for
    402     * @return the iterator of the collection at the key, empty iterator if key not in map
    403     */
    404    public Iterator<V> iterator(final Object key) {
    405        if (!containsKey(key)) {
    406            return EmptyIterator.<V>emptyIterator();
    407        }
    408        return new ValuesIterator(key);
    409    }
    410
    411    /**
    412     * Adds the value to the collection associated with the specified key.
    413     * <p>
    414     * Unlike a normal {@code Map} the previous value is not replaced.
    415     * Instead, the new value is added to the collection stored against the key.
    416     * </p>
    417     *
    418     * @param key  the key to store against
    419     * @param value  the value to add to the collection at the key
    420     * @return the value added if the map changed and null if the map did not change
    421     */
    422    @Override
    423    @SuppressWarnings("unchecked")
    424    public Object put(final K key, final Object value) {
    425        boolean result = false;
    426        Collection<V> coll = getCollection(key);
    427        if (coll == null) {
    428            coll = createCollection(1);  // might produce a non-empty collection
    429            coll.add((V) value);
    430            if (!coll.isEmpty()) {
    431                // only add if non-zero size to maintain class state
    432                decorated().put(key, coll);
    433                result = true;  // map definitely changed
    434            }
    435        } else {
    436            result = coll.add((V) value);
    437        }
    438        return result ? value : null;
    439    }
    440
    441    /**
    442     * Adds a collection of values to the collection associated with
    443     * the specified key.
    444     *
    445     * @param key  the key to store against
    446     * @param values  the values to add to the collection at the key, null ignored
    447     * @return true if this map changed
    448     */
    449    public boolean putAll(final K key, final Collection<V> values) {
    450        if (values == null || values.isEmpty()) {
    451            return false;
    452        }
    453        boolean result = false;
    454        Collection<V> coll = getCollection(key);
    455        if (coll == null) {
    456            coll = createCollection(values.size());  // might produce a non-empty collection
    457            coll.addAll(values);
    458            if (!coll.isEmpty()) {
    459                // only add if non-zero size to maintain class state
    460                decorated().put(key, coll);
    461                result = true;  // map definitely changed
    462            }
    463        } else {
    464            result = coll.addAll(values);
    465        }
    466        return result;
    467    }
    468
    469    /**
    470     * Override superclass to ensure that MultiMap instances are
    471     * correctly handled.
    472     * <p>
    473     * If you call this method with a normal map, each entry is
    474     * added using {@code put(Object,Object)}.
    475     * If you call this method with a multi map, each entry is
    476     * added using {@code putAll(Object,Collection)}.
    477     * </p>
    478     *
    479     * @param map  the map to copy (either a normal or multi map)
    480     */
    481    @Override
    482    @SuppressWarnings("unchecked")
    483    public void putAll(final Map<? extends K, ?> map) {
    484        if (map instanceof MultiMap) {
    485            for (final Map.Entry<? extends K, Object> entry : ((MultiMap<? extends K, V>) map).entrySet()) {
    486                putAll(entry.getKey(), (Collection<V>) entry.getValue());
    487            }
    488        } else {
    489            for (final Map.Entry<? extends K, ?> entry : map.entrySet()) {
    490                put(entry.getKey(), entry.getValue());
    491            }
    492        }
    493    }
    494
    495    /**
    496     * Deserializes the map in using a custom routine.
    497     *
    498     * @param in  the input stream
    499     * @throws IOException if an error occurs while reading from the stream
    500     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
    501     * @since 4.0
    502     */
    503    @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect
    504    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    505        in.defaultReadObject();
    506        map = (Map<K, Object>) in.readObject(); // (1)
    507    }
    508
    509    /**
    510     * Removes a specific value from map.
    511     * <p>
    512     * The item is removed from the collection mapped to the specified key.
    513     * Other values attached to that key are unaffected.
    514     * </p>
    515     * <p>
    516     * If the last value for a key is removed, {@code null} will be returned
    517     * from a subsequent {@code get(key)}.
    518     * </p>
    519     *
    520     * @param key  the key to remove from
    521     * @param value the value to remove
    522     * @return {@code true} if the mapping was removed, {@code false} otherwise
    523     */
    524    @Override
    525    public boolean removeMapping(final Object key, final Object value) {
    526        final Collection<V> valuesForKey = getCollection(key);
    527        if (valuesForKey == null) {
    528            return false;
    529        }
    530        final boolean removed = valuesForKey.remove(value);
    531        if (!removed) {
    532            return false;
    533        }
    534        if (valuesForKey.isEmpty()) {
    535            remove(key);
    536        }
    537        return true;
    538    }
    539
    540    /**
    541     * Gets the size of the collection mapped to the specified key.
    542     *
    543     * @param key  the key to get size for
    544     * @return the size of the collection at the key, zero if key not in map
    545     */
    546    public int size(final Object key) {
    547        final Collection<V> coll = getCollection(key);
    548        if (coll == null) {
    549            return 0;
    550        }
    551        return coll.size();
    552    }
    553
    554    /**
    555     * Gets the total size of the map by counting all the values.
    556     *
    557     * @return the total size of the map counting all values
    558     */
    559    public int totalSize() {
    560        int total = 0;
    561        for (final Object v : decorated().values()) {
    562            total += CollectionUtils.size(v);
    563        }
    564        return total;
    565    }
    566
    567    /**
    568     * Gets a collection containing all the values in the map.
    569     * <p>
    570     * This returns a collection containing the combination of values from all keys.
    571     * </p>
    572     *
    573     * @return a collection view of the values contained in this map
    574     */
    575    @Override
    576    @SuppressWarnings("unchecked")
    577    public Collection<Object> values() {
    578        final Collection<V> vs = valuesView;
    579        return (Collection<Object>) (vs != null ? vs : (valuesView = new Values()));
    580    }
    581
    582    /**
    583     * Serializes this object to an ObjectOutputStream.
    584     *
    585     * @param out the target ObjectOutputStream.
    586     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    587     * @since 4.0
    588     */
    589    private void writeObject(final ObjectOutputStream out) throws IOException {
    590        out.defaultWriteObject();
    591        out.writeObject(map);
    592    }
    593
    594}