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;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.util.AbstractCollection;
022    import java.util.ArrayList;
023    import java.util.Collection;
024    import java.util.HashMap;
025    import java.util.Iterator;
026    import java.util.Map;
027    import java.util.NoSuchElementException;
028    import java.util.Set;
029    
030    import org.apache.commons.collections.iterators.EmptyIterator;
031    
032    /** 
033     * <code>MultiHashMap</code> is the default implementation of the 
034     * {@link org.apache.commons.collections.MultiMap MultiMap} interface.
035     * <p>
036     * A <code>MultiMap</code> is a Map with slightly different semantics.
037     * Putting a value into the map will add the value to a Collection at that key.
038     * Getting a value will return a Collection, holding all the values put to that key.
039     * <p>
040     * This implementation uses an <code>ArrayList</code> as the collection.
041     * The internal storage list is made available without cloning via the
042     * <code>get(Object)</code> and <code>entrySet()</code> methods.
043     * The implementation returns <code>null</code> when there are no values mapped to a key.
044     * <p>
045     * For example:
046     * <pre>
047     * MultiMap mhm = new MultiHashMap();
048     * mhm.put(key, "A");
049     * mhm.put(key, "B");
050     * mhm.put(key, "C");
051     * List list = (List) mhm.get(key);</pre>
052     * <p>
053     * <code>list</code> will be a list containing "A", "B", "C".
054     *
055     * @deprecated Class now available as MultiValueMap in map subpackage.
056     * This version is due to be removed in collections v4.0.
057     *
058     * @since Commons Collections 2.0
059     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
060     * 
061     * @author Christopher Berry
062     * @author James Strachan
063     * @author Steve Downey
064     * @author Stephen Colebourne
065     * @author Julien Buret
066     * @author Serhiy Yevtushenko
067     * @author Robert Ribnitz
068     */
069    public class MultiHashMap extends HashMap implements MultiMap {
070        
071        // backed values collection
072        private transient Collection values = null;
073        
074        // compatibility with commons-collection releases 2.0/2.1
075        private static final long serialVersionUID = 1943563828307035349L;
076    
077        /**
078         * Constructor.
079         */
080        public MultiHashMap() {
081            super();
082        }
083    
084        /**
085         * Constructor.
086         * 
087         * @param initialCapacity  the initial map capacity
088         */
089        public MultiHashMap(int initialCapacity) {
090            super(initialCapacity);
091        }
092    
093        /**
094         * Constructor.
095         * 
096         * @param initialCapacity  the initial map capacity
097         * @param loadFactor  the amount 0.0-1.0 at which to resize the map
098         */
099        public MultiHashMap(int initialCapacity, float loadFactor) {
100            super(initialCapacity, loadFactor);
101        }
102    
103        /**
104         * Constructor that copies the input map creating an independent copy.
105         * <p>
106         * This method performs different behaviour depending on whether the map
107         * specified is a MultiMap or not. If a MultiMap is specified, each internal
108         * collection is also cloned. If the specified map only implements Map, then
109         * the values are not cloned.
110         * <p>
111         * NOTE: From Commons Collections 3.1 this method correctly copies a MultiMap
112         * to form a truly independent new map.
113         * NOTE: From Commons Collections 3.2 this method delegates to the newly
114         * added putAll(Map) override method.
115         * 
116         * @param mapToCopy  a Map to copy
117         */
118        public MultiHashMap(Map mapToCopy) {
119            // be careful of JDK 1.3 vs 1.4 differences
120            super((int) (mapToCopy.size() * 1.4f));
121            putAll(mapToCopy);
122        }
123    
124        /**
125         * Read the object during deserialization.
126         */
127        private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
128            // This method is needed because the 1.2/1.3 Java deserialisation called
129            // put and thus messed up that method
130            
131            // default read object
132            s.defaultReadObject();
133    
134            // problem only with jvm <1.4
135            String version = "1.2";
136            try {
137                version = System.getProperty("java.version");
138            } catch (SecurityException ex) {
139                // ignore and treat as 1.2/1.3
140            }
141    
142            if (version.startsWith("1.2") || version.startsWith("1.3")) {
143                for (Iterator iterator = entrySet().iterator(); iterator.hasNext();) {
144                    Map.Entry entry = (Map.Entry) iterator.next();
145                    // put has created a extra collection level, remove it
146                    super.put(entry.getKey(), ((Collection) entry.getValue()).iterator().next());
147                }
148            }
149        }
150    
151        //-----------------------------------------------------------------------
152        /**
153         * Gets the total size of the map by counting all the values.
154         * 
155         * @return the total size of the map counting all values
156         * @since Commons Collections 3.1
157         */
158        public int totalSize() {
159            int total = 0;
160            Collection values = super.values();
161            for (Iterator it = values.iterator(); it.hasNext();) {
162                Collection coll = (Collection) it.next();
163                total += coll.size();
164            }
165            return total;
166        }
167    
168        /**
169         * Gets the collection mapped to the specified key.
170         * This method is a convenience method to typecast the result of <code>get(key)</code>.
171         * 
172         * @param key  the key to retrieve
173         * @return the collection mapped to the key, null if no mapping
174         * @since Commons Collections 3.1
175         */
176        public Collection getCollection(Object key) {
177            return (Collection) get(key);
178        }
179    
180        /**
181         * Gets the size of the collection mapped to the specified key.
182         * 
183         * @param key  the key to get size for
184         * @return the size of the collection at the key, zero if key not in map
185         * @since Commons Collections 3.1
186         */
187        public int size(Object key) {
188            Collection coll = getCollection(key);
189            if (coll == null) {
190                return 0;
191            }
192            return coll.size();
193        }
194    
195        /**
196         * Gets an iterator for the collection mapped to the specified key.
197         * 
198         * @param key  the key to get an iterator for
199         * @return the iterator of the collection at the key, empty iterator if key not in map
200         * @since Commons Collections 3.1
201         */
202        public Iterator iterator(Object key) {
203            Collection coll = getCollection(key);
204            if (coll == null) {
205                return EmptyIterator.INSTANCE;
206            }
207            return coll.iterator();
208        }
209    
210        /**
211         * Adds the value to the collection associated with the specified key.
212         * <p>
213         * Unlike a normal <code>Map</code> the previous value is not replaced.
214         * Instead the new value is added to the collection stored against the key.
215         *
216         * @param key  the key to store against
217         * @param value  the value to add to the collection at the key
218         * @return the value added if the map changed and null if the map did not change
219         */    
220        public Object put(Object key, Object value) {
221            // NOTE:: put is called during deserialization in JDK < 1.4 !!!!!!
222            //        so we must have a readObject()
223            Collection coll = getCollection(key);
224            if (coll == null) {
225                coll = createCollection(null);
226                super.put(key, coll);
227            }
228            boolean results = coll.add(value);
229            return (results ? value : null);
230        }
231    
232        /**
233         * Override superclass to ensure that MultiMap instances are
234         * correctly handled.
235         * <p>
236         * NOTE: Prior to version 3.2, putAll(map) did not work properly
237         * when passed a MultiMap.
238         * 
239         * @param map  the map to copy (either a normal or multi map)
240         */
241        public void putAll(Map map) {
242            if (map instanceof MultiMap) {
243                for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
244                    Map.Entry entry = (Map.Entry) it.next();
245                    Collection coll = (Collection) entry.getValue();
246                    putAll(entry.getKey(), coll);
247                }
248            } else {
249                for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
250                    Map.Entry entry = (Map.Entry) it.next();
251                    put(entry.getKey(), entry.getValue());
252                }
253            }
254        }
255    
256        /**
257         * Adds a collection of values to the collection associated with the specified key.
258         *
259         * @param key  the key to store against
260         * @param values  the values to add to the collection at the key, null ignored
261         * @return true if this map changed
262         * @since Commons Collections 3.1
263         */    
264        public boolean putAll(Object key, Collection values) {
265            if (values == null || values.size() == 0) {
266                return false;
267            }
268            Collection coll = getCollection(key);
269            if (coll == null) {
270                coll = createCollection(values);
271                if (coll.size() == 0) {
272                    return false;
273                }
274                super.put(key, coll);
275                return true;
276            } else {
277                return coll.addAll(values);
278            }
279        }
280    
281        /**
282         * Checks whether the map contains the value specified.
283         * <p>
284         * This checks all collections against all keys for the value, and thus could be slow.
285         * 
286         * @param value  the value to search for
287         * @return true if the map contains the value
288         */
289        public boolean containsValue(Object value) {
290            Set pairs = super.entrySet();
291    
292            if (pairs == null) {
293                return false;
294            }
295            Iterator pairsIterator = pairs.iterator();
296            while (pairsIterator.hasNext()) {
297                Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
298                Collection coll = (Collection) keyValuePair.getValue();
299                if (coll.contains(value)) {
300                    return true;
301                }
302            }
303            return false;
304        }
305    
306        /**
307         * Checks whether the collection at the specified key contains the value.
308         * 
309         * @param value  the value to search for
310         * @return true if the map contains the value
311         * @since Commons Collections 3.1
312         */
313        public boolean containsValue(Object key, Object value) {
314            Collection coll = getCollection(key);
315            if (coll == null) {
316                return false;
317            }
318            return coll.contains(value);
319        }
320    
321        /**
322         * Removes a specific value from map.
323         * <p>
324         * The item is removed from the collection mapped to the specified key.
325         * Other values attached to that key are unaffected.
326         * <p>
327         * If the last value for a key is removed, <code>null</code> will be returned
328         * from a subsequant <code>get(key)</code>.
329         * 
330         * @param key  the key to remove from
331         * @param item  the value to remove
332         * @return the value removed (which was passed in), null if nothing removed
333         */
334        public Object remove(Object key, Object item) {
335            Collection valuesForKey = getCollection(key);
336            if (valuesForKey == null) {
337                return null;
338            }
339            boolean removed = valuesForKey.remove(item);
340            if (removed == false) {
341                return null;
342            }
343            // remove the list if it is now empty
344            // (saves space, and allows equals to work)
345            if (valuesForKey.isEmpty()){
346                remove(key);
347            }
348            return item;
349        }
350    
351        /**
352         * Clear the map.
353         * <p>
354         * This clears each collection in the map, and so may be slow.
355         */
356        public void clear() {
357            // For gc, clear each list in the map
358            Set pairs = super.entrySet();
359            Iterator pairsIterator = pairs.iterator();
360            while (pairsIterator.hasNext()) {
361                Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
362                Collection coll = (Collection) keyValuePair.getValue();
363                coll.clear();
364            }
365            super.clear();
366        }
367    
368        /**
369         * Gets a collection containing all the values in the map.
370         * <p>
371         * This returns a collection containing the combination of values from all keys.
372         *
373         * @return a collection view of the values contained in this map
374         */
375        public Collection values() {
376            Collection vs = values;
377            return (vs != null ? vs : (values = new Values()));
378        }
379    
380        /**
381         * Gets the values iterator from the superclass, as used by inner class.
382         *
383         * @return iterator
384         */
385        Iterator superValuesIterator() {
386            return super.values().iterator();
387        }
388    
389        //-----------------------------------------------------------------------
390        /**
391         * Inner class to view the elements.
392         */
393        private class Values extends AbstractCollection {
394    
395            public Iterator iterator() {
396                return new ValueIterator();
397            }
398    
399            public int size() {
400                int compt = 0;
401                Iterator it = iterator();
402                while (it.hasNext()) {
403                    it.next();
404                    compt++;
405                }
406                return compt;
407            }
408    
409            public void clear() {
410                MultiHashMap.this.clear();
411            }
412    
413        }
414    
415        /**
416         * Inner iterator to view the elements.
417         */
418        private class ValueIterator implements Iterator {
419            private Iterator backedIterator;
420            private Iterator tempIterator;
421    
422            private ValueIterator() {
423                backedIterator = MultiHashMap.this.superValuesIterator();
424            }
425    
426            private boolean searchNextIterator() {
427                while (tempIterator == null || tempIterator.hasNext() == false) {
428                    if (backedIterator.hasNext() == false) {
429                        return false;
430                    }
431                    tempIterator = ((Collection) backedIterator.next()).iterator();
432                }
433                return true;
434            }
435    
436            public boolean hasNext() {
437                return searchNextIterator();
438            }
439    
440            public Object next() {
441                if (searchNextIterator() == false) {
442                    throw new NoSuchElementException();
443                }
444                return tempIterator.next();
445            }
446    
447            public void remove() {
448                if (tempIterator == null) {
449                    throw new IllegalStateException();
450                }
451                tempIterator.remove();
452            }
453    
454        }
455    
456        //-----------------------------------------------------------------------
457        /**
458         * Clones the map creating an independent copy.
459         * <p>
460         * The clone will shallow clone the collections as well as the map.
461         * 
462         * @return the cloned map
463         */
464        public Object clone() {
465            MultiHashMap cloned = (MultiHashMap) super.clone();
466    
467            // clone each Collection container
468            for (Iterator it = cloned.entrySet().iterator(); it.hasNext();) {
469                Map.Entry entry = (Map.Entry) it.next();
470                Collection coll = (Collection) entry.getValue();
471                Collection newColl = createCollection(coll);
472                entry.setValue(newColl);
473            }
474            return cloned;
475        }
476    
477        /** 
478         * Creates a new instance of the map value Collection container.
479         * <p>
480         * This method can be overridden to use your own collection type.
481         *
482         * @param coll  the collection to copy, may be null
483         * @return the new collection
484         */
485        protected Collection createCollection(Collection coll) {
486            if (coll == null) {
487                return new ArrayList();
488            } else {
489                return new ArrayList(coll);
490            }
491        }
492    
493    }