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     */
017    package org.apache.commons.collections.map;
018    
019    import java.util.AbstractCollection;
020    import java.util.ArrayList;
021    import java.util.Collection;
022    import java.util.HashMap;
023    import java.util.Iterator;
024    import java.util.Map;
025    import java.util.Set;
026    
027    import org.apache.commons.collections.Factory;
028    import org.apache.commons.collections.FunctorException;
029    import org.apache.commons.collections.MultiMap;
030    import org.apache.commons.collections.iterators.EmptyIterator;
031    import org.apache.commons.collections.iterators.IteratorChain;
032    
033    /**
034     * A MultiValueMap decorates another map, allowing it to have
035     * more than one value for a key.
036     * <p>
037     * A <code>MultiMap</code> is a Map with slightly different semantics.
038     * Putting a value into the map will add the value to a Collection at that key.
039     * Getting a value will return a Collection, holding all the values put to that key.
040     * <p>
041     * This implementation is a decorator, allowing any Map implementation
042     * to be used as the base.
043     * <p>
044     * In addition, this implementation allows the type of collection used
045     * for the values to be controlled. By default, an <code>ArrayList</code>
046     * is used, however a <code>Class</code> to instantiate may be specified,
047     * or a factory that returns a <code>Collection</code> instance.
048     * <p>
049     * <strong>Note that MultiValueMap is not synchronized and is not thread-safe.</strong>
050     * If you wish to use this map from multiple threads concurrently, you must use
051     * appropriate synchronization. This class may throw exceptions when accessed
052     * by concurrent threads without synchronization.
053     *
054     * @author James Carman
055     * @author Christopher Berry
056     * @author James Strachan
057     * @author Steve Downey
058     * @author Stephen Colebourne
059     * @author Julien Buret
060     * @author Serhiy Yevtushenko
061     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
062     * @since Commons Collections 3.2
063     */
064    public class MultiValueMap extends AbstractMapDecorator implements MultiMap {
065    
066        /** The factory for creating value collections. */
067        private final Factory collectionFactory;
068        /** The cached values. */
069        private transient Collection values;
070    
071        /**
072         * Creates a map which wraps the given map and
073         * maps keys to ArrayLists.
074         *
075         * @param map  the map to wrap
076         */
077        public static MultiValueMap decorate(Map map) {
078            return new MultiValueMap(map, new ReflectionFactory(ArrayList.class));
079        }
080    
081        /**
082         * Creates a map which decorates the given <code>map</code> and
083         * maps keys to collections of type <code>collectionClass</code>.
084         *
085         * @param map  the map to wrap
086         * @param collectionClass  the type of the collection class
087         */
088        public static MultiValueMap decorate(Map map, Class collectionClass) {
089            return new MultiValueMap(map, new ReflectionFactory(collectionClass));
090        }
091    
092        /**
093         * Creates a map which decorates the given <code>map</code> and
094         * creates the value collections using the supplied <code>collectionFactory</code>.
095         *
096         * @param map  the map to decorate
097         * @param collectionFactory  the collection factory (must return a Collection object).
098         */
099        public static MultiValueMap decorate(Map map, Factory collectionFactory) {
100            return new MultiValueMap(map, collectionFactory);
101        }
102    
103        //-----------------------------------------------------------------------
104        /**
105         * Creates a MultiValueMap based on a <code>HashMap</code> and
106         * storing the multiple values in an <code>ArrayList</code>.
107         */
108        public MultiValueMap() {
109            this(new HashMap(), new ReflectionFactory(ArrayList.class));
110        }
111    
112        /**
113         * Creates a MultiValueMap which decorates the given <code>map</code> and
114         * creates the value collections using the supplied <code>collectionFactory</code>.
115         *
116         * @param map  the map to decorate
117         * @param collectionFactory  the collection factory which must return a Collection instance
118         */
119        protected MultiValueMap(Map map, Factory collectionFactory) {
120            super(map);
121            if (collectionFactory == null) {
122                throw new IllegalArgumentException("The factory must not be null");
123            }
124            this.collectionFactory = collectionFactory;
125        }
126    
127        //-----------------------------------------------------------------------
128        /**
129         * Clear the map.
130         */
131        public void clear() {
132            // If you believe that you have GC issues here, try uncommenting this code
133    //        Set pairs = getMap().entrySet();
134    //        Iterator pairsIterator = pairs.iterator();
135    //        while (pairsIterator.hasNext()) {
136    //            Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
137    //            Collection coll = (Collection) keyValuePair.getValue();
138    //            coll.clear();
139    //        }
140            getMap().clear();
141        }
142    
143        /**
144         * Removes a specific value from map.
145         * <p>
146         * The item is removed from the collection mapped to the specified key.
147         * Other values attached to that key are unaffected.
148         * <p>
149         * If the last value for a key is removed, <code>null</code> will be returned
150         * from a subsequant <code>get(key)</code>.
151         *
152         * @param key  the key to remove from
153         * @param value the value to remove
154         * @return the value removed (which was passed in), null if nothing removed
155         */
156        public Object remove(Object key, Object value) {
157            Collection valuesForKey = getCollection(key);
158            if (valuesForKey == null) {
159                return null;
160            }
161            boolean removed = valuesForKey.remove(value);
162            if (removed == false) {
163                return null;
164            }
165            if (valuesForKey.isEmpty()) {
166                remove(key);
167            }
168            return value;
169        }
170    
171        /**
172         * Checks whether the map contains the value specified.
173         * <p>
174         * This checks all collections against all keys for the value, and thus could be slow.
175         *
176         * @param value  the value to search for
177         * @return true if the map contains the value
178         */
179        public boolean containsValue(Object value) {
180            Set pairs = getMap().entrySet();
181            if (pairs == null) {
182                return false;
183            }
184            Iterator pairsIterator = pairs.iterator();
185            while (pairsIterator.hasNext()) {
186                Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
187                Collection coll = (Collection) keyValuePair.getValue();
188                if (coll.contains(value)) {
189                    return true;
190                }
191            }
192            return false;
193        }
194    
195        /**
196         * Adds the value to the collection associated with the specified key.
197         * <p>
198         * Unlike a normal <code>Map</code> the previous value is not replaced.
199         * Instead the new value is added to the collection stored against the key.
200         *
201         * @param key  the key to store against
202         * @param value  the value to add to the collection at the key
203         * @return the value added if the map changed and null if the map did not change
204         */
205        public Object put(Object key, Object value) {
206            boolean result = false;
207            Collection coll = getCollection(key);
208            if (coll == null) {
209                coll = createCollection(1);
210                result = coll.add(value);
211                if (coll.size() > 0) {
212                    // only add if non-zero size to maintain class state
213                    getMap().put(key, coll);
214                    result = false;
215                }
216            } else {
217                result = coll.add(value);
218            }
219            return (result ? value : null);
220        }
221    
222        /**
223         * Override superclass to ensure that MultiMap instances are
224         * correctly handled.
225         * <p>
226         * If you call this method with a normal map, each entry is
227         * added using <code>put(Object,Object)</code>.
228         * If you call this method with a multi map, each entry is
229         * added using <code>putAll(Object,Collection)</code>.
230         *
231         * @param map  the map to copy (either a normal or multi map)
232         */
233        public void putAll(Map map) {
234            if (map instanceof MultiMap) {
235                for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
236                    Map.Entry entry = (Map.Entry) it.next();
237                    Collection coll = (Collection) entry.getValue();
238                    putAll(entry.getKey(), coll);
239                }
240            } else {
241                for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
242                    Map.Entry entry = (Map.Entry) it.next();
243                    put(entry.getKey(), entry.getValue());
244                }
245            }
246        }
247    
248        /**
249         * Gets a collection containing all the values in the map.
250         * <p>
251         * This returns a collection containing the combination of values from all keys.
252         *
253         * @return a collection view of the values contained in this map
254         */
255        public Collection values() {
256            Collection vs = values;
257            return (vs != null ? vs : (values = new Values()));
258        }
259    
260        /**
261         * Checks whether the collection at the specified key contains the value.
262         *
263         * @param value  the value to search for
264         * @return true if the map contains the value
265         */
266        public boolean containsValue(Object key, Object value) {
267            Collection coll = getCollection(key);
268            if (coll == null) {
269                return false;
270            }
271            return coll.contains(value);
272        }
273    
274        /**
275         * Gets the collection mapped to the specified key.
276         * This method is a convenience method to typecast the result of <code>get(key)</code>.
277         *
278         * @param key  the key to retrieve
279         * @return the collection mapped to the key, null if no mapping
280         */
281        public Collection getCollection(Object key) {
282            return (Collection) getMap().get(key);
283        }
284    
285        /**
286         * Gets the size of the collection mapped to the specified key.
287         *
288         * @param key  the key to get size for
289         * @return the size of the collection at the key, zero if key not in map
290         */
291        public int size(Object key) {
292            Collection coll = getCollection(key);
293            if (coll == null) {
294                return 0;
295            }
296            return coll.size();
297        }
298    
299        /**
300         * Adds a collection of values to the collection associated with
301         * the specified key.
302         *
303         * @param key  the key to store against
304         * @param values  the values to add to the collection at the key, null ignored
305         * @return true if this map changed
306         */
307        public boolean putAll(Object key, Collection values) {
308            if (values == null || values.size() == 0) {
309                return false;
310            }
311            Collection coll = getCollection(key);
312            if (coll == null) {
313                coll = createCollection(values.size());
314                boolean result = coll.addAll(values);
315                if (coll.size() > 0) {
316                    // only add if non-zero size to maintain class state
317                    getMap().put(key, coll);
318                    result = false;
319                }
320                return result;
321            } else {
322                return coll.addAll(values);
323            }
324        }
325    
326        /**
327         * Gets an iterator for the collection mapped to the specified key.
328         *
329         * @param key  the key to get an iterator for
330         * @return the iterator of the collection at the key, empty iterator if key not in map
331         */
332        public Iterator iterator(Object key) {
333            if (!containsKey(key)) {
334                return EmptyIterator.INSTANCE;
335            } else {
336                return new ValuesIterator(key);
337            }
338        }
339    
340        /**
341         * Gets the total size of the map by counting all the values.
342         *
343         * @return the total size of the map counting all values
344         */
345        public int totalSize() {
346            int total = 0;
347            Collection values = getMap().values();
348            for (Iterator it = values.iterator(); it.hasNext();) {
349                Collection coll = (Collection) it.next();
350                total += coll.size();
351            }
352            return total;
353        }
354    
355        /**
356         * Creates a new instance of the map value Collection container
357         * using the factory.
358         * <p>
359         * This method can be overridden to perform your own processing
360         * instead of using the factory.
361         *
362         * @param size  the collection size that is about to be added
363         * @return the new collection
364         */
365        protected Collection createCollection(int size) {
366            return (Collection) collectionFactory.create();
367        }
368    
369        //-----------------------------------------------------------------------
370        /**
371         * Inner class that provides the values view.
372         */
373        private class Values extends AbstractCollection {
374            public Iterator iterator() {
375                final IteratorChain chain = new IteratorChain();
376                for (Iterator it = keySet().iterator(); it.hasNext();) {
377                    chain.addIterator(new ValuesIterator(it.next()));
378                }
379                return chain;
380            }
381    
382            public int size() {
383                return totalSize();
384            }
385    
386            public void clear() {
387                MultiValueMap.this.clear();
388            }
389        }
390    
391        /**
392         * Inner class that provides the values iterator.
393         */
394        private class ValuesIterator implements Iterator {
395            private final Object key;
396            private final Collection values;
397            private final Iterator iterator;
398    
399            public ValuesIterator(Object key) {
400                this.key = key;
401                this.values = getCollection(key);
402                this.iterator = values.iterator();
403            }
404    
405            public void remove() {
406                iterator.remove();
407                if (values.isEmpty()) {
408                    MultiValueMap.this.remove(key);
409                }
410            }
411    
412            public boolean hasNext() {
413                return iterator.hasNext();
414            }
415    
416            public Object next() {
417                return iterator.next();
418            }
419        }
420    
421        /**
422         * Inner class that provides a simple reflection factory.
423         */
424        private static class ReflectionFactory implements Factory {
425            private final Class clazz;
426    
427            public ReflectionFactory(Class clazz) {
428                this.clazz = clazz;
429            }
430    
431            public Object create() {
432                try {
433                    return clazz.newInstance();
434                } catch (Exception ex) {
435                    throw new FunctorException("Cannot instantiate class: " + clazz, ex);
436                }
437            }
438        }
439    
440    }