1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.map;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
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.Set;
31
32 import org.apache.commons.collections.CollectionUtils;
33 import org.apache.commons.collections.Factory;
34 import org.apache.commons.collections.FunctorException;
35 import org.apache.commons.collections.MultiMap;
36 import org.apache.commons.collections.iterators.EmptyIterator;
37 import org.apache.commons.collections.iterators.IteratorChain;
38
39 /**
40 * A MultiValueMap decorates another map, allowing it to have
41 * more than one value for a key.
42 * <p>
43 * A <code>MultiMap</code> is a Map with slightly different semantics.
44 * Putting a value into the map will add the value to a Collection at that key.
45 * Getting a value will return a Collection, holding all the values put to that key.
46 * <p>
47 * This implementation is a decorator, allowing any Map implementation
48 * to be used as the base.
49 * <p>
50 * In addition, this implementation allows the type of collection used
51 * for the values to be controlled. By default, an <code>ArrayList</code>
52 * is used, however a <code>Class</code> to instantiate may be specified,
53 * or a factory that returns a <code>Collection</code> instance.
54 * <p>
55 * <strong>Note that MultiValueMap is not synchronized and is not thread-safe.</strong>
56 * If you wish to use this map from multiple threads concurrently, you must use
57 * appropriate synchronization. This class may throw exceptions when accessed
58 * by concurrent threads without synchronization.
59 *
60 * @since 3.2
61 * @version $Id: MultiValueMap.java 1451177 2013-02-28 11:42:31Z tn $
62 */
63 public class MultiValueMap<K, V> extends AbstractMapDecorator<K, Object> implements MultiMap<K, V>, Serializable {
64
65 /** Serialization version */
66 private static final long serialVersionUID = -2214159910087182007L;
67
68 /** The factory for creating value collections. */
69 private final Factory<? extends Collection<V>> collectionFactory;
70 /** The cached values. */
71 private transient Collection<V> valuesView;
72
73 /**
74 * Creates a map which wraps the given map and
75 * maps keys to ArrayLists.
76 *
77 * @param <K> the key type
78 * @param <V> the value type
79 * @param map the map to wrap
80 * @return a new multi-value map
81 */
82 @SuppressWarnings({ "unchecked", "rawtypes" })
83 public static <K, V> MultiValueMap<K, V> multiValueMap(final Map<K, ? super Collection<V>> map) {
84 return MultiValueMap.<K, V, ArrayList> multiValueMap((Map<K, ? super Collection>) map, ArrayList.class);
85 }
86
87 /**
88 * Creates a map which decorates the given <code>map</code> and
89 * maps keys to collections of type <code>collectionClass</code>.
90 *
91 * @param <K> the key type
92 * @param <V> the value type
93 * @param <C> the collection class type
94 * @param map the map to wrap
95 * @param collectionClass the type of the collection class
96 * @return a new multi-value map
97 */
98 public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
99 final Class<C> collectionClass) {
100 return new MultiValueMap<K, V>(map, new ReflectionFactory<C>(collectionClass));
101 }
102
103 /**
104 * Creates a map which decorates the given <code>map</code> and
105 * creates the value collections using the supplied <code>collectionFactory</code>.
106 *
107 * @param <K> the key type
108 * @param <V> the value type
109 * @param <C> the collection class type
110 * @param map the map to decorate
111 * @param collectionFactory the collection factory (must return a Collection object).
112 * @return a new multi-value map
113 */
114 public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
115 final Factory<C> collectionFactory) {
116 return new MultiValueMap<K, V>(map, collectionFactory);
117 }
118
119 //-----------------------------------------------------------------------
120 /**
121 * Creates a MultiValueMap based on a <code>HashMap</code> and
122 * storing the multiple values in an <code>ArrayList</code>.
123 */
124 @SuppressWarnings({ "unchecked", "rawtypes" })
125 public MultiValueMap() {
126 this(new HashMap<K, V>(), new ReflectionFactory(ArrayList.class));
127 }
128
129 /**
130 * Creates a MultiValueMap which decorates the given <code>map</code> and
131 * creates the value collections using the supplied <code>collectionFactory</code>.
132 *
133 * @param <C> the collection class type
134 * @param map the map to decorate
135 * @param collectionFactory the collection factory which must return a Collection instance
136 */
137 @SuppressWarnings("unchecked")
138 protected <C extends Collection<V>> MultiValueMap(final Map<K, ? super C> map,
139 final Factory<C> collectionFactory) {
140 super((Map<K, Object>) map);
141 if (collectionFactory == null) {
142 throw new IllegalArgumentException("The factory must not be null");
143 }
144 this.collectionFactory = collectionFactory;
145 }
146
147 //-----------------------------------------------------------------------
148 /**
149 * Write the map out using a custom routine.
150 *
151 * @param out the output stream
152 * @throws IOException
153 * @since 4.0
154 */
155 private void writeObject(final ObjectOutputStream out) throws IOException {
156 out.defaultWriteObject();
157 out.writeObject(map);
158 }
159
160 /**
161 * Read the map in using a custom routine.
162 *
163 * @param in the input stream
164 * @throws IOException
165 * @throws ClassNotFoundException
166 * @since 4.0
167 */
168 @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect
169 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
170 in.defaultReadObject();
171 map = (Map<K, Object>) in.readObject(); // (1)
172 }
173
174 //-----------------------------------------------------------------------
175 /**
176 * Clear the map.
177 */
178 @Override
179 public void clear() {
180 // If you believe that you have GC issues here, try uncommenting this code
181 // Set pairs = getMap().entrySet();
182 // Iterator pairsIterator = pairs.iterator();
183 // while (pairsIterator.hasNext()) {
184 // Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
185 // Collection coll = (Collection) keyValuePair.getValue();
186 // coll.clear();
187 // }
188 decorated().clear();
189 }
190
191 /**
192 * Removes a specific value from map.
193 * <p>
194 * The item is removed from the collection mapped to the specified key.
195 * Other values attached to that key are unaffected.
196 * <p>
197 * If the last value for a key is removed, <code>null</code> will be returned
198 * from a subsequant <code>get(key)</code>.
199 *
200 * @param key the key to remove from
201 * @param value the value to remove
202 * @return the value removed (which was passed in), null if nothing removed
203 */
204 @SuppressWarnings("unchecked")
205 public V remove(final Object key, final Object value) {
206 final Collection<V> valuesForKey = getCollection(key);
207 if (valuesForKey == null) {
208 return null;
209 }
210 final boolean removed = valuesForKey.remove(value);
211 if (removed == false) {
212 return null;
213 }
214 if (valuesForKey.isEmpty()) {
215 remove(key);
216 }
217 return (V) value;
218 }
219
220 /**
221 * Checks whether the map contains the value specified.
222 * <p>
223 * This checks all collections against all keys for the value, and thus could be slow.
224 *
225 * @param value the value to search for
226 * @return true if the map contains the value
227 */
228 @Override
229 @SuppressWarnings("unchecked")
230 public boolean containsValue(final Object value) {
231 final Set<Map.Entry<K, Object>> pairs = decorated().entrySet();
232 if (pairs != null) {
233 for (final Map.Entry<K, Object> entry : pairs) {
234 if (((Collection<V>) entry.getValue()).contains(value)) {
235 return true;
236 }
237 }
238 }
239 return false;
240 }
241
242 /**
243 * Adds the value to the collection associated with the specified key.
244 * <p>
245 * Unlike a normal <code>Map</code> the previous value is not replaced.
246 * Instead the new value is added to the collection stored against the key.
247 *
248 * @param key the key to store against
249 * @param value the value to add to the collection at the key
250 * @return the value added if the map changed and null if the map did not change
251 */
252 @Override
253 @SuppressWarnings("unchecked")
254 public Object put(final K key, final Object value) {
255 boolean result = false;
256 Collection<V> coll = getCollection(key);
257 if (coll == null) {
258 coll = createCollection(1); // might produce a non-empty collection
259 coll.add((V) value);
260 if (coll.size() > 0) {
261 // only add if non-zero size to maintain class state
262 decorated().put(key, coll);
263 result = true; // map definitely changed
264 }
265 } else {
266 result = coll.add((V) value);
267 }
268 return result ? value : null;
269 }
270
271 /**
272 * Override superclass to ensure that MultiMap instances are
273 * correctly handled.
274 * <p>
275 * If you call this method with a normal map, each entry is
276 * added using <code>put(Object,Object)</code>.
277 * If you call this method with a multi map, each entry is
278 * added using <code>putAll(Object,Collection)</code>.
279 *
280 * @param map the map to copy (either a normal or multi map)
281 */
282 @Override
283 @SuppressWarnings("unchecked")
284 public void putAll(final Map<? extends K, ?> map) {
285 if (map instanceof MultiMap) {
286 for (final Map.Entry<? extends K, Object> entry : ((MultiMap<? extends K, V>) map).entrySet()) {
287 putAll(entry.getKey(), (Collection<V>) entry.getValue());
288 }
289 } else {
290 for (final Map.Entry<? extends K, ?> entry : map.entrySet()) {
291 put(entry.getKey(), entry.getValue());
292 }
293 }
294 }
295
296 /**
297 * Gets a collection containing all the values in the map.
298 * <p>
299 * This returns a collection containing the combination of values from all keys.
300 *
301 * @return a collection view of the values contained in this map
302 */
303 @Override
304 @SuppressWarnings("unchecked")
305 public Collection<Object> values() {
306 final Collection<V> vs = valuesView;
307 return (Collection<Object>) (vs != null ? vs : (valuesView = new Values()));
308 }
309
310 /**
311 * Checks whether the collection at the specified key contains the value.
312 *
313 * @param key the key to search for
314 * @param value the value to search for
315 * @return true if the map contains the value
316 */
317 public boolean containsValue(final Object key, final Object value) {
318 final Collection<V> coll = getCollection(key);
319 if (coll == null) {
320 return false;
321 }
322 return coll.contains(value);
323 }
324
325 /**
326 * Gets the collection mapped to the specified key.
327 * This method is a convenience method to typecast the result of <code>get(key)</code>.
328 *
329 * @param key the key to retrieve
330 * @return the collection mapped to the key, null if no mapping
331 */
332 @SuppressWarnings("unchecked")
333 public Collection<V> getCollection(final Object key) {
334 return (Collection<V>) decorated().get(key);
335 }
336
337 /**
338 * Gets the size of the collection mapped to the specified key.
339 *
340 * @param key the key to get size for
341 * @return the size of the collection at the key, zero if key not in map
342 */
343 public int size(final Object key) {
344 final Collection<V> coll = getCollection(key);
345 if (coll == null) {
346 return 0;
347 }
348 return coll.size();
349 }
350
351 /**
352 * Adds a collection of values to the collection associated with
353 * the specified key.
354 *
355 * @param key the key to store against
356 * @param values the values to add to the collection at the key, null ignored
357 * @return true if this map changed
358 */
359 public boolean putAll(final K key, final Collection<V> values) {
360 if (values == null || values.size() == 0) {
361 return false;
362 }
363 boolean result = false;
364 Collection<V> coll = getCollection(key);
365 if (coll == null) {
366 coll = createCollection(values.size()); // might produce a non-empty collection
367 coll.addAll(values);
368 if (coll.size() > 0) {
369 // only add if non-zero size to maintain class state
370 decorated().put(key, coll);
371 result = true; // map definitely changed
372 }
373 } else {
374 result = coll.addAll(values);
375 }
376 return result;
377 }
378
379 /**
380 * Gets an iterator for the collection mapped to the specified key.
381 *
382 * @param key the key to get an iterator for
383 * @return the iterator of the collection at the key, empty iterator if key not in map
384 */
385 public Iterator<V> iterator(final Object key) {
386 if (!containsKey(key)) {
387 return EmptyIterator.<V>emptyIterator();
388 }
389 return new ValuesIterator(key);
390 }
391
392 /**
393 * Gets the total size of the map by counting all the values.
394 *
395 * @return the total size of the map counting all values
396 */
397 public int totalSize() {
398 int total = 0;
399 for (final Object v : decorated().values()) {
400 total += CollectionUtils.size(v);
401 }
402 return total;
403 }
404
405 /**
406 * Creates a new instance of the map value Collection container
407 * using the factory.
408 * <p>
409 * This method can be overridden to perform your own processing
410 * instead of using the factory.
411 *
412 * @param size the collection size that is about to be added
413 * @return the new collection
414 */
415 protected Collection<V> createCollection(final int size) {
416 return collectionFactory.create();
417 }
418
419 //-----------------------------------------------------------------------
420 /**
421 * Inner class that provides the values view.
422 */
423 private class Values extends AbstractCollection<V> {
424 @Override
425 public Iterator<V> iterator() {
426 final IteratorChain<V> chain = new IteratorChain<V>();
427 for (final K k : keySet()) {
428 chain.addIterator(new ValuesIterator(k));
429 }
430 return chain;
431 }
432
433 @Override
434 public int size() {
435 return totalSize();
436 }
437
438 @Override
439 public void clear() {
440 MultiValueMap.this.clear();
441 }
442 }
443
444 /**
445 * Inner class that provides the values iterator.
446 */
447 private class ValuesIterator implements Iterator<V> {
448 private final Object key;
449 private final Collection<V> values;
450 private final Iterator<V> iterator;
451
452 public ValuesIterator(final Object key) {
453 this.key = key;
454 this.values = getCollection(key);
455 this.iterator = values.iterator();
456 }
457
458 public void remove() {
459 iterator.remove();
460 if (values.isEmpty()) {
461 MultiValueMap.this.remove(key);
462 }
463 }
464
465 public boolean hasNext() {
466 return iterator.hasNext();
467 }
468
469 public V next() {
470 return iterator.next();
471 }
472 }
473
474 /**
475 * Inner class that provides a simple reflection factory.
476 */
477 private static class ReflectionFactory<T extends Collection<?>> implements Factory<T>, Serializable {
478
479 /** Serialization version */
480 private static final long serialVersionUID = 2986114157496788874L;
481
482 private final Class<T> clazz;
483
484 public ReflectionFactory(final Class<T> clazz) {
485 this.clazz = clazz;
486 }
487
488 public T create() {
489 try {
490 return clazz.newInstance();
491 } catch (final Exception ex) {
492 throw new FunctorException("Cannot instantiate class: " + clazz, ex);
493 }
494 }
495 }
496
497 }