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