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