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