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