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.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.io.Serializable; 023import java.util.AbstractCollection; 024import java.util.ArrayList; 025import java.util.Collection; 026import java.util.HashMap; 027import java.util.Iterator; 028import java.util.Map; 029import java.util.Set; 030 031import org.apache.commons.collections4.CollectionUtils; 032import org.apache.commons.collections4.Factory; 033import org.apache.commons.collections4.FunctorException; 034import org.apache.commons.collections4.MultiMap; 035import org.apache.commons.collections4.Transformer; 036import org.apache.commons.collections4.iterators.EmptyIterator; 037import org.apache.commons.collections4.iterators.IteratorChain; 038import org.apache.commons.collections4.iterators.LazyIteratorChain; 039import org.apache.commons.collections4.iterators.TransformIterator; 040 041/** 042 * A MultiValueMap decorates another map, allowing it to have 043 * more than one value for a key. 044 * <p> 045 * A {@code MultiMap} is a Map with slightly different semantics. 046 * Putting a value into the map will add the value to a Collection at that key. 047 * Getting a value will return a Collection, holding all the values put to that key. 048 * </p> 049 * <p> 050 * This implementation is a decorator, allowing any Map implementation 051 * to be used as the base. 052 * </p> 053 * <p> 054 * In addition, this implementation allows the type of collection used 055 * for the values to be controlled. By default, an {@code ArrayList} 056 * is used, however a {@code Class} to instantiate may be specified, 057 * or a factory that returns a {@code Collection} instance. 058 * </p> 059 * <p> 060 * <strong>Note that MultiValueMap is not synchronized and is not thread-safe.</strong> 061 * If you wish to use this map from multiple threads concurrently, you must use 062 * appropriate synchronization. This class may throw exceptions when accessed 063 * by concurrent threads without synchronization. 064 * </p> 065 * 066 * @param <K> the type of the keys in this map 067 * @param <V> the type of the values in this map 068 * @since 3.2 069 * @deprecated since 4.1, use {@link org.apache.commons.collections4.MultiValuedMap MultiValuedMap} instead 070 */ 071@Deprecated 072public class MultiValueMap<K, V> extends AbstractMapDecorator<K, Object> implements MultiMap<K, V>, Serializable { 073 074 /** 075 * Inner class that provides a simple reflection factory. 076 */ 077 private static final class ReflectionFactory<T extends Collection<?>> implements Factory<T>, Serializable { 078 079 /** Serialization version */ 080 private static final long serialVersionUID = 2986114157496788874L; 081 082 private final Class<T> clazz; 083 084 ReflectionFactory(final Class<T> clazz) { 085 this.clazz = clazz; 086 } 087 088 @Override 089 public T create() { 090 try { 091 return clazz.getDeclaredConstructor().newInstance(); 092 } catch (final Exception ex) { 093 throw new FunctorException("Cannot instantiate class: " + clazz, ex); 094 } 095 } 096 097 private void readObject(final ObjectInputStream is) throws IOException, ClassNotFoundException { 098 is.defaultReadObject(); 099 // ensure that the de-serialized class is a Collection, COLLECTIONS-580 100 if (clazz != null && !Collection.class.isAssignableFrom(clazz)) { 101 throw new UnsupportedOperationException(); 102 } 103 } 104 } 105 106 /** 107 * Inner class that provides the values view. 108 */ 109 private final class Values extends AbstractCollection<V> { 110 @Override 111 public void clear() { 112 MultiValueMap.this.clear(); 113 } 114 115 @Override 116 public Iterator<V> iterator() { 117 final IteratorChain<V> chain = new IteratorChain<>(); 118 for (final K k : keySet()) { 119 chain.addIterator(new ValuesIterator(k)); 120 } 121 return chain; 122 } 123 124 @Override 125 public int size() { 126 return totalSize(); 127 } 128 } 129 /** 130 * Inner class that provides the values iterator. 131 */ 132 private final class ValuesIterator implements Iterator<V> { 133 private final Object key; 134 private final Collection<V> values; 135 private final Iterator<V> iterator; 136 137 ValuesIterator(final Object key) { 138 this.key = key; 139 this.values = getCollection(key); 140 this.iterator = values.iterator(); 141 } 142 143 @Override 144 public boolean hasNext() { 145 return iterator.hasNext(); 146 } 147 148 @Override 149 public V next() { 150 return iterator.next(); 151 } 152 153 @Override 154 public void remove() { 155 iterator.remove(); 156 if (values.isEmpty()) { 157 MultiValueMap.this.remove(key); 158 } 159 } 160 } 161 162 /** Serialization version */ 163 private static final long serialVersionUID = -2214159910087182007L; 164 165 /** 166 * Creates a map which decorates the given {@code map} and 167 * maps keys to collections of type {@code collectionClass}. 168 * 169 * @param <K> the key type 170 * @param <V> the value type 171 * @param <C> the collection class type 172 * @param map the map to wrap 173 * @param collectionClass the type of the collection class 174 * @return a new multi-value map 175 * @since 4.0 176 */ 177 public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map, 178 final Class<C> collectionClass) { 179 return new MultiValueMap<>(map, new ReflectionFactory<>(collectionClass)); 180 } 181 182 /** 183 * Creates a map which decorates the given {@code map} and 184 * creates the value collections using the supplied {@code collectionFactory}. 185 * 186 * @param <K> the key type 187 * @param <V> the value type 188 * @param <C> the collection class type 189 * @param map the map to decorate 190 * @param collectionFactory the collection factory (must return a Collection object). 191 * @return a new multi-value map 192 * @since 4.0 193 */ 194 public static <K, V, C extends Collection<V>> MultiValueMap<K, V> multiValueMap(final Map<K, ? super C> map, 195 final Factory<C> collectionFactory) { 196 return new MultiValueMap<>(map, collectionFactory); 197 } 198 199 /** 200 * Creates a map which wraps the given map and 201 * maps keys to ArrayLists. 202 * 203 * @param <K> the key type 204 * @param <V> the value type 205 * @param map the map to wrap 206 * @return a new multi-value map 207 * @since 4.0 208 */ 209 @SuppressWarnings({ "unchecked", "rawtypes" }) 210 public static <K, V> MultiValueMap<K, V> multiValueMap(final Map<K, ? super Collection<V>> map) { 211 return MultiValueMap.<K, V, ArrayList>multiValueMap((Map<K, ? super Collection>) map, ArrayList.class); 212 } 213 214 /** The factory for creating value collections. */ 215 private final Factory<? extends Collection<V>> collectionFactory; 216 217 /** The cached values. */ 218 private transient Collection<V> valuesView; 219 220 /** 221 * Creates a MultiValueMap based on a {@code HashMap} and 222 * storing the multiple values in an {@code ArrayList}. 223 */ 224 @SuppressWarnings({ "unchecked", "rawtypes" }) 225 public MultiValueMap() { 226 this(new HashMap<>(), new ReflectionFactory(ArrayList.class)); 227 } 228 229 /** 230 * Creates a MultiValueMap which decorates the given {@code map} and 231 * creates the value collections using the supplied {@code collectionFactory}. 232 * 233 * @param <C> the collection class type 234 * @param map the map to decorate 235 * @param collectionFactory the collection factory which must return a Collection instance 236 */ 237 @SuppressWarnings("unchecked") 238 protected <C extends Collection<V>> MultiValueMap(final Map<K, ? super C> map, 239 final Factory<C> collectionFactory) { 240 super((Map<K, Object>) map); 241 if (collectionFactory == null) { 242 throw new IllegalArgumentException("The factory must not be null"); 243 } 244 this.collectionFactory = collectionFactory; 245 } 246 247 /** 248 * Clear the map. 249 */ 250 @Override 251 public void clear() { 252 // If you believe that you have GC issues here, try uncommenting this code 253// Set pairs = getMap().entrySet(); 254// Iterator pairsIterator = pairs.iterator(); 255// while (pairsIterator.hasNext()) { 256// Map.Entry keyValuePair = (Map.Entry) pairsIterator.next(); 257// Collection coll = (Collection) keyValuePair.getValue(); 258// coll.clear(); 259// } 260 decorated().clear(); 261 } 262 263 /** 264 * Checks whether the map contains the value specified. 265 * <p> 266 * This checks all collections against all keys for the value, and thus could be slow. 267 * 268 * @param value the value to search for 269 * @return true if the map contains the value 270 */ 271 @Override 272 @SuppressWarnings("unchecked") 273 public boolean containsValue(final Object value) { 274 final Set<Map.Entry<K, Object>> pairs = decorated().entrySet(); 275 if (pairs != null) { 276 for (final Map.Entry<K, Object> entry : pairs) { 277 if (((Collection<V>) entry.getValue()).contains(value)) { 278 return true; 279 } 280 } 281 } 282 return false; 283 } 284 285 /** 286 * Checks whether the collection at the specified key contains the value. 287 * 288 * @param key the key to search for 289 * @param value the value to search for 290 * @return true if the map contains the value 291 */ 292 public boolean containsValue(final Object key, final Object value) { 293 final Collection<V> coll = getCollection(key); 294 if (coll == null) { 295 return false; 296 } 297 return coll.contains(value); 298 } 299 300 /** 301 * Creates a new instance of the map value Collection container 302 * using the factory. 303 * <p> 304 * This method can be overridden to perform your own processing 305 * instead of using the factory. 306 * 307 * @param size the collection size that is about to be added 308 * @return the new collection 309 */ 310 protected Collection<V> createCollection(final int size) { 311 return collectionFactory.create(); 312 } 313 314 /** 315 * {@inheritDoc} 316 * <p> 317 * NOTE: the returned Entry objects will contain as value a {@link Collection} 318 * of all values that are mapped to the given key. To get a "flattened" version 319 * of all mappings contained in this map, use {@link #iterator()}. 320 * 321 * @see #iterator() 322 */ 323 @Override 324 public Set<Entry<K, Object>> entrySet() { // NOPMD 325 return super.entrySet(); 326 } 327 328 /** 329 * Gets the collection mapped to the specified key. 330 * This method is a convenience method to typecast the result of {@code get(key)}. 331 * 332 * @param key the key to retrieve 333 * @return the collection mapped to the key, null if no mapping 334 */ 335 @SuppressWarnings("unchecked") 336 public Collection<V> getCollection(final Object key) { 337 return (Collection<V>) decorated().get(key); 338 } 339 340 /** 341 * Gets an iterator for all mappings stored in this {@link MultiValueMap}. 342 * <p> 343 * The iterator will return multiple Entry objects with the same key 344 * if there are multiple values mapped to this key. 345 * <p> 346 * NOTE: calling {@link java.util.Map.Entry#setValue(Object)} on any of the returned 347 * elements will result in a {@link UnsupportedOperationException}. 348 * 349 * @return the iterator of all mappings in this map 350 * @since 4.0 351 */ 352 public Iterator<Entry<K, V>> iterator() { 353 final Collection<K> allKeys = new ArrayList<>(keySet()); 354 final Iterator<K> keyIterator = allKeys.iterator(); 355 356 return new LazyIteratorChain<Entry<K, V>>() { 357 @Override 358 protected Iterator<? extends Entry<K, V>> nextIterator(final int count) { 359 if ( ! keyIterator.hasNext() ) { 360 return null; 361 } 362 final K key = keyIterator.next(); 363 final Transformer<V, Entry<K, V>> transformer = input -> new Entry<K, V>() { 364 @Override 365 public K getKey() { 366 return key; 367 } 368 @Override 369 public V getValue() { 370 return input; 371 } 372 @Override 373 public V setValue(final V value) { 374 throw new UnsupportedOperationException(); 375 } 376 }; 377 return new TransformIterator<>(new ValuesIterator(key), transformer); 378 } 379 }; 380 } 381 382 /** 383 * Gets an iterator for the collection mapped to the specified key. 384 * 385 * @param key the key to get an iterator for 386 * @return the iterator of the collection at the key, empty iterator if key not in map 387 */ 388 public Iterator<V> iterator(final Object key) { 389 if (!containsKey(key)) { 390 return EmptyIterator.<V>emptyIterator(); 391 } 392 return new ValuesIterator(key); 393 } 394 395 /** 396 * Adds the value to the collection associated with the specified key. 397 * <p> 398 * Unlike a normal {@code Map} the previous value is not replaced. 399 * Instead, the new value is added to the collection stored against the key. 400 * 401 * @param key the key to store against 402 * @param value the value to add to the collection at the key 403 * @return the value added if the map changed and null if the map did not change 404 */ 405 @Override 406 @SuppressWarnings("unchecked") 407 public Object put(final K key, final Object value) { 408 boolean result = false; 409 Collection<V> coll = getCollection(key); 410 if (coll == null) { 411 coll = createCollection(1); // might produce a non-empty collection 412 coll.add((V) value); 413 if (!coll.isEmpty()) { 414 // only add if non-zero size to maintain class state 415 decorated().put(key, coll); 416 result = true; // map definitely changed 417 } 418 } else { 419 result = coll.add((V) value); 420 } 421 return result ? value : null; 422 } 423 424 /** 425 * Adds a collection of values to the collection associated with 426 * the specified key. 427 * 428 * @param key the key to store against 429 * @param values the values to add to the collection at the key, null ignored 430 * @return true if this map changed 431 */ 432 public boolean putAll(final K key, final Collection<V> values) { 433 if (values == null || values.isEmpty()) { 434 return false; 435 } 436 boolean result = false; 437 Collection<V> coll = getCollection(key); 438 if (coll == null) { 439 coll = createCollection(values.size()); // might produce a non-empty collection 440 coll.addAll(values); 441 if (!coll.isEmpty()) { 442 // only add if non-zero size to maintain class state 443 decorated().put(key, coll); 444 result = true; // map definitely changed 445 } 446 } else { 447 result = coll.addAll(values); 448 } 449 return result; 450 } 451 452 /** 453 * Override superclass to ensure that MultiMap instances are 454 * correctly handled. 455 * <p> 456 * If you call this method with a normal map, each entry is 457 * added using {@code put(Object,Object)}. 458 * If you call this method with a multi map, each entry is 459 * added using {@code putAll(Object,Collection)}. 460 * 461 * @param map the map to copy (either a normal or multi map) 462 */ 463 @Override 464 @SuppressWarnings("unchecked") 465 public void putAll(final Map<? extends K, ?> map) { 466 if (map instanceof MultiMap) { 467 for (final Map.Entry<? extends K, Object> entry : ((MultiMap<? extends K, V>) map).entrySet()) { 468 putAll(entry.getKey(), (Collection<V>) entry.getValue()); 469 } 470 } else { 471 for (final Map.Entry<? extends K, ?> entry : map.entrySet()) { 472 put(entry.getKey(), entry.getValue()); 473 } 474 } 475 } 476 477 /** 478 * Read the map in using a custom routine. 479 * 480 * @param in the input stream 481 * @throws IOException if an error occurs while reading from the stream 482 * @throws ClassNotFoundException if an object read from the stream can not be loaded 483 * @since 4.0 484 */ 485 @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect 486 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 487 in.defaultReadObject(); 488 map = (Map<K, Object>) in.readObject(); // (1) 489 } 490 491 /** 492 * Removes a specific value from map. 493 * <p> 494 * The item is removed from the collection mapped to the specified key. 495 * Other values attached to that key are unaffected. 496 * <p> 497 * If the last value for a key is removed, {@code null} will be returned 498 * from a subsequent {@code get(key)}. 499 * 500 * @param key the key to remove from 501 * @param value the value to remove 502 * @return {@code true} if the mapping was removed, {@code false} otherwise 503 */ 504 @Override 505 public boolean removeMapping(final Object key, final Object value) { 506 final Collection<V> valuesForKey = getCollection(key); 507 if (valuesForKey == null) { 508 return false; 509 } 510 final boolean removed = valuesForKey.remove(value); 511 if (!removed) { 512 return false; 513 } 514 if (valuesForKey.isEmpty()) { 515 remove(key); 516 } 517 return true; 518 } 519 520 /** 521 * Gets the size of the collection mapped to the specified key. 522 * 523 * @param key the key to get size for 524 * @return the size of the collection at the key, zero if key not in map 525 */ 526 public int size(final Object key) { 527 final Collection<V> coll = getCollection(key); 528 if (coll == null) { 529 return 0; 530 } 531 return coll.size(); 532 } 533 534 /** 535 * Gets the total size of the map by counting all the values. 536 * 537 * @return the total size of the map counting all values 538 */ 539 public int totalSize() { 540 int total = 0; 541 for (final Object v : decorated().values()) { 542 total += CollectionUtils.size(v); 543 } 544 return total; 545 } 546 547 /** 548 * Gets a collection containing all the values in the map. 549 * <p> 550 * This returns a collection containing the combination of values from all keys. 551 * 552 * @return a collection view of the values contained in this map 553 */ 554 @Override 555 @SuppressWarnings("unchecked") 556 public Collection<Object> values() { 557 final Collection<V> vs = valuesView; 558 return (Collection<Object>) (vs != null ? vs : (valuesView = new Values())); 559 } 560 561 /** 562 * Write the map out using a custom routine. 563 * 564 * @param out the output stream 565 * @throws IOException if an error occurs while writing to the stream 566 * @since 4.0 567 */ 568 private void writeObject(final ObjectOutputStream out) throws IOException { 569 out.defaultWriteObject(); 570 out.writeObject(map); 571 } 572 573}