View Javadoc

1   /*
2    * Copyright (C) 2004 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 library is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU Lesser General Public
9    * License as published by the Free Software Foundation; either
10   * version 2.1 of the License, or (at your option) any later version.
11   *
12   * This library 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 GNU
15   * Lesser General Public License for more details.
16   *
17   * You should have received a copy of the GNU Lesser General Public
18   * License along with this library; if not, visit
19   * http://www.gnu.org/licenses/lgpl.html or write to the Free Software
20   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, 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.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             // compare wrapped maps
292             return store.equals(((MultiValueMap) o).store);
293         } else if (o instanceof Map) {
294             // compare wrapped map with object
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             // remove the list if it is now empty
427             // (saves space, and allows equals to work)
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 }