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