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 }