001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.map;
018
019 import java.util.Collection;
020 import java.util.Iterator;
021 import java.util.Map;
022 import java.util.Set;
023
024 import org.apache.commons.collections.CollectionUtils;
025 import org.apache.commons.collections.collection.CompositeCollection;
026 import org.apache.commons.collections.set.CompositeSet;
027
028 /**
029 * Decorates a map of other maps to provide a single unified view.
030 * <p>
031 * Changes made to this map will actually be made on the decorated map.
032 * Add and remove operations require the use of a pluggable strategy. If no
033 * strategy is provided then add and remove are unsupported.
034 * <p>
035 * <strong>Note that CompositeMap is not synchronized and is not thread-safe.</strong>
036 * If you wish to use this map from multiple threads concurrently, you must use
037 * appropriate synchronization. The simplest approach is to wrap this map
038 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
039 * exceptions when accessed by concurrent threads without synchronization.
040 *
041 * @since Commons Collections 3.0
042 * @version $Revision: 647116 $ $Date: 2008-04-11 12:23:08 +0100 (Fri, 11 Apr 2008) $
043 *
044 * @author Brian McCallister
045 */
046 public class CompositeMap implements Map {
047
048 /** Array of all maps in the composite */
049 private Map[] composite;
050
051 /** Handle mutation operations */
052 private MapMutator mutator;
053
054 /**
055 * Create a new, empty, CompositeMap.
056 */
057 public CompositeMap() {
058 this(new Map[]{}, null);
059 }
060
061 /**
062 * Create a new CompositeMap with two composited Map instances.
063 *
064 * @param one the first Map to be composited
065 * @param two the second Map to be composited
066 * @throws IllegalArgumentException if there is a key collision
067 */
068 public CompositeMap(Map one, Map two) {
069 this(new Map[]{one, two}, null);
070 }
071
072 /**
073 * Create a new CompositeMap with two composited Map instances.
074 *
075 * @param one the first Map to be composited
076 * @param two the second Map to be composited
077 * @param mutator MapMutator to be used for mutation operations
078 */
079 public CompositeMap(Map one, Map two, MapMutator mutator) {
080 this(new Map[]{one, two}, mutator);
081 }
082
083 /**
084 * Create a new CompositeMap which composites all of the Map instances in the
085 * argument. It copies the argument array, it does not use it directly.
086 *
087 * @param composite the Maps to be composited
088 * @throws IllegalArgumentException if there is a key collision
089 */
090 public CompositeMap(Map[] composite) {
091 this(composite, null);
092 }
093
094 /**
095 * Create a new CompositeMap which composites all of the Map instances in the
096 * argument. It copies the argument array, it does not use it directly.
097 *
098 * @param composite Maps to be composited
099 * @param mutator MapMutator to be used for mutation operations
100 */
101 public CompositeMap(Map[] composite, MapMutator mutator) {
102 this.mutator = mutator;
103 this.composite = new Map[0];
104 for (int i = composite.length - 1; i >= 0; --i) {
105 this.addComposited(composite[i]);
106 }
107 }
108
109 //-----------------------------------------------------------------------
110 /**
111 * Specify the MapMutator to be used by mutation operations.
112 *
113 * @param mutator the MapMutator to be used for mutation delegation
114 */
115 public void setMutator(MapMutator mutator) {
116 this.mutator = mutator;
117 }
118
119 /**
120 * Add an additional Map to the composite.
121 *
122 * @param map the Map to be added to the composite
123 * @throws IllegalArgumentException if there is a key collision and there is no
124 * MapMutator set to handle it.
125 */
126 public synchronized void addComposited(Map map) throws IllegalArgumentException {
127 for (int i = composite.length - 1; i >= 0; --i) {
128 Collection intersect = CollectionUtils.intersection(this.composite[i].keySet(), map.keySet());
129 if (intersect.size() != 0) {
130 if (this.mutator == null) {
131 throw new IllegalArgumentException("Key collision adding Map to CompositeMap");
132 }
133 else {
134 this.mutator.resolveCollision(this, this.composite[i], map, intersect);
135 }
136 }
137 }
138 Map[] temp = new Map[this.composite.length + 1];
139 System.arraycopy(this.composite, 0, temp, 0, this.composite.length);
140 temp[temp.length - 1] = map;
141 this.composite = temp;
142 }
143
144 /**
145 * Remove a Map from the composite.
146 *
147 * @param map the Map to be removed from the composite
148 * @return The removed Map or <code>null</code> if map is not in the composite
149 */
150 public synchronized Map removeComposited(Map map) {
151 int size = this.composite.length;
152 for (int i = 0; i < size; ++i) {
153 if (this.composite[i].equals(map)) {
154 Map[] temp = new Map[size - 1];
155 System.arraycopy(this.composite, 0, temp, 0, i);
156 System.arraycopy(this.composite, i + 1, temp, i, size - i - 1);
157 this.composite = temp;
158 return map;
159 }
160 }
161 return null;
162 }
163
164 //-----------------------------------------------------------------------
165 /**
166 * Calls <code>clear()</code> on all composited Maps.
167 *
168 * @throws UnsupportedOperationException if any of the composited Maps do not support clear()
169 */
170 public void clear() {
171 for (int i = this.composite.length - 1; i >= 0; --i) {
172 this.composite[i].clear();
173 }
174 }
175
176 /**
177 * Returns <tt>true</tt> if this map contains a mapping for the specified
178 * key. More formally, returns <tt>true</tt> if and only if
179 * this map contains at a mapping for a key <tt>k</tt> such that
180 * <tt>(key==null ? k==null : key.equals(k))</tt>. (There can be
181 * at most one such mapping.)
182 *
183 * @param key key whose presence in this map is to be tested.
184 * @return <tt>true</tt> if this map contains a mapping for the specified
185 * key.
186 *
187 * @throws ClassCastException if the key is of an inappropriate type for
188 * this map (optional).
189 * @throws NullPointerException if the key is <tt>null</tt> and this map
190 * does not not permit <tt>null</tt> keys (optional).
191 */
192 public boolean containsKey(Object key) {
193 for (int i = this.composite.length - 1; i >= 0; --i) {
194 if (this.composite[i].containsKey(key)) {
195 return true;
196 }
197 }
198 return false;
199 }
200
201 /**
202 * Returns <tt>true</tt> if this map maps one or more keys to the
203 * specified value. More formally, returns <tt>true</tt> if and only if
204 * this map contains at least one mapping to a value <tt>v</tt> such that
205 * <tt>(value==null ? v==null : value.equals(v))</tt>. This operation
206 * will probably require time linear in the map size for most
207 * implementations of the <tt>Map</tt> interface.
208 *
209 * @param value value whose presence in this map is to be tested.
210 * @return <tt>true</tt> if this map maps one or more keys to the
211 * specified value.
212 * @throws ClassCastException if the value is of an inappropriate type for
213 * this map (optional).
214 * @throws NullPointerException if the value is <tt>null</tt> and this map
215 * does not not permit <tt>null</tt> values (optional).
216 */
217 public boolean containsValue(Object value) {
218 for (int i = this.composite.length - 1; i >= 0; --i) {
219 if (this.composite[i].containsValue(value)) {
220 return true;
221 }
222 }
223 return false;
224 }
225
226 /**
227 * Returns a set view of the mappings contained in this map. Each element
228 * in the returned set is a <code>Map.Entry</code>. The set is backed by the
229 * map, so changes to the map are reflected in the set, and vice-versa.
230 * If the map is modified while an iteration over the set is in progress,
231 * the results of the iteration are undefined. The set supports element
232 * removal, which removes the corresponding mapping from the map, via the
233 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
234 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not support
235 * the <tt>add</tt> or <tt>addAll</tt> operations.
236 * <p>
237 * This implementation returns a <code>CompositeSet</code> which
238 * composites the entry sets from all of the composited maps.
239 *
240 * @see CompositeSet
241 * @return a set view of the mappings contained in this map.
242 */
243 public Set entrySet() {
244 CompositeSet entries = new CompositeSet();
245 for (int i = this.composite.length - 1; i >= 0; --i) {
246 entries.addComposited(this.composite[i].entrySet());
247 }
248 return entries;
249 }
250
251 /**
252 * Returns the value to which this map maps the specified key. Returns
253 * <tt>null</tt> if the map contains no mapping for this key. A return
254 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
255 * map contains no mapping for the key; it's also possible that the map
256 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
257 * operation may be used to distinguish these two cases.
258 *
259 * <p>More formally, if this map contains a mapping from a key
260 * <tt>k</tt> to a value <tt>v</tt> such that <tt>(key==null ? k==null :
261 * key.equals(k))</tt>, then this method returns <tt>v</tt>; otherwise
262 * it returns <tt>null</tt>. (There can be at most one such mapping.)
263 *
264 * @param key key whose associated value is to be returned.
265 * @return the value to which this map maps the specified key, or
266 * <tt>null</tt> if the map contains no mapping for this key.
267 *
268 * @throws ClassCastException if the key is of an inappropriate type for
269 * this map (optional).
270 * @throws NullPointerException key is <tt>null</tt> and this map does not
271 * not permit <tt>null</tt> keys (optional).
272 *
273 * @see #containsKey(Object)
274 */
275 public Object get(Object key) {
276 for (int i = this.composite.length - 1; i >= 0; --i) {
277 if (this.composite[i].containsKey(key)) {
278 return this.composite[i].get(key);
279 }
280 }
281 return null;
282 }
283
284 /**
285 * Returns <tt>true</tt> if this map contains no key-value mappings.
286 *
287 * @return <tt>true</tt> if this map contains no key-value mappings.
288 */
289 public boolean isEmpty() {
290 for (int i = this.composite.length - 1; i >= 0; --i) {
291 if (!this.composite[i].isEmpty()) {
292 return false;
293 }
294 }
295 return true;
296 }
297
298 /**
299 * Returns a set view of the keys contained in this map. The set is
300 * backed by the map, so changes to the map are reflected in the set, and
301 * vice-versa. If the map is modified while an iteration over the set is
302 * in progress, the results of the iteration are undefined. The set
303 * supports element removal, which removes the corresponding mapping from
304 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
305 * <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt> operations.
306 * It does not support the add or <tt>addAll</tt> operations.
307 * <p>
308 * This implementation returns a <code>CompositeSet</code> which
309 * composites the key sets from all of the composited maps.
310 *
311 * @return a set view of the keys contained in this map.
312 */
313 public Set keySet() {
314 CompositeSet keys = new CompositeSet();
315 for (int i = this.composite.length - 1; i >= 0; --i) {
316 keys.addComposited(this.composite[i].keySet());
317 }
318 return keys;
319 }
320
321 /**
322 * Associates the specified value with the specified key in this map
323 * (optional operation). If the map previously contained a mapping for
324 * this key, the old value is replaced by the specified value. (A map
325 * <tt>m</tt> is said to contain a mapping for a key <tt>k</tt> if and only
326 * if {@link #containsKey(Object) m.containsKey(k)} would return
327 * <tt>true</tt>.))
328 *
329 * @param key key with which the specified value is to be associated.
330 * @param value value to be associated with the specified key.
331 * @return previous value associated with specified key, or <tt>null</tt>
332 * if there was no mapping for key. A <tt>null</tt> return can
333 * also indicate that the map previously associated <tt>null</tt>
334 * with the specified key, if the implementation supports
335 * <tt>null</tt> values.
336 *
337 * @throws UnsupportedOperationException if no MapMutator has been specified
338 * @throws ClassCastException if the class of the specified key or value
339 * prevents it from being stored in this map.
340 * @throws IllegalArgumentException if some aspect of this key or value
341 * prevents it from being stored in this map.
342 * @throws NullPointerException this map does not permit <tt>null</tt>
343 * keys or values, and the specified key or value is
344 * <tt>null</tt>.
345 */
346 public Object put(Object key, Object value) {
347 if (this.mutator == null) {
348 throw new UnsupportedOperationException("No mutator specified");
349 }
350 return this.mutator.put(this, this.composite, key, value);
351 }
352
353 /**
354 * Copies all of the mappings from the specified map to this map
355 * (optional operation). The effect of this call is equivalent to that
356 * of calling {@link #put(Object,Object) put(k, v)} on this map once
357 * for each mapping from key <tt>k</tt> to value <tt>v</tt> in the
358 * specified map. The behavior of this operation is unspecified if the
359 * specified map is modified while the operation is in progress.
360 *
361 * @param map Mappings to be stored in this map.
362 *
363 * @throws UnsupportedOperationException if the <tt>putAll</tt> method is
364 * not supported by this map.
365 *
366 * @throws ClassCastException if the class of a key or value in the
367 * specified map prevents it from being stored in this map.
368 *
369 * @throws IllegalArgumentException some aspect of a key or value in the
370 * specified map prevents it from being stored in this map.
371 * @throws NullPointerException the specified map is <tt>null</tt>, or if
372 * this map does not permit <tt>null</tt> keys or values, and the
373 * specified map contains <tt>null</tt> keys or values.
374 */
375 public void putAll(Map map) {
376 if (this.mutator == null) {
377 throw new UnsupportedOperationException("No mutator specified");
378 }
379 this.mutator.putAll(this, this.composite, map);
380 }
381
382 /**
383 * Removes the mapping for this key from this map if it is present
384 * (optional operation). More formally, if this map contains a mapping
385 * from key <tt>k</tt> to value <tt>v</tt> such that
386 * <code>(key==null ? k==null : key.equals(k))</code>, that mapping
387 * is removed. (The map can contain at most one such mapping.)
388 *
389 * <p>Returns the value to which the map previously associated the key, or
390 * <tt>null</tt> if the map contained no mapping for this key. (A
391 * <tt>null</tt> return can also indicate that the map previously
392 * associated <tt>null</tt> with the specified key if the implementation
393 * supports <tt>null</tt> values.) The map will not contain a mapping for
394 * the specified key once the call returns.
395 *
396 * @param key key whose mapping is to be removed from the map.
397 * @return previous value associated with specified key, or <tt>null</tt>
398 * if there was no mapping for key.
399 *
400 * @throws ClassCastException if the key is of an inappropriate type for
401 * the composited map (optional).
402 * @throws NullPointerException if the key is <tt>null</tt> and the composited map
403 * does not not permit <tt>null</tt> keys (optional).
404 * @throws UnsupportedOperationException if the <tt>remove</tt> method is
405 * not supported by the composited map containing the key
406 */
407 public Object remove(Object key) {
408 for (int i = this.composite.length - 1; i >= 0; --i) {
409 if (this.composite[i].containsKey(key)) {
410 return this.composite[i].remove(key);
411 }
412 }
413 return null;
414 }
415
416 /**
417 * Returns the number of key-value mappings in this map. If the
418 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
419 * <tt>Integer.MAX_VALUE</tt>.
420 *
421 * @return the number of key-value mappings in this map.
422 */
423 public int size() {
424 int size = 0;
425 for (int i = this.composite.length - 1; i >= 0; --i) {
426 size += this.composite[i].size();
427 }
428 return size;
429 }
430
431 /**
432 * Returns a collection view of the values contained in this map. The
433 * collection is backed by the map, so changes to the map are reflected in
434 * the collection, and vice-versa. If the map is modified while an
435 * iteration over the collection is in progress, the results of the
436 * iteration are undefined. The collection supports element removal,
437 * which removes the corresponding mapping from the map, via the
438 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
439 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> operations.
440 * It does not support the add or <tt>addAll</tt> operations.
441 *
442 * @return a collection view of the values contained in this map.
443 */
444 public Collection values() {
445 CompositeCollection keys = new CompositeCollection();
446 for (int i = this.composite.length - 1; i >= 0; --i) {
447 keys.addComposited(this.composite[i].values());
448 }
449 return keys;
450 }
451
452 /**
453 * Checks if this Map equals another as per the Map specification.
454 *
455 * @param obj the object to compare to
456 * @return true if the maps are equal
457 */
458 public boolean equals(Object obj) {
459 if (obj instanceof Map) {
460 Map map = (Map) obj;
461 return (this.entrySet().equals(map.entrySet()));
462 }
463 return false;
464 }
465
466 /**
467 * Gets a hash code for the Map as per the Map specification.
468 */
469 public int hashCode() {
470 int code = 0;
471 for (Iterator i = this.entrySet().iterator(); i.hasNext();) {
472 code += i.next().hashCode();
473 }
474 return code;
475 }
476
477 /**
478 * This interface allows definition for all of the indeterminate
479 * mutators in a CompositeMap, as well as providing a hook for
480 * callbacks on key collisions.
481 */
482 public static interface MapMutator {
483 /**
484 * Called when adding a new Composited Map results in a
485 * key collision.
486 *
487 * @param composite the CompositeMap with the collision
488 * @param existing the Map already in the composite which contains the
489 * offending key
490 * @param added the Map being added
491 * @param intersect the intersection of the keysets of the existing and added maps
492 */
493 public void resolveCollision(
494 CompositeMap composite, Map existing, Map added, Collection intersect);
495
496 /**
497 * Called when the CompositeMap.put() method is invoked.
498 *
499 * @param map the CompositeMap which is being modified
500 * @param composited array of Maps in the CompositeMap being modified
501 * @param key key with which the specified value is to be associated.
502 * @param value value to be associated with the specified key.
503 * @return previous value associated with specified key, or <tt>null</tt>
504 * if there was no mapping for key. A <tt>null</tt> return can
505 * also indicate that the map previously associated <tt>null</tt>
506 * with the specified key, if the implementation supports
507 * <tt>null</tt> values.
508 *
509 * @throws UnsupportedOperationException if not defined
510 * @throws ClassCastException if the class of the specified key or value
511 * prevents it from being stored in this map.
512 * @throws IllegalArgumentException if some aspect of this key or value
513 * prevents it from being stored in this map.
514 * @throws NullPointerException this map does not permit <tt>null</tt>
515 * keys or values, and the specified key or value is
516 * <tt>null</tt>.
517 */
518 public Object put(CompositeMap map, Map[] composited, Object key, Object value);
519
520 /**
521 * Called when the CompositeMap.putAll() method is invoked.
522 *
523 * @param map the CompositeMap which is being modified
524 * @param composited array of Maps in the CompositeMap being modified
525 * @param mapToAdd Mappings to be stored in this CompositeMap
526 *
527 * @throws UnsupportedOperationException if not defined
528 * @throws ClassCastException if the class of the specified key or value
529 * prevents it from being stored in this map.
530 * @throws IllegalArgumentException if some aspect of this key or value
531 * prevents it from being stored in this map.
532 * @throws NullPointerException this map does not permit <tt>null</tt>
533 * keys or values, and the specified key or value is
534 * <tt>null</tt>.
535 */
536 public void putAll(CompositeMap map, Map[] composited, Map mapToAdd);
537 }
538 }