1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package de.fu_berlin.ties.util;
23
24 import java.util.AbstractCollection;
25 import java.util.ArrayList;
26 import java.util.Collection;
27 import java.util.HashMap;
28 import java.util.Iterator;
29 import java.util.Map;
30 import java.util.NoSuchElementException;
31 import java.util.Set;
32
33 /***
34 * A <code>MultiValueMap</code> allows storing multiple values for each key.
35 * Putting a value into the map will add the value to a Collection at that key.
36 * Getting a value will return a Collection, holding all the values put to that
37 * key.
38 * <p>
39 * This implementation uses an <code>ArrayList</code> as the collection.
40 * When there are no values mapped to a key, <code>null</code> is returned.
41 * <p>
42 * This class does not implement the {@link java.util.Map} interface because
43 * of the slightly different semantics: <code>put</code> adds a value of
44 * type <code>V</code>, but <code>get</code> returns a Collection of
45 * <code>V</code> objects instead of a single <code>V</code> object.
46 * <p>
47 * For example:
48 * <pre>
49 * MultiValueMap<String, String> mm =
50 * new MultiValueMap<String, String>();
51 * mm.put(key, "A");
52 * mm.put(key, "B");
53 * mm.put(key, "C");
54 * Collection<String> col = mm.get(key);
55 * </pre>
56 *
57 * <p>
58 * <code>col</code> will be a collection containing "A", "B", "C".
59 * <p>
60 * This class has been adapted from the <code>MultiHashMap</code> in the
61 * <a href="http://jakarta.apache.org/commons/collections/">Jakarta Commons
62 * Collections</a>.
63 *
64 * @author Christian Siefkes
65 * @version $Revision: 1.10 $, $Date: 2006/10/21 16:04:27 $, $Author: siefkes $
66 * @param <K> the type of keys
67 * @param <V> the type of values
68 */
69 public class MultiValueMap<K, V> {
70
71
72 /***
73 * Inner class to view the elements.
74 */
75 private class Values extends AbstractCollection<V> {
76
77 /***
78 * {@inheritDoc}
79 */
80 public Iterator<V> iterator() {
81 return new ValueIterator();
82 }
83
84 /***
85 * {@inheritDoc}
86 */
87 public int size() {
88 int compt = 0;
89 Iterator it = iterator();
90 while (it.hasNext()) {
91 it.next();
92 compt++;
93 }
94 return compt;
95 }
96
97 /***
98 * {@inheritDoc}
99 */
100 public void clear() {
101 MultiValueMap.this.clear();
102 }
103
104 }
105
106 /***
107 * Inner iterator to view the elements.
108 */
109 private final class ValueIterator implements Iterator<V> {
110
111 /***
112 * The backed iterator.
113 */
114 private Iterator<Collection<V>> backedIterator;
115
116 /***
117 * Iterator used to search.
118 */
119 private Iterator<V> tempIterator;
120
121 /***
122 * Creates a new instance.
123 */
124 private ValueIterator() {
125 backedIterator = store.values().iterator();
126 }
127
128 /***
129 * Searches for the next available iterator.
130 * @return <code>true</code> if there is a new iterator
131 */
132 private boolean searchNextIterator() {
133 while (tempIterator == null || !tempIterator.hasNext()) {
134 if (!backedIterator.hasNext()) {
135 return false;
136 }
137 tempIterator = backedIterator.next().iterator();
138 }
139 return true;
140 }
141
142 /***
143 * {@inheritDoc}
144 */
145 public boolean hasNext() {
146 return searchNextIterator();
147 }
148
149 /***
150 * {@inheritDoc}
151 */
152 public V next() {
153 if (!searchNextIterator()) {
154 throw new NoSuchElementException();
155 }
156 return tempIterator.next();
157 }
158
159 /***
160 * {@inheritDoc}
161 */
162 public void remove() {
163 if (tempIterator == null) {
164 throw new IllegalStateException();
165 }
166 tempIterator.remove();
167 }
168
169 }
170
171 /***
172 * Wrapped map used as storage.
173 */
174 private final Map<K, Collection<V>> store;
175
176 /***
177 * Backed values collection.
178 */
179 private transient Collection<V> values = null;
180
181 /***
182 * Creates a new instance, using a {@link HashMap} as storage.
183 */
184 public MultiValueMap() {
185 this(new HashMap<K, Collection<V>>());
186 }
187
188 /***
189 * Creates a new instance.
190 *
191 * @param wrappedMap wrapped map used as storage, e.g. a {@link HashMap} or
192 * a {@link java.util.TreeMap}
193 */
194 public MultiValueMap(final Map<K, Collection<V>> wrappedMap) {
195 store = wrappedMap;
196 }
197
198 /***
199 * Creates a new instance of the map value Collection container.
200 * <p>
201 * This method can be overridden to use your own collection type.
202 *
203 * @param coll the collection to copy, may be <code>null</code>
204 * @return the new collection
205 */
206 protected Collection<V> createCollection(
207 final Collection<? extends V> coll) {
208 if (coll == null) {
209 return new ArrayList<V>();
210 } else {
211 return new ArrayList<V>(coll);
212 }
213 }
214
215 /***
216 * Removes all mappings from this map.
217 */
218 public void clear() {
219 store.clear();
220 }
221
222 /***
223 * Returns <code>true</code> if this map contains a mapping for the
224 * specified key. More formally, returns <code>true</code> if and only if
225 * this map contains a mapping for a key <code>k</code> such that
226 * <code>(key==null ? k==null : key.equals(k))</code>. (There can be one or
227 * several such mappings.)
228 *
229 * @param key key whose presence in this map is to be tested
230 * @return <code>true</code> if this map contains a mapping for the
231 * pecified key
232 */
233 public boolean containsKey(final K key) {
234 return store.containsKey(key);
235 }
236
237 /***
238 * Checks whether the map contains the value specified.
239 * <p>
240 * This checks all collections against all keys for the value, and thus
241 * could be slow.
242 *
243 * @param value the value to search for
244 * @return <code>true</code> if the map contains the value
245 */
246 public boolean containsValue(final V value) {
247 final Set pairs = store.entrySet();
248 if (pairs == null) {
249 return false;
250 }
251
252 final Iterator pairsIterator = pairs.iterator();
253 Map.Entry keyValuePair;
254
255 while (pairsIterator.hasNext()) {
256 keyValuePair = (Map.Entry) pairsIterator.next();
257 Collection coll = (Collection) keyValuePair.getValue();
258 if (coll.contains(value)) {
259 return true;
260 }
261 }
262 return false;
263 }
264
265 /***
266 * Checks whether the collection at the specified key contains the value.
267 *
268 * @param key the key to use
269 * @param value the value to search for
270 * @return <code>true</code> if the map contains the value at the specified
271 * key
272 */
273 public boolean containsValue(final K key, final V value) {
274 Collection<V> coll = get(key);
275 if (coll == null) {
276 return false;
277 } else {
278 return coll.contains(value);
279 }
280 }
281
282 /***
283 * Compares the specified object with this map for equality. Returns
284 * <code>true</code> if the given object is also a
285 * <code>MultiValueMap</code> map or a map of collections and the two Maps
286 * represent the same mappings.
287 *
288 * @param o object to be compared for equality with this map
289 * @return <code>true</code> if the specified object is equal to this map
290 */
291 public boolean equals(final Object o) {
292 if (o instanceof MultiValueMap) {
293
294 return store.equals(((MultiValueMap) o).store);
295 } else if (o instanceof Map) {
296
297 return store.equals(o);
298 } else {
299 return false;
300 }
301 }
302
303 /***
304 * Returns the collection of values to which this map maps the specified
305 * key.
306 *
307 * @param key key whose associated value is to be returned
308 * @return the collection of values to which this map maps the specified
309 * key, or <code>null</code> if the map contains no mapping for this key
310 */
311 public Collection<V> get(final K key) {
312 return store.get(key);
313 }
314
315 /***
316 * Returns the hash code value for this map.
317 *
318 * @return the hash code value for this map.
319 */
320 public int hashCode() {
321 return store.hashCode();
322 }
323
324 /***
325 * Returns <code>true</code> if this map contains no key-value mappings.
326 *
327 * @return <code>true</code> if this map contains no key-value mappings
328 */
329 public boolean isEmpty() {
330 return store.isEmpty();
331 }
332
333 /***
334 * Returns a set view of the keys contained in this map. The set is backed
335 * by the map, so changes to the map are reflected in the set, and
336 * vice-versa.
337 *
338 * @return a set view of the keys contained in this map
339 */
340 public Set<K> keySet() {
341 return store.keySet();
342 }
343
344 /***
345 * Adds the value to the collection associated with the specified key.
346 * <p>
347 * Unlike a normal <code>Map</code> the previous value is not replaced.
348 * Instead the new value is added to the collection stored against the key.
349 *
350 * @param key the key to store against
351 * @param value the value to add to the collection at the key
352 * @return the value added if the map changed and <code>null</code> if the
353 * map did not change
354 */
355 public V put(final K key, final V value) {
356 Collection<V> coll = get(key);
357 if (coll == null) {
358 coll = createCollection(null);
359 store.put(key, coll);
360 }
361 final boolean result = coll.add(value);
362 return (result ? value : null);
363 }
364
365 /***
366 * Adds a collection of values to the collection associated with the
367 * specified key.
368 *
369 * @param key the key to store against
370 * @param valueCol the values to add to the collection at the key,
371 * ignored if <code>null</code>
372 * @return <code>true</code> if this map changed
373 */
374 public boolean putAll(final K key, final Collection<? extends V> valueCol) {
375 if (valueCol == null || valueCol.size() == 0) {
376 return false;
377 }
378
379 Collection<V> coll = get(key);
380 if (coll == null) {
381 coll = createCollection(valueCol);
382 if (coll.size() == 0) {
383 return false;
384 }
385 store.put(key, coll);
386 return true;
387 } else {
388 return coll.addAll(valueCol);
389 }
390 }
391
392 /***
393 * Removes all mappings for this key from this map if any are present.
394 * Returns the collection of value to which the map previously associated
395 * the key, or <code>null</code> if the map contained no mappings for this
396 * key. The map will not contain any mappings for the specified key once
397 * the call returns.
398 *
399 * @param key key whose mappings are to be removed from the map.
400 * @return collection of values previously associated with specified key,
401 * or <code>null</code> if there was no mapping for key
402 */
403 public Collection<V> remove(final K key) {
404 return store.remove(key);
405 }
406
407 /***
408 * Removes a specific value from map.
409 * <p>
410 * The item is removed from the collection mapped to the specified key.
411 * Other values attached to that key are unaffected.
412 * <p>
413 * If the last value for a key is removed, <code>null</code> will be
414 * returned from a subsequant <code>get(key)</code>.
415 *
416 * @param key the key to remove from
417 * @param item the value to remove
418 * @return <code>true</code> iff the map changed as a result of this call
419 */
420 public boolean remove(final K key, final V item) {
421 final Collection<V> valuesForKey = get(key);
422
423 if (valuesForKey == null) {
424 return false;
425 } else {
426 final boolean didRemove = valuesForKey.remove(item);
427
428
429
430 if (valuesForKey.isEmpty()) {
431 remove(key);
432 }
433
434 return didRemove;
435 }
436 }
437
438 /***
439 * Returns the number of key-value mappings in this map. If the map contains
440 * more than <code>Integer.MAX_VALUE</code> elements, returns
441 * <code>Integer.MAX_VALUE</code>.
442 *
443 * @return the number of key-value mappings in this map
444 */
445 public int size() {
446 return store.size();
447 }
448
449 /***
450 * Gets the size of the collection mapped to the specified key.
451 *
452 * @param key the key to get size for
453 * @return the size of the collection at the key, zero if key not in map
454 */
455 public int size(final K key) {
456 final Collection coll = get(key);
457 if (coll == null) {
458 return 0;
459 } else {
460 return coll.size();
461 }
462 }
463
464 /***
465 * Gets the total size of the map by counting all the values.
466 *
467 * @return the total size of the map counting all values
468 */
469 public int totalSize() {
470 int total = 0;
471 final Iterator<Collection<V>> it = store.values().iterator();
472 Collection coll;
473
474 while (it.hasNext()) {
475 coll = it.next();
476 total += coll.size();
477 }
478 return total;
479 }
480
481 /***
482 * Gets a collection containing all the values in the map.
483 * <p>
484 * This returns a collection containing the combination of values from all
485 * keys.
486 *
487 * @return a collection view of the values contained in this map
488 */
489 public Collection<V> values() {
490 if (values == null) {
491 values = new Values();
492 }
493 return values;
494 }
495
496 }