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.collections4.map;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
23 import java.util.AbstractCollection;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.HashMap;
27 import java.util.Iterator;
28 import java.util.Map;
29 import java.util.Set;
30
31 import org.apache.commons.collections4.CollectionUtils;
32 import org.apache.commons.collections4.Factory;
33 import org.apache.commons.collections4.FunctorException;
34 import org.apache.commons.collections4.MultiMap;
35 import org.apache.commons.collections4.Transformer;
36 import org.apache.commons.collections4.iterators.EmptyIterator;
37 import org.apache.commons.collections4.iterators.IteratorChain;
38 import org.apache.commons.collections4.iterators.LazyIteratorChain;
39 import org.apache.commons.collections4.iterators.TransformIterator;
40
41 /**
42 * A MultiValueMap decorates another map, allowing it to have
43 * more than one value for a key.
44 * <p>
45 * A {@code MultiMap} is a Map with slightly different semantics.
46 * Putting a value into the map will add the value to a Collection at that key.
47 * Getting a value will return a Collection, holding all the values put to that key.
48 * </p>
49 * <p>
50 * This implementation is a decorator, allowing any Map implementation
51 * to be used as the base.
52 * </p>
53 * <p>
54 * In addition, this implementation allows the type of collection used
55 * for the values to be controlled. By default, an {@code ArrayList}
56 * is used, however a {@code Class} to instantiate may be specified,
57 * or a factory that returns a {@code Collection} instance.
58 * </p>
59 * <p>
60 * <strong>Note that MultiValueMap is not synchronized and is not thread-safe.</strong>
61 * If you wish to use this map from multiple threads concurrently, you must use
62 * appropriate synchronization. This class may throw exceptions when accessed
63 * by concurrent threads without synchronization.
64 * </p>
65 *
66 * @param <K> the type of the keys in this map
67 * @param <V> the type of the values in this map
68 * @since 3.2
69 * @deprecated since 4.1, use {@link org.apache.commons.collections4.MultiValuedMap MultiValuedMap} instead
70 */
71 @Deprecated
72 public class MultiValueMap<K, V> extends AbstractMapDecorator<K, Object> implements MultiMap<K, V>, Serializable {
73
74 /**
75 * Inner class that provides a simple reflection factory.
76 *
77 * @param <T> the type of results supplied by this supplier.
78 */
79 private static final class ReflectionFactory<T extends Collection<?>> implements Factory<T>, Serializable {
80
81 /** Serialization version */
82 private static final long serialVersionUID = 2986114157496788874L;
83
84 private final Class<T> clazz;
85
86 ReflectionFactory(final Class<T> clazz) {
87 this.clazz = clazz;
88 }
89
90 @Override
91 public T create() {
92 try {
93 return clazz.getDeclaredConstructor().newInstance();
94 } catch (final Exception ex) {
95 throw new FunctorException("Cannot instantiate class: " + clazz, ex);
96 }
97 }
98
99 /**
100 * Deserializes an instance from an ObjectInputStream.
101 *
102 * @param in The source ObjectInputStream.
103 * @throws IOException Any of the usual Input/Output related exceptions.
104 * @throws ClassNotFoundException A class of a serialized object cannot be found.
105 */
106 private void readObject(final ObjectInputStream is) throws IOException, ClassNotFoundException {
107 is.defaultReadObject();
108 // ensure that the de-serialized class is a Collection, COLLECTIONS-580
109 if (clazz != null && !Collection.class.isAssignableFrom(clazz)) {
110 throw new UnsupportedOperationException();
111 }
112 }
113 }
114
115 /**
116 * Inner class that provides the values view.
117 */
118 private final class Values extends AbstractCollection<V> {
119 @Override
120 public void clear() {
121 MultiValueMap.this.clear();
122 }
123
124 @Override
125 public Iterator<V> iterator() {
126 final IteratorChain<V> chain = new IteratorChain<>();
127 for (final K k : keySet()) {
128 chain.addIterator(new ValuesIterator(k));
129 }
130 return chain;
131 }
132
133 @Override
134 public int size() {
135 return totalSize();
136 }
137 }
138 /**
139 * Inner class that provides the values iterator.
140 */
141 private final class ValuesIterator implements Iterator<V> {
142 private final Object key;
143 private final Collection<V> values;
144 private final Iterator<V> iterator;
145
146 ValuesIterator(final Object key) {
147 this.key = key;
148 this.values = getCollection(key);
149 this.iterator = values.iterator();
150 }
151
152 @Override
153 public boolean hasNext() {
154 return iterator.hasNext();
155 }
156
157 @Override
158 public V next() {
159 return iterator.next();
160 }
161
162 @Override
163 public void remove() {
164 iterator.remove();
165 if (values.isEmpty()) {
166 MultiValueMap.this.remove(key);
167 }
168 }
169 }
170
171 /** Serialization version */
172 private static final long serialVersionUID = -2214159910087182007L;
173
174 /**
175 * Creates a map which decorates the given {@code map} and
176 * maps keys to collections of type {@code collectionClass}.
177 *
178 * @param <K> the key type
179 * @param <V> the value type
180 * @param <C> the collection class type
181 * @param map the map to wrap
182 * @param collectionClass the type of the collection class
183 * @return a new multi-value map
184 * @since 4.0
185 */
186 public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
187 final Class<C> collectionClass) {
188 return new MultiValueMap<>(map, new ReflectionFactory<>(collectionClass));
189 }
190
191 /**
192 * Creates a map which decorates the given {@code map} and
193 * creates the value collections using the supplied {@code collectionFactory}.
194 *
195 * @param <K> the key type
196 * @param <V> the value type
197 * @param <C> the collection class type
198 * @param map the map to decorate
199 * @param collectionFactory the collection factory (must return a Collection object).
200 * @return a new multi-value map
201 * @since 4.0
202 */
203 public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map,
204 final Factory<C> collectionFactory) {
205 return new MultiValueMap<>(map, collectionFactory);
206 }
207
208 /**
209 * Creates a map which wraps the given map and
210 * maps keys to ArrayLists.
211 *
212 * @param <K> the key type
213 * @param <V> the value type
214 * @param map the map to wrap
215 * @return a new multi-value map
216 * @since 4.0
217 */
218 @SuppressWarnings({ "unchecked", "rawtypes" })
219 public static <K, V> MultiValueMap<K, V> multiValueMap(final Map<K, ? super Collection<V>> map) {
220 return MultiValueMap.<K, V, ArrayList>multiValueMap((Map<K, ? super Collection>) map, ArrayList.class);
221 }
222
223 /** The factory for creating value collections. */
224 private final Factory<? extends Collection<V>> collectionFactory;
225
226 /** The cached values. */
227 private transient Collection<V> valuesView;
228
229 /**
230 * Creates a MultiValueMap based on a {@code HashMap} and
231 * storing the multiple values in an {@code ArrayList}.
232 */
233 @SuppressWarnings({ "unchecked", "rawtypes" })
234 public MultiValueMap() {
235 this(new HashMap<>(), new ReflectionFactory(ArrayList.class));
236 }
237
238 /**
239 * Creates a MultiValueMap which decorates the given {@code map} and
240 * creates the value collections using the supplied {@code collectionFactory}.
241 *
242 * @param <C> the collection class type
243 * @param map the map to decorate
244 * @param collectionFactory the collection factory which must return a Collection instance
245 */
246 @SuppressWarnings("unchecked")
247 protected <C extends Collection<V>> MultiValueMap(final Map<K, ? super C> map,
248 final Factory<C> collectionFactory) {
249 super((Map<K, Object>) map);
250 if (collectionFactory == null) {
251 throw new IllegalArgumentException("The factory must not be null");
252 }
253 this.collectionFactory = collectionFactory;
254 }
255
256 /**
257 * Clear the map.
258 */
259 @Override
260 public void clear() {
261 // If you believe that you have GC issues here, try uncommenting this code
262 // Set pairs = getMap().entrySet();
263 // Iterator pairsIterator = pairs.iterator();
264 // while (pairsIterator.hasNext()) {
265 // Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
266 // Collection coll = (Collection) keyValuePair.getValue();
267 // coll.clear();
268 // }
269 decorated().clear();
270 }
271
272 /**
273 * Checks whether the map contains the value specified.
274 * <p>
275 * This checks all collections against all keys for the value, and thus could be slow.
276 * </p>
277 *
278 * @param value the value to search for
279 * @return true if the map contains the value
280 */
281 @Override
282 @SuppressWarnings("unchecked")
283 public boolean containsValue(final Object value) {
284 final Set<Map.Entry<K, Object>> pairs = decorated().entrySet();
285 if (pairs != null) {
286 for (final Map.Entry<K, Object> entry : pairs) {
287 if (((Collection<V>) entry.getValue()).contains(value)) {
288 return true;
289 }
290 }
291 }
292 return false;
293 }
294
295 /**
296 * Checks whether the collection at the specified key contains the value.
297 *
298 * @param key the key to search for
299 * @param value the value to search for
300 * @return true if the map contains the value
301 */
302 public boolean containsValue(final Object key, final Object value) {
303 final Collection<V> coll = getCollection(key);
304 if (coll == null) {
305 return false;
306 }
307 return coll.contains(value);
308 }
309
310 /**
311 * Creates a new instance of the map value Collection container
312 * using the factory.
313 * <p>
314 * This method can be overridden to perform your own processing
315 * instead of using the factory.
316 * </p>
317 *
318 * @param size the collection size that is about to be added
319 * @return the new collection
320 */
321 protected Collection<V> createCollection(final int size) {
322 return collectionFactory.get();
323 }
324
325 /**
326 * {@inheritDoc}
327 * <p>
328 * Note: the returned Entry objects will contain as value a {@link Collection}
329 * of all values that are mapped to the given key. To get a "flattened" version
330 * of all mappings contained in this map, use {@link #iterator()}.
331 * </p>
332 *
333 * @see #iterator()
334 */
335 @Override
336 public Set<Entry<K, Object>> entrySet() { // NOPMD
337 return super.entrySet();
338 }
339
340 /**
341 * Gets the collection mapped to the specified key.
342 * This method is a convenience method to typecast the result of {@code get(key)}.
343 *
344 * @param key the key to retrieve
345 * @return the collection mapped to the key, null if no mapping
346 */
347 @SuppressWarnings("unchecked")
348 public Collection<V> getCollection(final Object key) {
349 return (Collection<V>) decorated().get(key);
350 }
351
352 /**
353 * Gets an iterator for all mappings stored in this {@link MultiValueMap}.
354 * <p>
355 * The iterator will return multiple Entry objects with the same key
356 * if there are multiple values mapped to this key.
357 * </p>
358 * <p>
359 * Note: calling {@link java.util.Map.Entry#setValue(Object)} on any of the returned
360 * elements will result in a {@link UnsupportedOperationException}.
361 * </p>
362 *
363 * @return the iterator of all mappings in this map
364 * @since 4.0
365 */
366 public Iterator<Entry<K, V>> iterator() {
367 final Collection<K> allKeys = new ArrayList<>(keySet());
368 final Iterator<K> keyIterator = allKeys.iterator();
369
370 return new LazyIteratorChain<Entry<K, V>>() {
371 @Override
372 protected Iterator<? extends Entry<K, V>> nextIterator(final int count) {
373 if (!keyIterator.hasNext()) {
374 return null;
375 }
376 final K key = keyIterator.next();
377 final Transformer<V, Entry<K, V>> transformer = input -> new Entry<K, V>() {
378 @Override
379 public K getKey() {
380 return key;
381 }
382
383 @Override
384 public V getValue() {
385 return input;
386 }
387
388 @Override
389 public V setValue(final V value) {
390 throw new UnsupportedOperationException();
391 }
392 };
393 return new TransformIterator<>(new ValuesIterator(key), transformer);
394 }
395 };
396 }
397
398 /**
399 * Gets an iterator for the collection mapped to the specified key.
400 *
401 * @param key the key to get an iterator for
402 * @return the iterator of the collection at the key, empty iterator if key not in map
403 */
404 public Iterator<V> iterator(final Object key) {
405 if (!containsKey(key)) {
406 return EmptyIterator.<V>emptyIterator();
407 }
408 return new ValuesIterator(key);
409 }
410
411 /**
412 * Adds the value to the collection associated with the specified key.
413 * <p>
414 * Unlike a normal {@code Map} the previous value is not replaced.
415 * Instead, the new value is added to the collection stored against the key.
416 * </p>
417 *
418 * @param key the key to store against
419 * @param value the value to add to the collection at the key
420 * @return the value added if the map changed and null if the map did not change
421 */
422 @Override
423 @SuppressWarnings("unchecked")
424 public Object put(final K key, final Object value) {
425 boolean result = false;
426 Collection<V> coll = getCollection(key);
427 if (coll == null) {
428 coll = createCollection(1); // might produce a non-empty collection
429 coll.add((V) value);
430 if (!coll.isEmpty()) {
431 // only add if non-zero size to maintain class state
432 decorated().put(key, coll);
433 result = true; // map definitely changed
434 }
435 } else {
436 result = coll.add((V) value);
437 }
438 return result ? value : null;
439 }
440
441 /**
442 * Adds a collection of values to the collection associated with
443 * the specified key.
444 *
445 * @param key the key to store against
446 * @param values the values to add to the collection at the key, null ignored
447 * @return true if this map changed
448 */
449 public boolean putAll(final K key, final Collection<V> values) {
450 if (values == null || values.isEmpty()) {
451 return false;
452 }
453 boolean result = false;
454 Collection<V> coll = getCollection(key);
455 if (coll == null) {
456 coll = createCollection(values.size()); // might produce a non-empty collection
457 coll.addAll(values);
458 if (!coll.isEmpty()) {
459 // only add if non-zero size to maintain class state
460 decorated().put(key, coll);
461 result = true; // map definitely changed
462 }
463 } else {
464 result = coll.addAll(values);
465 }
466 return result;
467 }
468
469 /**
470 * Override superclass to ensure that MultiMap instances are
471 * correctly handled.
472 * <p>
473 * If you call this method with a normal map, each entry is
474 * added using {@code put(Object,Object)}.
475 * If you call this method with a multi map, each entry is
476 * added using {@code putAll(Object,Collection)}.
477 * </p>
478 *
479 * @param map the map to copy (either a normal or multi map)
480 */
481 @Override
482 @SuppressWarnings("unchecked")
483 public void putAll(final Map<? extends K, ?> map) {
484 if (map instanceof MultiMap) {
485 for (final Map.Entry<? extends K, Object> entry : ((MultiMap<? extends K, V>) map).entrySet()) {
486 putAll(entry.getKey(), (Collection<V>) entry.getValue());
487 }
488 } else {
489 for (final Map.Entry<? extends K, ?> entry : map.entrySet()) {
490 put(entry.getKey(), entry.getValue());
491 }
492 }
493 }
494
495 /**
496 * Deserializes the map in using a custom routine.
497 *
498 * @param in the input stream
499 * @throws IOException if an error occurs while reading from the stream
500 * @throws ClassNotFoundException if an object read from the stream cannot be loaded
501 * @since 4.0
502 */
503 @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect
504 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
505 in.defaultReadObject();
506 map = (Map<K, Object>) in.readObject(); // (1)
507 }
508
509 /**
510 * Removes a specific value from map.
511 * <p>
512 * The item is removed from the collection mapped to the specified key.
513 * Other values attached to that key are unaffected.
514 * </p>
515 * <p>
516 * If the last value for a key is removed, {@code null} will be returned
517 * from a subsequent {@code get(key)}.
518 * </p>
519 *
520 * @param key the key to remove from
521 * @param value the value to remove
522 * @return {@code true} if the mapping was removed, {@code false} otherwise
523 */
524 @Override
525 public boolean removeMapping(final Object key, final Object value) {
526 final Collection<V> valuesForKey = getCollection(key);
527 if (valuesForKey == null) {
528 return false;
529 }
530 final boolean removed = valuesForKey.remove(value);
531 if (!removed) {
532 return false;
533 }
534 if (valuesForKey.isEmpty()) {
535 remove(key);
536 }
537 return true;
538 }
539
540 /**
541 * Gets the size of the collection mapped to the specified key.
542 *
543 * @param key the key to get size for
544 * @return the size of the collection at the key, zero if key not in map
545 */
546 public int size(final Object key) {
547 final Collection<V> coll = getCollection(key);
548 if (coll == null) {
549 return 0;
550 }
551 return coll.size();
552 }
553
554 /**
555 * Gets the total size of the map by counting all the values.
556 *
557 * @return the total size of the map counting all values
558 */
559 public int totalSize() {
560 int total = 0;
561 for (final Object v : decorated().values()) {
562 total += CollectionUtils.size(v);
563 }
564 return total;
565 }
566
567 /**
568 * Gets a collection containing all the values in the map.
569 * <p>
570 * This returns a collection containing the combination of values from all keys.
571 * </p>
572 *
573 * @return a collection view of the values contained in this map
574 */
575 @Override
576 @SuppressWarnings("unchecked")
577 public Collection<Object> values() {
578 final Collection<V> vs = valuesView;
579 return (Collection<Object>) (vs != null ? vs : (valuesView = new Values()));
580 }
581
582 /**
583 * Serializes this object to an ObjectOutputStream.
584 *
585 * @param out the target ObjectOutputStream.
586 * @throws IOException thrown when an I/O errors occur writing to the target stream.
587 * @since 4.0
588 */
589 private void writeObject(final ObjectOutputStream out) throws IOException {
590 out.defaultWriteObject();
591 out.writeObject(map);
592 }
593
594 }