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