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