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