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