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