View Javadoc

1   /*
2    * Copyright (C) 2004-2006 Christian Siefkes <christian@siefkes.net>.
3    * Development of this software is supported by the German Research Society,
4    * Berlin-Brandenburg Graduate School in Distributed Information Systems
5    * (DFG grant no. GRK 316).
6    *
7    * This program is free software; you can redistribute it and/or modify
8    * it under the terms of the GNU General Public License as published by
9    * the Free Software Foundation; either version 2 of the License, or
10   * (at your option) any later version.
11   *
12   * This program is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   * GNU General Public License for more details.
16   *
17   * You should have received a copy of the GNU General Public License
18   * along with this program; if not, visit
19   * http://www.gnu.org/licenses/gpl.html or write to the Free Software
20   * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
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&lt;String, String&gt; mm =
50   *     new MultiValueMap&lt;String, String&gt;();
51   * mm.put(key, "A");
52   * mm.put(key, "B");
53   * mm.put(key, "C");
54   * Collection&lt;String&gt; 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             // compare wrapped maps
294             return store.equals(((MultiValueMap) o).store);
295         } else if (o instanceof Map) {
296             // compare wrapped map with object
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             // remove the list if it is now empty
429             // (saves space, and allows equals to work)
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 }