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