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.Serializable;
20 import java.util.Arrays;
21 import java.util.Collection;
22 import java.util.Map;
23 import java.util.Set;
24
25 import org.apache.commons.collections4.CollectionUtils;
26 import org.apache.commons.collections4.collection.CompositeCollection;
27 import org.apache.commons.collections4.set.CompositeSet;
28
29 /**
30 * Decorates a map of other maps to provide a single unified view.
31 * <p>
32 * Changes made to this map will actually be made on the decorated map.
33 * Add and remove operations require the use of a pluggable strategy. If no
34 * strategy is provided then add and remove are unsupported.
35 * </p>
36 * <p>
37 * <strong>Note that CompositeMap is not synchronized and is not thread-safe.</strong>
38 * If you wish to use this map from multiple threads concurrently, you must use
39 * appropriate synchronization. The simplest approach is to wrap this map
40 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
41 * exceptions when accessed by concurrent threads without synchronization.
42 * </p>
43 *
44 * @param <K> The type of the keys in this map
45 * @param <V> The type of the values in this map
46 * @since 3.0
47 */
48 public class CompositeMap<K, V> extends AbstractIterableMap<K, V> implements Serializable {
49
50 /**
51 * This interface allows definition for all of the indeterminate
52 * mutators in a CompositeMap, as well as providing a hook for
53 * callbacks on key collisions.
54 *
55 * @param <K> The type of the keys in the map
56 * @param <V> The type of the values in the map
57 */
58 public interface MapMutator<K, V> extends Serializable {
59
60 /**
61 * Called when the CompositeMap.put() method is invoked.
62 *
63 * @param map The CompositeMap which is being modified
64 * @param composited array of Maps in the CompositeMap being modified
65 * @param key key with which the specified value is to be associated.
66 * @param value value to be associated with the specified key.
67 * @return previous value associated with specified key, or {@code null}
68 * if there was no mapping for key. A {@code null} return can
69 * also indicate that the map previously associated {@code null}
70 * with the specified key, if the implementation supports
71 * {@code null} values.
72 *
73 * @throws UnsupportedOperationException if not defined
74 * @throws ClassCastException if the class of the specified key or value
75 * prevents it from being stored in this map.
76 * @throws IllegalArgumentException if some aspect of this key or value
77 * prevents it from being stored in this map.
78 * @throws NullPointerException this map does not permit {@code null}
79 * keys or values, and the specified key or value is
80 * {@code null}.
81 */
82 V put(CompositeMap<K, V> map, Map<K, V>[] composited, K key, V value);
83
84 /**
85 * Called when the CompositeMap.putAll() method is invoked.
86 *
87 * @param map The CompositeMap which is being modified
88 * @param composited array of Maps in the CompositeMap being modified
89 * @param mapToAdd Mappings to be stored in this CompositeMap
90 * @throws UnsupportedOperationException if not defined
91 * @throws ClassCastException if the class of the specified key or value
92 * prevents it from being stored in this map.
93 * @throws IllegalArgumentException if some aspect of this key or value
94 * prevents it from being stored in this map.
95 * @throws NullPointerException this map does not permit {@code null}
96 * keys or values, and the specified key or value is
97 * {@code null}.
98 */
99 void putAll(CompositeMap<K, V> map, Map<K, V>[] composited,
100 Map<? extends K, ? extends V> mapToAdd);
101
102 /**
103 * Called when adding a new Composited Map results in a
104 * key collision.
105 *
106 * @param composite The CompositeMap with the collision
107 * @param existing The Map already in the composite which contains the
108 * offending key
109 * @param added The Map being added
110 * @param intersect The intersection of the keysets of the existing and added maps
111 */
112 void resolveCollision(CompositeMap<K, V> composite, Map<K, V> existing,
113 Map<K, V> added, Collection<K> intersect);
114 }
115
116 @SuppressWarnings("rawtypes")
117 private static final Map[] EMPTY_MAP_ARRAY = {};
118
119 /** Serialization version */
120 private static final long serialVersionUID = -6096931280583808322L;
121
122 /** Array of all maps in the composite */
123 private Map<K, V>[] composite;
124
125 /** Handle mutation operations */
126 private MapMutator<K, V> mutator;
127
128 /**
129 * Create a new, empty, CompositeMap.
130 */
131 @SuppressWarnings("unchecked")
132 public CompositeMap() {
133 this(new Map[] {}, null);
134 }
135
136 /**
137 * Create a new CompositeMap which composites all of the Map instances in the
138 * argument. It copies the argument array, it does not use it directly.
139 *
140 * @param composite The Maps to be composited
141 * @throws IllegalArgumentException if there is a key collision
142 */
143 public CompositeMap(final Map<K, V>... composite) {
144 this(composite, null);
145 }
146
147 /**
148 * Create a new CompositeMap with two composited Map instances.
149 *
150 * @param one The first Map to be composited
151 * @param two The second Map to be composited
152 * @throws IllegalArgumentException if there is a key collision
153 */
154 @SuppressWarnings("unchecked")
155 public CompositeMap(final Map<K, V> one, final Map<K, V> two) {
156 this(new Map[] { one, two }, null);
157 }
158
159 /**
160 * Create a new CompositeMap with two composited Map instances.
161 *
162 * @param one The first Map to be composited
163 * @param two The second Map to be composited
164 * @param mutator MapMutator to be used for mutation operations
165 */
166 @SuppressWarnings("unchecked")
167 public CompositeMap(final Map<K, V> one, final Map<K, V> two, final MapMutator<K, V> mutator) {
168 this(new Map[] { one, two }, mutator);
169 }
170
171 /**
172 * Create a new CompositeMap which composites all of the Map instances in the
173 * argument. It copies the argument array, it does not use it directly.
174 *
175 * @param composite Maps to be composited
176 * @param mutator MapMutator to be used for mutation operations
177 */
178 @SuppressWarnings("unchecked")
179 public CompositeMap(final Map<K, V>[] composite, final MapMutator<K, V> mutator) {
180 this.mutator = mutator;
181 this.composite = EMPTY_MAP_ARRAY;
182 for (int i = composite.length - 1; i >= 0; --i) {
183 this.addComposited(composite[i]);
184 }
185 }
186
187 /**
188 * Add an additional Map to the composite.
189 *
190 * @param map The Map to be added to the composite
191 * @throws IllegalArgumentException if there is a key collision and there is no
192 * MapMutator set to handle it.
193 */
194 public synchronized void addComposited(final Map<K, V> map) throws IllegalArgumentException {
195 if (map != null) {
196 for (int i = composite.length - 1; i >= 0; --i) {
197 final Collection<K> intersect = CollectionUtils.intersection(composite[i].keySet(), map.keySet());
198 if (!intersect.isEmpty()) {
199 if (mutator == null) {
200 throw new IllegalArgumentException("Key collision adding Map to CompositeMap");
201 }
202 mutator.resolveCollision(this, composite[i], map, intersect);
203 }
204 }
205 final Map<K, V>[] temp = Arrays.copyOf(composite, composite.length + 1);
206 temp[temp.length - 1] = map;
207 composite = temp;
208 }
209 }
210
211 /**
212 * Calls {@code clear()} on all composited Maps.
213 *
214 * @throws UnsupportedOperationException if any of the composited Maps do not support clear()
215 */
216 @Override
217 public void clear() {
218 for (int i = composite.length - 1; i >= 0; --i) {
219 composite[i].clear();
220 }
221 }
222
223 /**
224 * Returns {@code true} if this map contains a mapping for the specified
225 * key. More formally, returns {@code true} if and only if
226 * this map contains at a mapping for a key {@code k} such that
227 * {@code (key==null ? k==null : key.equals(k))}. (There can be
228 * at most one such mapping.)
229 *
230 * @param key key whose presence in this map is to be tested.
231 * @return {@code true} if this map contains a mapping for the specified
232 * key.
233 *
234 * @throws ClassCastException if the key is of an inappropriate type for
235 * this map (optional).
236 * @throws NullPointerException if the key is {@code null} and this map
237 * does not permit {@code null} keys (optional).
238 */
239 @Override
240 public boolean containsKey(final Object key) {
241 for (int i = composite.length - 1; i >= 0; --i) {
242 if (composite[i].containsKey(key)) {
243 return true;
244 }
245 }
246 return false;
247 }
248
249 /**
250 * Returns {@code true} if this map maps one or more keys to the
251 * specified value. More formally, returns {@code true} if and only if
252 * this map contains at least one mapping to a value {@code v} such that
253 * {@code (value==null ? v==null : value.equals(v))}. This operation
254 * will probably require time linear in the map size for most
255 * implementations of the {@code Map} interface.
256 *
257 * @param value value whose presence in this map is to be tested.
258 * @return {@code true} if this map maps one or more keys to the
259 * specified value.
260 * @throws ClassCastException if the value is of an inappropriate type for
261 * this map (optional).
262 * @throws NullPointerException if the value is {@code null} and this map
263 * does not permit {@code null} values (optional).
264 */
265 @Override
266 public boolean containsValue(final Object value) {
267 for (int i = composite.length - 1; i >= 0; --i) {
268 if (composite[i].containsValue(value)) {
269 return true;
270 }
271 }
272 return false;
273 }
274
275 /**
276 * Returns a set view of the mappings contained in this map. Each element
277 * in the returned set is a {@code Map.Entry}. The set is backed by the
278 * map, so changes to the map are reflected in the set, and vice-versa.
279 * If the map is modified while an iteration over the set is in progress,
280 * the results of the iteration are undefined. The set supports element
281 * removal, which removes the corresponding mapping from the map, via the
282 * {@code Iterator.remove}, {@code Set.remove}, {@code removeAll},
283 * {@code retainAll} and {@code clear} operations. It does not support
284 * the {@code add} or {@code addAll} operations.
285 * <p>
286 * This implementation returns a {@code CompositeSet} which
287 * composites the entry sets from all of the composited maps.
288 *
289 * @see CompositeSet
290 * @return A set view of the mappings contained in this map.
291 */
292 @Override
293 public Set<Map.Entry<K, V>> entrySet() {
294 final CompositeSet<Map.Entry<K, V>> entries = new CompositeSet<>();
295 for (int i = composite.length - 1; i >= 0; --i) {
296 entries.addComposited(composite[i].entrySet());
297 }
298 return entries;
299 }
300
301 /**
302 * Checks if this Map equals another as per the Map specification.
303 *
304 * @param obj The object to compare to
305 * @return true if the maps are equal
306 */
307 @Override
308 public boolean equals(final Object obj) {
309 if (obj instanceof Map) {
310 final Map<?, ?> map = (Map<?, ?>) obj;
311 return this.entrySet().equals(map.entrySet());
312 }
313 return false;
314 }
315
316 /**
317 * Gets the value to which this map maps the specified key. Returns
318 * {@code null} if the map contains no mapping for this key. A return
319 * value of {@code null} does not <em>necessarily</em> indicate that the
320 * map contains no mapping for the key; it's also possible that the map
321 * explicitly maps the key to {@code null}. The {@code containsKey}
322 * operation may be used to distinguish these two cases.
323 *
324 * <p>More formally, if this map contains a mapping from a key
325 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
326 * key.equals(k))}, then this method returns {@code v}; otherwise
327 * it returns {@code null}. (There can be at most one such mapping.)
328 *
329 * @param key key whose associated value is to be returned.
330 * @return The value to which this map maps the specified key, or
331 * {@code null} if the map contains no mapping for this key.
332 *
333 * @throws ClassCastException if the key is of an inappropriate type for
334 * this map (optional).
335 * @throws NullPointerException key is {@code null} and this map does
336 * not permit {@code null} keys (optional).
337 *
338 * @see #containsKey(Object)
339 */
340 @Override
341 public V get(final Object key) {
342 for (int i = composite.length - 1; i >= 0; --i) {
343 if (composite[i].containsKey(key)) {
344 return composite[i].get(key);
345 }
346 }
347 return null;
348 }
349
350 /**
351 * Gets a hash code for the Map as per the Map specification.
352 * {@inheritDoc}
353 */
354 @Override
355 public int hashCode() {
356 int code = 0;
357 for (final Map.Entry<K, V> entry : entrySet()) {
358 code += entry.hashCode();
359 }
360 return code;
361 }
362
363 /**
364 * Returns {@code true} if this map contains no key-value mappings.
365 *
366 * @return {@code true} if this map contains no key-value mappings.
367 */
368 @Override
369 public boolean isEmpty() {
370 for (int i = composite.length - 1; i >= 0; --i) {
371 if (!composite[i].isEmpty()) {
372 return false;
373 }
374 }
375 return true;
376 }
377
378 /**
379 * Returns a set view of the keys contained in this map. The set is
380 * backed by the map, so changes to the map are reflected in the set, and
381 * vice-versa. If the map is modified while an iteration over the set is
382 * in progress, the results of the iteration are undefined. The set
383 * supports element removal, which removes the corresponding mapping from
384 * the map, via the {@code Iterator.remove}, {@code Set.remove},
385 * {@code removeAll} {@code retainAll}, and {@code clear} operations.
386 * It does not support the add or {@code addAll} operations.
387 * <p>
388 * This implementation returns a {@code CompositeSet} which
389 * composites the key sets from all of the composited maps.
390 * </p>
391 *
392 * @return A set view of the keys contained in this map.
393 */
394 @Override
395 public Set<K> keySet() {
396 final CompositeSet<K> keys = new CompositeSet<>();
397 for (int i = composite.length - 1; i >= 0; --i) {
398 keys.addComposited(composite[i].keySet());
399 }
400 return keys;
401 }
402
403 /**
404 * Associates the specified value with the specified key in this map
405 * (optional operation). If the map previously contained a mapping for
406 * this key, the old value is replaced by the specified value. (A map
407 * {@code m} is said to contain a mapping for a key {@code k} if and only
408 * if {@link #containsKey(Object) m.containsKey(k)} would return
409 * {@code true}.))
410 *
411 * @param key key with which the specified value is to be associated.
412 * @param value value to be associated with the specified key.
413 * @return previous value associated with specified key, or {@code null}
414 * if there was no mapping for key. A {@code null} return can
415 * also indicate that the map previously associated {@code null}
416 * with the specified key, if the implementation supports
417 * {@code null} values.
418 *
419 * @throws UnsupportedOperationException if no MapMutator has been specified
420 * @throws ClassCastException if the class of the specified key or value
421 * prevents it from being stored in this map.
422 * @throws IllegalArgumentException if some aspect of this key or value
423 * prevents it from being stored in this map.
424 * @throws NullPointerException this map does not permit {@code null}
425 * keys or values, and the specified key or value is
426 * {@code null}.
427 */
428 @Override
429 public V put(final K key, final V value) {
430 if (mutator == null) {
431 throw new UnsupportedOperationException("No mutator specified");
432 }
433 return mutator.put(this, composite, key, value);
434 }
435
436 /**
437 * Copies all of the mappings from the specified map to this map
438 * (optional operation). The effect of this call is equivalent to that
439 * of calling {@link #put(Object,Object) put(k, v)} on this map once
440 * for each mapping from key {@code k} to value {@code v} in the
441 * specified map. The behavior of this operation is unspecified if the
442 * specified map is modified while the operation is in progress.
443 *
444 * @param map Mappings to be stored in this map.
445 * @throws UnsupportedOperationException if the {@code putAll} method is
446 * not supported by this map.
447 *
448 * @throws ClassCastException if the class of a key or value in the
449 * specified map prevents it from being stored in this map.
450 *
451 * @throws IllegalArgumentException some aspect of a key or value in the
452 * specified map prevents it from being stored in this map.
453 * @throws NullPointerException the specified map is {@code null}, or if
454 * this map does not permit {@code null} keys or values, and the
455 * specified map contains {@code null} keys or values.
456 */
457 @Override
458 public void putAll(final Map<? extends K, ? extends V> map) {
459 if (mutator == null) {
460 throw new UnsupportedOperationException("No mutator specified");
461 }
462 mutator.putAll(this, composite, map);
463 }
464
465 /**
466 * Removes the mapping for this key from this map if it is present
467 * (optional operation). More formally, if this map contains a mapping
468 * from key {@code k} to value {@code v} such that
469 * {@code (key==null ? k==null : key.equals(k))}, that mapping
470 * is removed. (The map can contain at most one such mapping.)
471 *
472 * <p>Returns the value to which the map previously associated the key, or
473 * {@code null} if the map contained no mapping for this key. (A
474 * {@code null} return can also indicate that the map previously
475 * associated {@code null} with the specified key if the implementation
476 * supports {@code null} values.) The map will not contain a mapping for
477 * the specified key once the call returns.
478 *
479 * @param key key whose mapping is to be removed from the map.
480 * @return previous value associated with specified key, or {@code null}
481 * if there was no mapping for key.
482 *
483 * @throws ClassCastException if the key is of an inappropriate type for
484 * the composited map (optional).
485 * @throws NullPointerException if the key is {@code null} and the composited map
486 * does not permit {@code null} keys (optional).
487 * @throws UnsupportedOperationException if the {@code remove} method is
488 * not supported by the composited map containing the key
489 */
490 @Override
491 public V remove(final Object key) {
492 for (int i = composite.length - 1; i >= 0; --i) {
493 if (composite[i].containsKey(key)) {
494 return composite[i].remove(key);
495 }
496 }
497 return null;
498 }
499
500 /**
501 * Remove a Map from the composite.
502 *
503 * @param map The Map to be removed from the composite
504 * @return The removed Map or {@code null} if map is not in the composite
505 */
506 @SuppressWarnings("unchecked")
507 public synchronized Map<K, V> removeComposited(final Map<K, V> map) {
508 final int size = composite.length;
509 for (int i = 0; i < size; ++i) {
510 if (composite[i].equals(map)) {
511 final Map<K, V>[] temp = new Map[size - 1];
512 System.arraycopy(composite, 0, temp, 0, i);
513 System.arraycopy(composite, i + 1, temp, i, size - i - 1);
514 composite = temp;
515 return map;
516 }
517 }
518 return null;
519 }
520
521 /**
522 * Specify the MapMutator to be used by mutation operations.
523 *
524 * @param mutator The MapMutator to be used for mutation delegation
525 */
526 public void setMutator(final MapMutator<K, V> mutator) {
527 this.mutator = mutator;
528 }
529
530 /**
531 * Returns the number of key-value mappings in this map. If the
532 * map contains more than {@code Integer.MAX_VALUE} elements, returns
533 * {@code Integer.MAX_VALUE}.
534 *
535 * @return The number of key-value mappings in this map.
536 */
537 @Override
538 public int size() {
539 long size = 0;
540 for (int i = composite.length - 1; i >= 0; --i) {
541 size += composite[i].size();
542 }
543 return (int) Math.min(size, Integer.MAX_VALUE);
544 }
545
546 /**
547 * Returns a collection view of the values contained in this map. The
548 * collection is backed by the map, so changes to the map are reflected in
549 * the collection, and vice-versa. If the map is modified while an
550 * iteration over the collection is in progress, the results of the
551 * iteration are undefined. The collection supports element removal,
552 * which removes the corresponding mapping from the map, via the
553 * {@code Iterator.remove}, {@code Collection.remove},
554 * {@code removeAll}, {@code retainAll} and {@code clear} operations.
555 * It does not support the add or {@code addAll} operations.
556 *
557 * @return A collection view of the values contained in this map.
558 */
559 @Override
560 public Collection<V> values() {
561 final CompositeCollection<V> values = new CompositeCollection<>();
562 for (int i = composite.length - 1; i >= 0; --i) {
563 values.addComposited(composite[i].values());
564 }
565 return values;
566 }
567 }