001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.collect.CollectPreconditions.checkNonnegative; 021import static com.google.common.collect.CollectPreconditions.checkRemove; 022import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT; 023import static java.util.Objects.requireNonNull; 024 025import com.google.common.annotations.Beta; 026import com.google.common.annotations.GwtCompatible; 027import com.google.common.annotations.GwtIncompatible; 028import com.google.common.base.Function; 029import com.google.common.base.Predicate; 030import com.google.common.base.Predicates; 031import com.google.common.base.Supplier; 032import com.google.common.collect.Maps.EntryTransformer; 033import com.google.errorprone.annotations.CanIgnoreReturnValue; 034import com.google.errorprone.annotations.concurrent.LazyInit; 035import com.google.j2objc.annotations.Weak; 036import com.google.j2objc.annotations.WeakOuter; 037import java.io.IOException; 038import java.io.ObjectInputStream; 039import java.io.ObjectOutputStream; 040import java.io.Serializable; 041import java.util.AbstractCollection; 042import java.util.Collection; 043import java.util.Collections; 044import java.util.Comparator; 045import java.util.HashSet; 046import java.util.Iterator; 047import java.util.List; 048import java.util.Map; 049import java.util.Map.Entry; 050import java.util.NavigableSet; 051import java.util.NoSuchElementException; 052import java.util.Set; 053import java.util.SortedSet; 054import java.util.Spliterator; 055import java.util.function.BiConsumer; 056import java.util.function.Consumer; 057import java.util.stream.Collector; 058import java.util.stream.Stream; 059import javax.annotation.CheckForNull; 060import org.checkerframework.checker.nullness.qual.Nullable; 061 062/** 063 * Provides static methods acting on or generating a {@code Multimap}. 064 * 065 * <p>See the Guava User Guide article on <a href= 066 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multimaps">{@code 067 * Multimaps}</a>. 068 * 069 * @author Jared Levy 070 * @author Robert Konigsberg 071 * @author Mike Bostock 072 * @author Louis Wasserman 073 * @since 2.0 074 */ 075@GwtCompatible(emulated = true) 076@ElementTypesAreNonnullByDefault 077public final class Multimaps { 078 private Multimaps() {} 079 080 /** 081 * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the 082 * specified supplier. The keys and values of the entries are the result of applying the provided 083 * mapping functions to the input elements, accumulated in the encounter order of the stream. 084 * 085 * <p>Example: 086 * 087 * <pre>{@code 088 * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP = 089 * Stream.of("banana", "apple", "carrot", "asparagus", "cherry") 090 * .collect( 091 * toMultimap( 092 * str -> str.charAt(0), 093 * str -> str.substring(1), 094 * MultimapBuilder.treeKeys().arrayListValues()::build)); 095 * 096 * // is equivalent to 097 * 098 * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP; 099 * 100 * static { 101 * FIRST_LETTER_MULTIMAP = MultimapBuilder.treeKeys().arrayListValues().build(); 102 * FIRST_LETTER_MULTIMAP.put('b', "anana"); 103 * FIRST_LETTER_MULTIMAP.put('a', "pple"); 104 * FIRST_LETTER_MULTIMAP.put('a', "sparagus"); 105 * FIRST_LETTER_MULTIMAP.put('c', "arrot"); 106 * FIRST_LETTER_MULTIMAP.put('c', "herry"); 107 * } 108 * }</pre> 109 * 110 * <p>To collect to an {@link ImmutableMultimap}, use either {@link 111 * ImmutableSetMultimap#toImmutableSetMultimap} or {@link 112 * ImmutableListMultimap#toImmutableListMultimap}. 113 * 114 * @since 21.0 115 */ 116 public static < 117 T extends @Nullable Object, 118 K extends @Nullable Object, 119 V extends @Nullable Object, 120 M extends Multimap<K, V>> 121 Collector<T, ?, M> toMultimap( 122 java.util.function.Function<? super T, ? extends K> keyFunction, 123 java.util.function.Function<? super T, ? extends V> valueFunction, 124 java.util.function.Supplier<M> multimapSupplier) { 125 return CollectCollectors.toMultimap(keyFunction, valueFunction, multimapSupplier); 126 } 127 128 /** 129 * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the 130 * specified supplier. Each input element is mapped to a key and a stream of values, each of which 131 * are put into the resulting {@code Multimap}, in the encounter order of the stream and the 132 * encounter order of the streams of values. 133 * 134 * <p>Example: 135 * 136 * <pre>{@code 137 * static final ListMultimap<Character, Character> FIRST_LETTER_MULTIMAP = 138 * Stream.of("banana", "apple", "carrot", "asparagus", "cherry") 139 * .collect( 140 * flatteningToMultimap( 141 * str -> str.charAt(0), 142 * str -> str.substring(1).chars().mapToObj(c -> (char) c), 143 * MultimapBuilder.linkedHashKeys().arrayListValues()::build)); 144 * 145 * // is equivalent to 146 * 147 * static final ListMultimap<Character, Character> FIRST_LETTER_MULTIMAP; 148 * 149 * static { 150 * FIRST_LETTER_MULTIMAP = MultimapBuilder.linkedHashKeys().arrayListValues().build(); 151 * FIRST_LETTER_MULTIMAP.putAll('b', Arrays.asList('a', 'n', 'a', 'n', 'a')); 152 * FIRST_LETTER_MULTIMAP.putAll('a', Arrays.asList('p', 'p', 'l', 'e')); 153 * FIRST_LETTER_MULTIMAP.putAll('c', Arrays.asList('a', 'r', 'r', 'o', 't')); 154 * FIRST_LETTER_MULTIMAP.putAll('a', Arrays.asList('s', 'p', 'a', 'r', 'a', 'g', 'u', 's')); 155 * FIRST_LETTER_MULTIMAP.putAll('c', Arrays.asList('h', 'e', 'r', 'r', 'y')); 156 * } 157 * }</pre> 158 * 159 * @since 21.0 160 */ 161 @Beta 162 public static < 163 T extends @Nullable Object, 164 K extends @Nullable Object, 165 V extends @Nullable Object, 166 M extends Multimap<K, V>> 167 Collector<T, ?, M> flatteningToMultimap( 168 java.util.function.Function<? super T, ? extends K> keyFunction, 169 java.util.function.Function<? super T, ? extends Stream<? extends V>> valueFunction, 170 java.util.function.Supplier<M> multimapSupplier) { 171 return CollectCollectors.flatteningToMultimap(keyFunction, valueFunction, multimapSupplier); 172 } 173 174 /** 175 * Creates a new {@code Multimap} backed by {@code map}, whose internal value collections are 176 * generated by {@code factory}. 177 * 178 * <p><b>Warning: do not use</b> this method when the collections returned by {@code factory} 179 * implement either {@link List} or {@code Set}! Use the more specific method {@link 180 * #newListMultimap}, {@link #newSetMultimap} or {@link #newSortedSetMultimap} instead, to avoid 181 * very surprising behavior from {@link Multimap#equals}. 182 * 183 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration 184 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code 185 * toString} methods for the multimap and its returned views. However, the multimap's {@code get} 186 * method returns instances of a different class than {@code factory.get()} does. 187 * 188 * <p>The multimap is serializable if {@code map}, {@code factory}, the collections generated by 189 * {@code factory}, and the multimap contents are all serializable. 190 * 191 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if 192 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will 193 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link 194 * #synchronizedMultimap}. 195 * 196 * <p>Call this method only when the simpler methods {@link ArrayListMultimap#create()}, {@link 197 * HashMultimap#create()}, {@link LinkedHashMultimap#create()}, {@link 198 * LinkedListMultimap#create()}, {@link TreeMultimap#create()}, and {@link 199 * TreeMultimap#create(Comparator, Comparator)} won't suffice. 200 * 201 * <p>Note: the multimap assumes complete ownership over of {@code map} and the collections 202 * returned by {@code factory}. Those objects should not be manually updated and they should not 203 * use soft, weak, or phantom references. 204 * 205 * @param map place to store the mapping from each key to its corresponding values 206 * @param factory supplier of new, empty collections that will each hold all values for a given 207 * key 208 * @throws IllegalArgumentException if {@code map} is not empty 209 */ 210 public static <K extends @Nullable Object, V extends @Nullable Object> Multimap<K, V> newMultimap( 211 Map<K, Collection<V>> map, final Supplier<? extends Collection<V>> factory) { 212 return new CustomMultimap<>(map, factory); 213 } 214 215 private static class CustomMultimap<K extends @Nullable Object, V extends @Nullable Object> 216 extends AbstractMapBasedMultimap<K, V> { 217 transient Supplier<? extends Collection<V>> factory; 218 219 CustomMultimap(Map<K, Collection<V>> map, Supplier<? extends Collection<V>> factory) { 220 super(map); 221 this.factory = checkNotNull(factory); 222 } 223 224 @Override 225 Set<K> createKeySet() { 226 return createMaybeNavigableKeySet(); 227 } 228 229 @Override 230 Map<K, Collection<V>> createAsMap() { 231 return createMaybeNavigableAsMap(); 232 } 233 234 @Override 235 protected Collection<V> createCollection() { 236 return factory.get(); 237 } 238 239 @Override 240 <E extends @Nullable Object> Collection<E> unmodifiableCollectionSubclass( 241 Collection<E> collection) { 242 if (collection instanceof NavigableSet) { 243 return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection); 244 } else if (collection instanceof SortedSet) { 245 return Collections.unmodifiableSortedSet((SortedSet<E>) collection); 246 } else if (collection instanceof Set) { 247 return Collections.unmodifiableSet((Set<E>) collection); 248 } else if (collection instanceof List) { 249 return Collections.unmodifiableList((List<E>) collection); 250 } else { 251 return Collections.unmodifiableCollection(collection); 252 } 253 } 254 255 @Override 256 Collection<V> wrapCollection(@ParametricNullness K key, Collection<V> collection) { 257 if (collection instanceof List) { 258 return wrapList(key, (List<V>) collection, null); 259 } else if (collection instanceof NavigableSet) { 260 return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null); 261 } else if (collection instanceof SortedSet) { 262 return new WrappedSortedSet(key, (SortedSet<V>) collection, null); 263 } else if (collection instanceof Set) { 264 return new WrappedSet(key, (Set<V>) collection); 265 } else { 266 return new WrappedCollection(key, collection, null); 267 } 268 } 269 270 // can't use Serialization writeMultimap and populateMultimap methods since 271 // there's no way to generate the empty backing map. 272 273 /** @serialData the factory and the backing map */ 274 @GwtIncompatible // java.io.ObjectOutputStream 275 private void writeObject(ObjectOutputStream stream) throws IOException { 276 stream.defaultWriteObject(); 277 stream.writeObject(factory); 278 stream.writeObject(backingMap()); 279 } 280 281 @GwtIncompatible // java.io.ObjectInputStream 282 @SuppressWarnings("unchecked") // reading data stored by writeObject 283 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 284 stream.defaultReadObject(); 285 factory = (Supplier<? extends Collection<V>>) stream.readObject(); 286 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject(); 287 setMap(map); 288 } 289 290 @GwtIncompatible // java serialization not supported 291 private static final long serialVersionUID = 0; 292 } 293 294 /** 295 * Creates a new {@code ListMultimap} that uses the provided map and factory. It can generate a 296 * multimap based on arbitrary {@link Map} and {@link List} classes. 297 * 298 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration 299 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code 300 * toString} methods for the multimap and its returned views. The multimap's {@code get}, {@code 301 * removeAll}, and {@code replaceValues} methods return {@code RandomAccess} lists if the factory 302 * does. However, the multimap's {@code get} method returns instances of a different class than 303 * does {@code factory.get()}. 304 * 305 * <p>The multimap is serializable if {@code map}, {@code factory}, the lists generated by {@code 306 * factory}, and the multimap contents are all serializable. 307 * 308 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if 309 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will 310 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link 311 * #synchronizedListMultimap}. 312 * 313 * <p>Call this method only when the simpler methods {@link ArrayListMultimap#create()} and {@link 314 * LinkedListMultimap#create()} won't suffice. 315 * 316 * <p>Note: the multimap assumes complete ownership over of {@code map} and the lists returned by 317 * {@code factory}. Those objects should not be manually updated, they should be empty when 318 * provided, and they should not use soft, weak, or phantom references. 319 * 320 * @param map place to store the mapping from each key to its corresponding values 321 * @param factory supplier of new, empty lists that will each hold all values for a given key 322 * @throws IllegalArgumentException if {@code map} is not empty 323 */ 324 public static <K extends @Nullable Object, V extends @Nullable Object> 325 ListMultimap<K, V> newListMultimap( 326 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) { 327 return new CustomListMultimap<>(map, factory); 328 } 329 330 private static class CustomListMultimap<K extends @Nullable Object, V extends @Nullable Object> 331 extends AbstractListMultimap<K, V> { 332 transient Supplier<? extends List<V>> factory; 333 334 CustomListMultimap(Map<K, Collection<V>> map, Supplier<? extends List<V>> factory) { 335 super(map); 336 this.factory = checkNotNull(factory); 337 } 338 339 @Override 340 Set<K> createKeySet() { 341 return createMaybeNavigableKeySet(); 342 } 343 344 @Override 345 Map<K, Collection<V>> createAsMap() { 346 return createMaybeNavigableAsMap(); 347 } 348 349 @Override 350 protected List<V> createCollection() { 351 return factory.get(); 352 } 353 354 /** @serialData the factory and the backing map */ 355 @GwtIncompatible // java.io.ObjectOutputStream 356 private void writeObject(ObjectOutputStream stream) throws IOException { 357 stream.defaultWriteObject(); 358 stream.writeObject(factory); 359 stream.writeObject(backingMap()); 360 } 361 362 @GwtIncompatible // java.io.ObjectInputStream 363 @SuppressWarnings("unchecked") // reading data stored by writeObject 364 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 365 stream.defaultReadObject(); 366 factory = (Supplier<? extends List<V>>) stream.readObject(); 367 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject(); 368 setMap(map); 369 } 370 371 @GwtIncompatible // java serialization not supported 372 private static final long serialVersionUID = 0; 373 } 374 375 /** 376 * Creates a new {@code SetMultimap} that uses the provided map and factory. It can generate a 377 * multimap based on arbitrary {@link Map} and {@link Set} classes. 378 * 379 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration 380 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code 381 * toString} methods for the multimap and its returned views. However, the multimap's {@code get} 382 * method returns instances of a different class than {@code factory.get()} does. 383 * 384 * <p>The multimap is serializable if {@code map}, {@code factory}, the sets generated by {@code 385 * factory}, and the multimap contents are all serializable. 386 * 387 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if 388 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will 389 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link 390 * #synchronizedSetMultimap}. 391 * 392 * <p>Call this method only when the simpler methods {@link HashMultimap#create()}, {@link 393 * LinkedHashMultimap#create()}, {@link TreeMultimap#create()}, and {@link 394 * TreeMultimap#create(Comparator, Comparator)} won't suffice. 395 * 396 * <p>Note: the multimap assumes complete ownership over of {@code map} and the sets returned by 397 * {@code factory}. Those objects should not be manually updated and they should not use soft, 398 * weak, or phantom references. 399 * 400 * @param map place to store the mapping from each key to its corresponding values 401 * @param factory supplier of new, empty sets that will each hold all values for a given key 402 * @throws IllegalArgumentException if {@code map} is not empty 403 */ 404 public static <K extends @Nullable Object, V extends @Nullable Object> 405 SetMultimap<K, V> newSetMultimap( 406 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) { 407 return new CustomSetMultimap<>(map, factory); 408 } 409 410 private static class CustomSetMultimap<K extends @Nullable Object, V extends @Nullable Object> 411 extends AbstractSetMultimap<K, V> { 412 transient Supplier<? extends Set<V>> factory; 413 414 CustomSetMultimap(Map<K, Collection<V>> map, Supplier<? extends Set<V>> factory) { 415 super(map); 416 this.factory = checkNotNull(factory); 417 } 418 419 @Override 420 Set<K> createKeySet() { 421 return createMaybeNavigableKeySet(); 422 } 423 424 @Override 425 Map<K, Collection<V>> createAsMap() { 426 return createMaybeNavigableAsMap(); 427 } 428 429 @Override 430 protected Set<V> createCollection() { 431 return factory.get(); 432 } 433 434 @Override 435 <E extends @Nullable Object> Collection<E> unmodifiableCollectionSubclass( 436 Collection<E> collection) { 437 if (collection instanceof NavigableSet) { 438 return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection); 439 } else if (collection instanceof SortedSet) { 440 return Collections.unmodifiableSortedSet((SortedSet<E>) collection); 441 } else { 442 return Collections.unmodifiableSet((Set<E>) collection); 443 } 444 } 445 446 @Override 447 Collection<V> wrapCollection(@ParametricNullness K key, Collection<V> collection) { 448 if (collection instanceof NavigableSet) { 449 return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null); 450 } else if (collection instanceof SortedSet) { 451 return new WrappedSortedSet(key, (SortedSet<V>) collection, null); 452 } else { 453 return new WrappedSet(key, (Set<V>) collection); 454 } 455 } 456 457 /** @serialData the factory and the backing map */ 458 @GwtIncompatible // java.io.ObjectOutputStream 459 private void writeObject(ObjectOutputStream stream) throws IOException { 460 stream.defaultWriteObject(); 461 stream.writeObject(factory); 462 stream.writeObject(backingMap()); 463 } 464 465 @GwtIncompatible // java.io.ObjectInputStream 466 @SuppressWarnings("unchecked") // reading data stored by writeObject 467 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 468 stream.defaultReadObject(); 469 factory = (Supplier<? extends Set<V>>) stream.readObject(); 470 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject(); 471 setMap(map); 472 } 473 474 @GwtIncompatible // not needed in emulated source 475 private static final long serialVersionUID = 0; 476 } 477 478 /** 479 * Creates a new {@code SortedSetMultimap} that uses the provided map and factory. It can generate 480 * a multimap based on arbitrary {@link Map} and {@link SortedSet} classes. 481 * 482 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration 483 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code 484 * toString} methods for the multimap and its returned views. However, the multimap's {@code get} 485 * method returns instances of a different class than {@code factory.get()} does. 486 * 487 * <p>The multimap is serializable if {@code map}, {@code factory}, the sets generated by {@code 488 * factory}, and the multimap contents are all serializable. 489 * 490 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if 491 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will 492 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link 493 * #synchronizedSortedSetMultimap}. 494 * 495 * <p>Call this method only when the simpler methods {@link TreeMultimap#create()} and {@link 496 * TreeMultimap#create(Comparator, Comparator)} won't suffice. 497 * 498 * <p>Note: the multimap assumes complete ownership over of {@code map} and the sets returned by 499 * {@code factory}. Those objects should not be manually updated and they should not use soft, 500 * weak, or phantom references. 501 * 502 * @param map place to store the mapping from each key to its corresponding values 503 * @param factory supplier of new, empty sorted sets that will each hold all values for a given 504 * key 505 * @throws IllegalArgumentException if {@code map} is not empty 506 */ 507 public static <K extends @Nullable Object, V extends @Nullable Object> 508 SortedSetMultimap<K, V> newSortedSetMultimap( 509 Map<K, Collection<V>> map, final Supplier<? extends SortedSet<V>> factory) { 510 return new CustomSortedSetMultimap<>(map, factory); 511 } 512 513 private static class CustomSortedSetMultimap< 514 K extends @Nullable Object, V extends @Nullable Object> 515 extends AbstractSortedSetMultimap<K, V> { 516 transient Supplier<? extends SortedSet<V>> factory; 517 @CheckForNull transient Comparator<? super V> valueComparator; 518 519 CustomSortedSetMultimap(Map<K, Collection<V>> map, Supplier<? extends SortedSet<V>> factory) { 520 super(map); 521 this.factory = checkNotNull(factory); 522 valueComparator = factory.get().comparator(); 523 } 524 525 @Override 526 Set<K> createKeySet() { 527 return createMaybeNavigableKeySet(); 528 } 529 530 @Override 531 Map<K, Collection<V>> createAsMap() { 532 return createMaybeNavigableAsMap(); 533 } 534 535 @Override 536 protected SortedSet<V> createCollection() { 537 return factory.get(); 538 } 539 540 @Override 541 @CheckForNull 542 public Comparator<? super V> valueComparator() { 543 return valueComparator; 544 } 545 546 /** @serialData the factory and the backing map */ 547 @GwtIncompatible // java.io.ObjectOutputStream 548 private void writeObject(ObjectOutputStream stream) throws IOException { 549 stream.defaultWriteObject(); 550 stream.writeObject(factory); 551 stream.writeObject(backingMap()); 552 } 553 554 @GwtIncompatible // java.io.ObjectInputStream 555 @SuppressWarnings("unchecked") // reading data stored by writeObject 556 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 557 stream.defaultReadObject(); 558 factory = (Supplier<? extends SortedSet<V>>) stream.readObject(); 559 valueComparator = factory.get().comparator(); 560 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject(); 561 setMap(map); 562 } 563 564 @GwtIncompatible // not needed in emulated source 565 private static final long serialVersionUID = 0; 566 } 567 568 /** 569 * Copies each key-value mapping in {@code source} into {@code dest}, with its key and value 570 * reversed. 571 * 572 * <p>If {@code source} is an {@link ImmutableMultimap}, consider using {@link 573 * ImmutableMultimap#inverse} instead. 574 * 575 * @param source any multimap 576 * @param dest the multimap to copy into; usually empty 577 * @return {@code dest} 578 */ 579 @CanIgnoreReturnValue 580 public static <K extends @Nullable Object, V extends @Nullable Object, M extends Multimap<K, V>> 581 M invertFrom(Multimap<? extends V, ? extends K> source, M dest) { 582 checkNotNull(dest); 583 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) { 584 dest.put(entry.getValue(), entry.getKey()); 585 } 586 return dest; 587 } 588 589 /** 590 * Returns a synchronized (thread-safe) multimap backed by the specified multimap. In order to 591 * guarantee serial access, it is critical that <b>all</b> access to the backing multimap is 592 * accomplished through the returned multimap. 593 * 594 * <p>It is imperative that the user manually synchronize on the returned multimap when accessing 595 * any of its collection views: 596 * 597 * <pre>{@code 598 * Multimap<K, V> multimap = Multimaps.synchronizedMultimap( 599 * HashMultimap.<K, V>create()); 600 * ... 601 * Collection<V> values = multimap.get(key); // Needn't be in synchronized block 602 * ... 603 * synchronized (multimap) { // Synchronizing on multimap, not values! 604 * Iterator<V> i = values.iterator(); // Must be in synchronized block 605 * while (i.hasNext()) { 606 * foo(i.next()); 607 * } 608 * } 609 * }</pre> 610 * 611 * <p>Failure to follow this advice may result in non-deterministic behavior. 612 * 613 * <p>Note that the generated multimap's {@link Multimap#removeAll} and {@link 614 * Multimap#replaceValues} methods return collections that aren't synchronized. 615 * 616 * <p>The returned multimap will be serializable if the specified multimap is serializable. 617 * 618 * @param multimap the multimap to be wrapped in a synchronized view 619 * @return a synchronized view of the specified multimap 620 */ 621 public static <K extends @Nullable Object, V extends @Nullable Object> 622 Multimap<K, V> synchronizedMultimap(Multimap<K, V> multimap) { 623 return Synchronized.multimap(multimap, null); 624 } 625 626 /** 627 * Returns an unmodifiable view of the specified multimap. Query operations on the returned 628 * multimap "read through" to the specified multimap, and attempts to modify the returned 629 * multimap, either directly or through the multimap's views, result in an {@code 630 * UnsupportedOperationException}. 631 * 632 * <p>The returned multimap will be serializable if the specified multimap is serializable. 633 * 634 * @param delegate the multimap for which an unmodifiable view is to be returned 635 * @return an unmodifiable view of the specified multimap 636 */ 637 public static <K extends @Nullable Object, V extends @Nullable Object> 638 Multimap<K, V> unmodifiableMultimap(Multimap<K, V> delegate) { 639 if (delegate instanceof UnmodifiableMultimap || delegate instanceof ImmutableMultimap) { 640 return delegate; 641 } 642 return new UnmodifiableMultimap<>(delegate); 643 } 644 645 /** 646 * Simply returns its argument. 647 * 648 * @deprecated no need to use this 649 * @since 10.0 650 */ 651 @Deprecated 652 public static <K, V> Multimap<K, V> unmodifiableMultimap(ImmutableMultimap<K, V> delegate) { 653 return checkNotNull(delegate); 654 } 655 656 private static class UnmodifiableMultimap<K extends @Nullable Object, V extends @Nullable Object> 657 extends ForwardingMultimap<K, V> implements Serializable { 658 final Multimap<K, V> delegate; 659 @LazyInit @CheckForNull transient Collection<Entry<K, V>> entries; 660 @LazyInit @CheckForNull transient Multiset<K> keys; 661 @LazyInit @CheckForNull transient Set<K> keySet; 662 @LazyInit @CheckForNull transient Collection<V> values; 663 @LazyInit @CheckForNull transient Map<K, Collection<V>> map; 664 665 UnmodifiableMultimap(final Multimap<K, V> delegate) { 666 this.delegate = checkNotNull(delegate); 667 } 668 669 @Override 670 protected Multimap<K, V> delegate() { 671 return delegate; 672 } 673 674 @Override 675 public void clear() { 676 throw new UnsupportedOperationException(); 677 } 678 679 @Override 680 public Map<K, Collection<V>> asMap() { 681 Map<K, Collection<V>> result = map; 682 if (result == null) { 683 result = 684 map = 685 Collections.unmodifiableMap( 686 Maps.transformValues( 687 delegate.asMap(), 688 new Function<Collection<V>, Collection<V>>() { 689 @Override 690 public Collection<V> apply(Collection<V> collection) { 691 return unmodifiableValueCollection(collection); 692 } 693 })); 694 } 695 return result; 696 } 697 698 @Override 699 public Collection<Entry<K, V>> entries() { 700 Collection<Entry<K, V>> result = entries; 701 if (result == null) { 702 entries = result = unmodifiableEntries(delegate.entries()); 703 } 704 return result; 705 } 706 707 @Override 708 public void forEach(BiConsumer<? super K, ? super V> consumer) { 709 delegate.forEach(checkNotNull(consumer)); 710 } 711 712 @Override 713 public Collection<V> get(@ParametricNullness K key) { 714 return unmodifiableValueCollection(delegate.get(key)); 715 } 716 717 @Override 718 public Multiset<K> keys() { 719 Multiset<K> result = keys; 720 if (result == null) { 721 keys = result = Multisets.unmodifiableMultiset(delegate.keys()); 722 } 723 return result; 724 } 725 726 @Override 727 public Set<K> keySet() { 728 Set<K> result = keySet; 729 if (result == null) { 730 keySet = result = Collections.unmodifiableSet(delegate.keySet()); 731 } 732 return result; 733 } 734 735 @Override 736 public boolean put(@ParametricNullness K key, @ParametricNullness V value) { 737 throw new UnsupportedOperationException(); 738 } 739 740 @Override 741 public boolean putAll(@ParametricNullness K key, Iterable<? extends V> values) { 742 throw new UnsupportedOperationException(); 743 } 744 745 @Override 746 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 747 throw new UnsupportedOperationException(); 748 } 749 750 @Override 751 public boolean remove(@CheckForNull Object key, @CheckForNull Object value) { 752 throw new UnsupportedOperationException(); 753 } 754 755 @Override 756 public Collection<V> removeAll(@CheckForNull Object key) { 757 throw new UnsupportedOperationException(); 758 } 759 760 @Override 761 public Collection<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) { 762 throw new UnsupportedOperationException(); 763 } 764 765 @Override 766 public Collection<V> values() { 767 Collection<V> result = values; 768 if (result == null) { 769 values = result = Collections.unmodifiableCollection(delegate.values()); 770 } 771 return result; 772 } 773 774 private static final long serialVersionUID = 0; 775 } 776 777 private static class UnmodifiableListMultimap< 778 K extends @Nullable Object, V extends @Nullable Object> 779 extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> { 780 UnmodifiableListMultimap(ListMultimap<K, V> delegate) { 781 super(delegate); 782 } 783 784 @Override 785 public ListMultimap<K, V> delegate() { 786 return (ListMultimap<K, V>) super.delegate(); 787 } 788 789 @Override 790 public List<V> get(@ParametricNullness K key) { 791 return Collections.unmodifiableList(delegate().get(key)); 792 } 793 794 @Override 795 public List<V> removeAll(@CheckForNull Object key) { 796 throw new UnsupportedOperationException(); 797 } 798 799 @Override 800 public List<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) { 801 throw new UnsupportedOperationException(); 802 } 803 804 private static final long serialVersionUID = 0; 805 } 806 807 private static class UnmodifiableSetMultimap< 808 K extends @Nullable Object, V extends @Nullable Object> 809 extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> { 810 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) { 811 super(delegate); 812 } 813 814 @Override 815 public SetMultimap<K, V> delegate() { 816 return (SetMultimap<K, V>) super.delegate(); 817 } 818 819 @Override 820 public Set<V> get(@ParametricNullness K key) { 821 /* 822 * Note that this doesn't return a SortedSet when delegate is a 823 * SortedSetMultiset, unlike (SortedSet<V>) super.get(). 824 */ 825 return Collections.unmodifiableSet(delegate().get(key)); 826 } 827 828 @Override 829 public Set<Map.Entry<K, V>> entries() { 830 return Maps.unmodifiableEntrySet(delegate().entries()); 831 } 832 833 @Override 834 public Set<V> removeAll(@CheckForNull Object key) { 835 throw new UnsupportedOperationException(); 836 } 837 838 @Override 839 public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) { 840 throw new UnsupportedOperationException(); 841 } 842 843 private static final long serialVersionUID = 0; 844 } 845 846 private static class UnmodifiableSortedSetMultimap< 847 K extends @Nullable Object, V extends @Nullable Object> 848 extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> { 849 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) { 850 super(delegate); 851 } 852 853 @Override 854 public SortedSetMultimap<K, V> delegate() { 855 return (SortedSetMultimap<K, V>) super.delegate(); 856 } 857 858 @Override 859 public SortedSet<V> get(@ParametricNullness K key) { 860 return Collections.unmodifiableSortedSet(delegate().get(key)); 861 } 862 863 @Override 864 public SortedSet<V> removeAll(@CheckForNull Object key) { 865 throw new UnsupportedOperationException(); 866 } 867 868 @Override 869 public SortedSet<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) { 870 throw new UnsupportedOperationException(); 871 } 872 873 @Override 874 @CheckForNull 875 public Comparator<? super V> valueComparator() { 876 return delegate().valueComparator(); 877 } 878 879 private static final long serialVersionUID = 0; 880 } 881 882 /** 883 * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the specified multimap. 884 * 885 * <p>You must follow the warnings described in {@link #synchronizedMultimap}. 886 * 887 * <p>The returned multimap will be serializable if the specified multimap is serializable. 888 * 889 * @param multimap the multimap to be wrapped 890 * @return a synchronized view of the specified multimap 891 */ 892 public static <K extends @Nullable Object, V extends @Nullable Object> 893 SetMultimap<K, V> synchronizedSetMultimap(SetMultimap<K, V> multimap) { 894 return Synchronized.setMultimap(multimap, null); 895 } 896 897 /** 898 * Returns an unmodifiable view of the specified {@code SetMultimap}. Query operations on the 899 * returned multimap "read through" to the specified multimap, and attempts to modify the returned 900 * multimap, either directly or through the multimap's views, result in an {@code 901 * UnsupportedOperationException}. 902 * 903 * <p>The returned multimap will be serializable if the specified multimap is serializable. 904 * 905 * @param delegate the multimap for which an unmodifiable view is to be returned 906 * @return an unmodifiable view of the specified multimap 907 */ 908 public static <K extends @Nullable Object, V extends @Nullable Object> 909 SetMultimap<K, V> unmodifiableSetMultimap(SetMultimap<K, V> delegate) { 910 if (delegate instanceof UnmodifiableSetMultimap || delegate instanceof ImmutableSetMultimap) { 911 return delegate; 912 } 913 return new UnmodifiableSetMultimap<>(delegate); 914 } 915 916 /** 917 * Simply returns its argument. 918 * 919 * @deprecated no need to use this 920 * @since 10.0 921 */ 922 @Deprecated 923 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap( 924 ImmutableSetMultimap<K, V> delegate) { 925 return checkNotNull(delegate); 926 } 927 928 /** 929 * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by the specified 930 * multimap. 931 * 932 * <p>You must follow the warnings described in {@link #synchronizedMultimap}. 933 * 934 * <p>The returned multimap will be serializable if the specified multimap is serializable. 935 * 936 * @param multimap the multimap to be wrapped 937 * @return a synchronized view of the specified multimap 938 */ 939 public static <K extends @Nullable Object, V extends @Nullable Object> 940 SortedSetMultimap<K, V> synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) { 941 return Synchronized.sortedSetMultimap(multimap, null); 942 } 943 944 /** 945 * Returns an unmodifiable view of the specified {@code SortedSetMultimap}. Query operations on 946 * the returned multimap "read through" to the specified multimap, and attempts to modify the 947 * returned multimap, either directly or through the multimap's views, result in an {@code 948 * UnsupportedOperationException}. 949 * 950 * <p>The returned multimap will be serializable if the specified multimap is serializable. 951 * 952 * @param delegate the multimap for which an unmodifiable view is to be returned 953 * @return an unmodifiable view of the specified multimap 954 */ 955 public static <K extends @Nullable Object, V extends @Nullable Object> 956 SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) { 957 if (delegate instanceof UnmodifiableSortedSetMultimap) { 958 return delegate; 959 } 960 return new UnmodifiableSortedSetMultimap<>(delegate); 961 } 962 963 /** 964 * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the specified multimap. 965 * 966 * <p>You must follow the warnings described in {@link #synchronizedMultimap}. 967 * 968 * @param multimap the multimap to be wrapped 969 * @return a synchronized view of the specified multimap 970 */ 971 public static <K extends @Nullable Object, V extends @Nullable Object> 972 ListMultimap<K, V> synchronizedListMultimap(ListMultimap<K, V> multimap) { 973 return Synchronized.listMultimap(multimap, null); 974 } 975 976 /** 977 * Returns an unmodifiable view of the specified {@code ListMultimap}. Query operations on the 978 * returned multimap "read through" to the specified multimap, and attempts to modify the returned 979 * multimap, either directly or through the multimap's views, result in an {@code 980 * UnsupportedOperationException}. 981 * 982 * <p>The returned multimap will be serializable if the specified multimap is serializable. 983 * 984 * @param delegate the multimap for which an unmodifiable view is to be returned 985 * @return an unmodifiable view of the specified multimap 986 */ 987 public static <K extends @Nullable Object, V extends @Nullable Object> 988 ListMultimap<K, V> unmodifiableListMultimap(ListMultimap<K, V> delegate) { 989 if (delegate instanceof UnmodifiableListMultimap || delegate instanceof ImmutableListMultimap) { 990 return delegate; 991 } 992 return new UnmodifiableListMultimap<>(delegate); 993 } 994 995 /** 996 * Simply returns its argument. 997 * 998 * @deprecated no need to use this 999 * @since 10.0 1000 */ 1001 @Deprecated 1002 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap( 1003 ImmutableListMultimap<K, V> delegate) { 1004 return checkNotNull(delegate); 1005 } 1006 1007 /** 1008 * Returns an unmodifiable view of the specified collection, preserving the interface for 1009 * instances of {@code SortedSet}, {@code Set}, {@code List} and {@code Collection}, in that order 1010 * of preference. 1011 * 1012 * @param collection the collection for which to return an unmodifiable view 1013 * @return an unmodifiable view of the collection 1014 */ 1015 private static <V extends @Nullable Object> Collection<V> unmodifiableValueCollection( 1016 Collection<V> collection) { 1017 if (collection instanceof SortedSet) { 1018 return Collections.unmodifiableSortedSet((SortedSet<V>) collection); 1019 } else if (collection instanceof Set) { 1020 return Collections.unmodifiableSet((Set<V>) collection); 1021 } else if (collection instanceof List) { 1022 return Collections.unmodifiableList((List<V>) collection); 1023 } 1024 return Collections.unmodifiableCollection(collection); 1025 } 1026 1027 /** 1028 * Returns an unmodifiable view of the specified collection of entries. The {@link Entry#setValue} 1029 * operation throws an {@link UnsupportedOperationException}. If the specified collection is a 1030 * {@code Set}, the returned collection is also a {@code Set}. 1031 * 1032 * @param entries the entries for which to return an unmodifiable view 1033 * @return an unmodifiable view of the entries 1034 */ 1035 private static <K extends @Nullable Object, V extends @Nullable Object> 1036 Collection<Entry<K, V>> unmodifiableEntries(Collection<Entry<K, V>> entries) { 1037 if (entries instanceof Set) { 1038 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries); 1039 } 1040 return new Maps.UnmodifiableEntries<>(Collections.unmodifiableCollection(entries)); 1041 } 1042 1043 /** 1044 * Returns {@link ListMultimap#asMap multimap.asMap()}, with its type corrected from {@code Map<K, 1045 * Collection<V>>} to {@code Map<K, List<V>>}. 1046 * 1047 * @since 15.0 1048 */ 1049 @Beta 1050 @SuppressWarnings("unchecked") 1051 // safe by specification of ListMultimap.asMap() 1052 public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, List<V>> asMap( 1053 ListMultimap<K, V> multimap) { 1054 return (Map<K, List<V>>) (Map<K, ?>) multimap.asMap(); 1055 } 1056 1057 /** 1058 * Returns {@link SetMultimap#asMap multimap.asMap()}, with its type corrected from {@code Map<K, 1059 * Collection<V>>} to {@code Map<K, Set<V>>}. 1060 * 1061 * @since 15.0 1062 */ 1063 @Beta 1064 @SuppressWarnings("unchecked") 1065 // safe by specification of SetMultimap.asMap() 1066 public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, Set<V>> asMap( 1067 SetMultimap<K, V> multimap) { 1068 return (Map<K, Set<V>>) (Map<K, ?>) multimap.asMap(); 1069 } 1070 1071 /** 1072 * Returns {@link SortedSetMultimap#asMap multimap.asMap()}, with its type corrected from {@code 1073 * Map<K, Collection<V>>} to {@code Map<K, SortedSet<V>>}. 1074 * 1075 * @since 15.0 1076 */ 1077 @Beta 1078 @SuppressWarnings("unchecked") 1079 // safe by specification of SortedSetMultimap.asMap() 1080 public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, SortedSet<V>> asMap( 1081 SortedSetMultimap<K, V> multimap) { 1082 return (Map<K, SortedSet<V>>) (Map<K, ?>) multimap.asMap(); 1083 } 1084 1085 /** 1086 * Returns {@link Multimap#asMap multimap.asMap()}. This is provided for parity with the other 1087 * more strongly-typed {@code asMap()} implementations. 1088 * 1089 * @since 15.0 1090 */ 1091 @Beta 1092 public static <K extends @Nullable Object, V extends @Nullable Object> 1093 Map<K, Collection<V>> asMap(Multimap<K, V> multimap) { 1094 return multimap.asMap(); 1095 } 1096 1097 /** 1098 * Returns a multimap view of the specified map. The multimap is backed by the map, so changes to 1099 * the map are reflected in the multimap, and vice versa. If the map is modified while an 1100 * iteration over one of the multimap's collection views is in progress (except through the 1101 * iterator's own {@code remove} operation, or through the {@code setValue} operation on a map 1102 * entry returned by the iterator), the results of the iteration are undefined. 1103 * 1104 * <p>The multimap supports mapping removal, which removes the corresponding mapping from the map. 1105 * It does not support any operations which might add mappings, such as {@code put}, {@code 1106 * putAll} or {@code replaceValues}. 1107 * 1108 * <p>The returned multimap will be serializable if the specified map is serializable. 1109 * 1110 * @param map the backing map for the returned multimap view 1111 */ 1112 public static <K extends @Nullable Object, V extends @Nullable Object> SetMultimap<K, V> forMap( 1113 Map<K, V> map) { 1114 return new MapMultimap<>(map); 1115 } 1116 1117 /** @see Multimaps#forMap */ 1118 private static class MapMultimap<K extends @Nullable Object, V extends @Nullable Object> 1119 extends AbstractMultimap<K, V> implements SetMultimap<K, V>, Serializable { 1120 final Map<K, V> map; 1121 1122 MapMultimap(Map<K, V> map) { 1123 this.map = checkNotNull(map); 1124 } 1125 1126 @Override 1127 public int size() { 1128 return map.size(); 1129 } 1130 1131 @Override 1132 public boolean containsKey(@CheckForNull Object key) { 1133 return map.containsKey(key); 1134 } 1135 1136 @Override 1137 public boolean containsValue(@CheckForNull Object value) { 1138 return map.containsValue(value); 1139 } 1140 1141 @Override 1142 public boolean containsEntry(@CheckForNull Object key, @CheckForNull Object value) { 1143 return map.entrySet().contains(Maps.immutableEntry(key, value)); 1144 } 1145 1146 @Override 1147 public Set<V> get(@ParametricNullness final K key) { 1148 return new Sets.ImprovedAbstractSet<V>() { 1149 @Override 1150 public Iterator<V> iterator() { 1151 return new Iterator<V>() { 1152 int i; 1153 1154 @Override 1155 public boolean hasNext() { 1156 return (i == 0) && map.containsKey(key); 1157 } 1158 1159 @Override 1160 @ParametricNullness 1161 public V next() { 1162 if (!hasNext()) { 1163 throw new NoSuchElementException(); 1164 } 1165 i++; 1166 /* 1167 * The cast is safe because of the containsKey check in hasNext(). (That means it's 1168 * unsafe under concurrent modification, but all bets are off then, anyway.) 1169 */ 1170 return uncheckedCastNullableTToT(map.get(key)); 1171 } 1172 1173 @Override 1174 public void remove() { 1175 checkRemove(i == 1); 1176 i = -1; 1177 map.remove(key); 1178 } 1179 }; 1180 } 1181 1182 @Override 1183 public int size() { 1184 return map.containsKey(key) ? 1 : 0; 1185 } 1186 }; 1187 } 1188 1189 @Override 1190 public boolean put(@ParametricNullness K key, @ParametricNullness V value) { 1191 throw new UnsupportedOperationException(); 1192 } 1193 1194 @Override 1195 public boolean putAll(@ParametricNullness K key, Iterable<? extends V> values) { 1196 throw new UnsupportedOperationException(); 1197 } 1198 1199 @Override 1200 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 1201 throw new UnsupportedOperationException(); 1202 } 1203 1204 @Override 1205 public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) { 1206 throw new UnsupportedOperationException(); 1207 } 1208 1209 @Override 1210 public boolean remove(@CheckForNull Object key, @CheckForNull Object value) { 1211 return map.entrySet().remove(Maps.immutableEntry(key, value)); 1212 } 1213 1214 @Override 1215 public Set<V> removeAll(@CheckForNull Object key) { 1216 Set<V> values = new HashSet<V>(2); 1217 if (!map.containsKey(key)) { 1218 return values; 1219 } 1220 values.add(map.remove(key)); 1221 return values; 1222 } 1223 1224 @Override 1225 public void clear() { 1226 map.clear(); 1227 } 1228 1229 @Override 1230 Set<K> createKeySet() { 1231 return map.keySet(); 1232 } 1233 1234 @Override 1235 Collection<V> createValues() { 1236 return map.values(); 1237 } 1238 1239 @Override 1240 public Set<Entry<K, V>> entries() { 1241 return map.entrySet(); 1242 } 1243 1244 @Override 1245 Collection<Entry<K, V>> createEntries() { 1246 throw new AssertionError("unreachable"); 1247 } 1248 1249 @Override 1250 Multiset<K> createKeys() { 1251 return new Multimaps.Keys<K, V>(this); 1252 } 1253 1254 @Override 1255 Iterator<Entry<K, V>> entryIterator() { 1256 return map.entrySet().iterator(); 1257 } 1258 1259 @Override 1260 Map<K, Collection<V>> createAsMap() { 1261 return new AsMap<>(this); 1262 } 1263 1264 @Override 1265 public int hashCode() { 1266 return map.hashCode(); 1267 } 1268 1269 private static final long serialVersionUID = 7845222491160860175L; 1270 } 1271 1272 /** 1273 * Returns a view of a multimap where each value is transformed by a function. All other 1274 * properties of the multimap, such as iteration order, are left intact. For example, the code: 1275 * 1276 * <pre>{@code 1277 * Multimap<String, Integer> multimap = 1278 * ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6); 1279 * Function<Integer, String> square = new Function<Integer, String>() { 1280 * public String apply(Integer in) { 1281 * return Integer.toString(in * in); 1282 * } 1283 * }; 1284 * Multimap<String, String> transformed = 1285 * Multimaps.transformValues(multimap, square); 1286 * System.out.println(transformed); 1287 * }</pre> 1288 * 1289 * ... prints {@code {a=[4, 16], b=[9, 9], c=[36]}}. 1290 * 1291 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view 1292 * supports removal operations, and these are reflected in the underlying multimap. 1293 * 1294 * <p>It's acceptable for the underlying multimap to contain null keys, and even null values 1295 * provided that the function is capable of accepting null input. The transformed multimap might 1296 * contain null values, if the function sometimes gives a null result. 1297 * 1298 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap 1299 * is. The {@code equals} and {@code hashCode} methods of the returned multimap are meaningless, 1300 * since there is not a definition of {@code equals} or {@code hashCode} for general collections, 1301 * and {@code get()} will return a general {@code Collection} as opposed to a {@code List} or a 1302 * {@code Set}. 1303 * 1304 * <p>The function is applied lazily, invoked when needed. This is necessary for the returned 1305 * multimap to be a view, but it means that the function will be applied many times for bulk 1306 * operations like {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to 1307 * perform well, {@code function} should be fast. To avoid lazy evaluation when the returned 1308 * multimap doesn't need to be a view, copy the returned multimap into a new multimap of your 1309 * choosing. 1310 * 1311 * @since 7.0 1312 */ 1313 public static < 1314 K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> 1315 Multimap<K, V2> transformValues( 1316 Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) { 1317 checkNotNull(function); 1318 EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function); 1319 return transformEntries(fromMultimap, transformer); 1320 } 1321 1322 /** 1323 * Returns a view of a {@code ListMultimap} where each value is transformed by a function. All 1324 * other properties of the multimap, such as iteration order, are left intact. For example, the 1325 * code: 1326 * 1327 * <pre>{@code 1328 * ListMultimap<String, Integer> multimap 1329 * = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9); 1330 * Function<Integer, Double> sqrt = 1331 * new Function<Integer, Double>() { 1332 * public Double apply(Integer in) { 1333 * return Math.sqrt((int) in); 1334 * } 1335 * }; 1336 * ListMultimap<String, Double> transformed = Multimaps.transformValues(map, 1337 * sqrt); 1338 * System.out.println(transformed); 1339 * }</pre> 1340 * 1341 * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}. 1342 * 1343 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view 1344 * supports removal operations, and these are reflected in the underlying multimap. 1345 * 1346 * <p>It's acceptable for the underlying multimap to contain null keys, and even null values 1347 * provided that the function is capable of accepting null input. The transformed multimap might 1348 * contain null values, if the function sometimes gives a null result. 1349 * 1350 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap 1351 * is. 1352 * 1353 * <p>The function is applied lazily, invoked when needed. This is necessary for the returned 1354 * multimap to be a view, but it means that the function will be applied many times for bulk 1355 * operations like {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to 1356 * perform well, {@code function} should be fast. To avoid lazy evaluation when the returned 1357 * multimap doesn't need to be a view, copy the returned multimap into a new multimap of your 1358 * choosing. 1359 * 1360 * @since 7.0 1361 */ 1362 public static < 1363 K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> 1364 ListMultimap<K, V2> transformValues( 1365 ListMultimap<K, V1> fromMultimap, final Function<? super V1, V2> function) { 1366 checkNotNull(function); 1367 EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function); 1368 return transformEntries(fromMultimap, transformer); 1369 } 1370 1371 /** 1372 * Returns a view of a multimap whose values are derived from the original multimap's entries. In 1373 * contrast to {@link #transformValues}, this method's entry-transformation logic may depend on 1374 * the key as well as the value. 1375 * 1376 * <p>All other properties of the transformed multimap, such as iteration order, are left intact. 1377 * For example, the code: 1378 * 1379 * <pre>{@code 1380 * SetMultimap<String, Integer> multimap = 1381 * ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6); 1382 * EntryTransformer<String, Integer, String> transformer = 1383 * new EntryTransformer<String, Integer, String>() { 1384 * public String transformEntry(String key, Integer value) { 1385 * return (value >= 0) ? key : "no" + key; 1386 * } 1387 * }; 1388 * Multimap<String, String> transformed = 1389 * Multimaps.transformEntries(multimap, transformer); 1390 * System.out.println(transformed); 1391 * }</pre> 1392 * 1393 * ... prints {@code {a=[a, a], b=[nob]}}. 1394 * 1395 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view 1396 * supports removal operations, and these are reflected in the underlying multimap. 1397 * 1398 * <p>It's acceptable for the underlying multimap to contain null keys and null values provided 1399 * that the transformer is capable of accepting null inputs. The transformed multimap might 1400 * contain null values if the transformer sometimes gives a null result. 1401 * 1402 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap 1403 * is. The {@code equals} and {@code hashCode} methods of the returned multimap are meaningless, 1404 * since there is not a definition of {@code equals} or {@code hashCode} for general collections, 1405 * and {@code get()} will return a general {@code Collection} as opposed to a {@code List} or a 1406 * {@code Set}. 1407 * 1408 * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned 1409 * multimap to be a view, but it means that the transformer will be applied many times for bulk 1410 * operations like {@link Multimap#containsValue} and {@link Object#toString}. For this to perform 1411 * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned multimap 1412 * doesn't need to be a view, copy the returned multimap into a new multimap of your choosing. 1413 * 1414 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code 1415 * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of 1416 * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as 1417 * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the 1418 * transformed multimap. 1419 * 1420 * @since 7.0 1421 */ 1422 public static < 1423 K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> 1424 Multimap<K, V2> transformEntries( 1425 Multimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) { 1426 return new TransformedEntriesMultimap<>(fromMap, transformer); 1427 } 1428 1429 /** 1430 * Returns a view of a {@code ListMultimap} whose values are derived from the original multimap's 1431 * entries. In contrast to {@link #transformValues(ListMultimap, Function)}, this method's 1432 * entry-transformation logic may depend on the key as well as the value. 1433 * 1434 * <p>All other properties of the transformed multimap, such as iteration order, are left intact. 1435 * For example, the code: 1436 * 1437 * <pre>{@code 1438 * Multimap<String, Integer> multimap = 1439 * ImmutableMultimap.of("a", 1, "a", 4, "b", 6); 1440 * EntryTransformer<String, Integer, String> transformer = 1441 * new EntryTransformer<String, Integer, String>() { 1442 * public String transformEntry(String key, Integer value) { 1443 * return key + value; 1444 * } 1445 * }; 1446 * Multimap<String, String> transformed = 1447 * Multimaps.transformEntries(multimap, transformer); 1448 * System.out.println(transformed); 1449 * }</pre> 1450 * 1451 * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}. 1452 * 1453 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view 1454 * supports removal operations, and these are reflected in the underlying multimap. 1455 * 1456 * <p>It's acceptable for the underlying multimap to contain null keys and null values provided 1457 * that the transformer is capable of accepting null inputs. The transformed multimap might 1458 * contain null values if the transformer sometimes gives a null result. 1459 * 1460 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap 1461 * is. 1462 * 1463 * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned 1464 * multimap to be a view, but it means that the transformer will be applied many times for bulk 1465 * operations like {@link Multimap#containsValue} and {@link Object#toString}. For this to perform 1466 * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned multimap 1467 * doesn't need to be a view, copy the returned multimap into a new multimap of your choosing. 1468 * 1469 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code 1470 * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of 1471 * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as 1472 * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the 1473 * transformed multimap. 1474 * 1475 * @since 7.0 1476 */ 1477 public static < 1478 K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> 1479 ListMultimap<K, V2> transformEntries( 1480 ListMultimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) { 1481 return new TransformedEntriesListMultimap<>(fromMap, transformer); 1482 } 1483 1484 private static class TransformedEntriesMultimap< 1485 K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> 1486 extends AbstractMultimap<K, V2> { 1487 final Multimap<K, V1> fromMultimap; 1488 final EntryTransformer<? super K, ? super V1, V2> transformer; 1489 1490 TransformedEntriesMultimap( 1491 Multimap<K, V1> fromMultimap, 1492 final EntryTransformer<? super K, ? super V1, V2> transformer) { 1493 this.fromMultimap = checkNotNull(fromMultimap); 1494 this.transformer = checkNotNull(transformer); 1495 } 1496 1497 Collection<V2> transform(@ParametricNullness K key, Collection<V1> values) { 1498 Function<? super V1, V2> function = Maps.asValueToValueFunction(transformer, key); 1499 if (values instanceof List) { 1500 return Lists.transform((List<V1>) values, function); 1501 } else { 1502 return Collections2.transform(values, function); 1503 } 1504 } 1505 1506 @Override 1507 Map<K, Collection<V2>> createAsMap() { 1508 return Maps.transformEntries( 1509 fromMultimap.asMap(), 1510 new EntryTransformer<K, Collection<V1>, Collection<V2>>() { 1511 @Override 1512 public Collection<V2> transformEntry(@ParametricNullness K key, Collection<V1> value) { 1513 return transform(key, value); 1514 } 1515 }); 1516 } 1517 1518 @Override 1519 public void clear() { 1520 fromMultimap.clear(); 1521 } 1522 1523 @Override 1524 public boolean containsKey(@CheckForNull Object key) { 1525 return fromMultimap.containsKey(key); 1526 } 1527 1528 @Override 1529 Collection<Entry<K, V2>> createEntries() { 1530 return new Entries(); 1531 } 1532 1533 @Override 1534 Iterator<Entry<K, V2>> entryIterator() { 1535 return Iterators.transform( 1536 fromMultimap.entries().iterator(), Maps.<K, V1, V2>asEntryToEntryFunction(transformer)); 1537 } 1538 1539 @Override 1540 public Collection<V2> get(@ParametricNullness final K key) { 1541 return transform(key, fromMultimap.get(key)); 1542 } 1543 1544 @Override 1545 public boolean isEmpty() { 1546 return fromMultimap.isEmpty(); 1547 } 1548 1549 @Override 1550 Set<K> createKeySet() { 1551 return fromMultimap.keySet(); 1552 } 1553 1554 @Override 1555 Multiset<K> createKeys() { 1556 return fromMultimap.keys(); 1557 } 1558 1559 @Override 1560 public boolean put(@ParametricNullness K key, @ParametricNullness V2 value) { 1561 throw new UnsupportedOperationException(); 1562 } 1563 1564 @Override 1565 public boolean putAll(@ParametricNullness K key, Iterable<? extends V2> values) { 1566 throw new UnsupportedOperationException(); 1567 } 1568 1569 @Override 1570 public boolean putAll(Multimap<? extends K, ? extends V2> multimap) { 1571 throw new UnsupportedOperationException(); 1572 } 1573 1574 @SuppressWarnings("unchecked") 1575 @Override 1576 public boolean remove(@CheckForNull Object key, @CheckForNull Object value) { 1577 return get((K) key).remove(value); 1578 } 1579 1580 @SuppressWarnings("unchecked") 1581 @Override 1582 public Collection<V2> removeAll(@CheckForNull Object key) { 1583 return transform((K) key, fromMultimap.removeAll(key)); 1584 } 1585 1586 @Override 1587 public Collection<V2> replaceValues(@ParametricNullness K key, Iterable<? extends V2> values) { 1588 throw new UnsupportedOperationException(); 1589 } 1590 1591 @Override 1592 public int size() { 1593 return fromMultimap.size(); 1594 } 1595 1596 @Override 1597 Collection<V2> createValues() { 1598 return Collections2.transform( 1599 fromMultimap.entries(), Maps.<K, V1, V2>asEntryToValueFunction(transformer)); 1600 } 1601 } 1602 1603 private static final class TransformedEntriesListMultimap< 1604 K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> 1605 extends TransformedEntriesMultimap<K, V1, V2> implements ListMultimap<K, V2> { 1606 1607 TransformedEntriesListMultimap( 1608 ListMultimap<K, V1> fromMultimap, EntryTransformer<? super K, ? super V1, V2> transformer) { 1609 super(fromMultimap, transformer); 1610 } 1611 1612 @Override 1613 List<V2> transform(@ParametricNullness K key, Collection<V1> values) { 1614 return Lists.transform((List<V1>) values, Maps.asValueToValueFunction(transformer, key)); 1615 } 1616 1617 @Override 1618 public List<V2> get(@ParametricNullness K key) { 1619 return transform(key, fromMultimap.get(key)); 1620 } 1621 1622 @SuppressWarnings("unchecked") 1623 @Override 1624 public List<V2> removeAll(@CheckForNull Object key) { 1625 return transform((K) key, fromMultimap.removeAll(key)); 1626 } 1627 1628 @Override 1629 public List<V2> replaceValues(@ParametricNullness K key, Iterable<? extends V2> values) { 1630 throw new UnsupportedOperationException(); 1631 } 1632 } 1633 1634 /** 1635 * Creates an index {@code ImmutableListMultimap} that contains the results of applying a 1636 * specified function to each item in an {@code Iterable} of values. Each value will be stored as 1637 * a value in the resulting multimap, yielding a multimap with the same size as the input 1638 * iterable. The key used to store that value in the multimap will be the result of calling the 1639 * function on that value. The resulting multimap is created as an immutable snapshot. In the 1640 * returned multimap, keys appear in the order they are first encountered, and the values 1641 * corresponding to each key appear in the same order as they are encountered. 1642 * 1643 * <p>For example, 1644 * 1645 * <pre>{@code 1646 * List<String> badGuys = 1647 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde"); 1648 * Function<String, Integer> stringLengthFunction = ...; 1649 * Multimap<Integer, String> index = 1650 * Multimaps.index(badGuys, stringLengthFunction); 1651 * System.out.println(index); 1652 * }</pre> 1653 * 1654 * <p>prints 1655 * 1656 * <pre>{@code 1657 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]} 1658 * }</pre> 1659 * 1660 * <p>The returned multimap is serializable if its keys and values are all serializable. 1661 * 1662 * @param values the values to use when constructing the {@code ImmutableListMultimap} 1663 * @param keyFunction the function used to produce the key for each value 1664 * @return {@code ImmutableListMultimap} mapping the result of evaluating the function {@code 1665 * keyFunction} on each value in the input collection to that value 1666 * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code 1667 * keyFunction} produces {@code null} for any key 1668 */ 1669 public static <K, V> ImmutableListMultimap<K, V> index( 1670 Iterable<V> values, Function<? super V, K> keyFunction) { 1671 return index(values.iterator(), keyFunction); 1672 } 1673 1674 /** 1675 * Creates an index {@code ImmutableListMultimap} that contains the results of applying a 1676 * specified function to each item in an {@code Iterator} of values. Each value will be stored as 1677 * a value in the resulting multimap, yielding a multimap with the same size as the input 1678 * iterator. The key used to store that value in the multimap will be the result of calling the 1679 * function on that value. The resulting multimap is created as an immutable snapshot. In the 1680 * returned multimap, keys appear in the order they are first encountered, and the values 1681 * corresponding to each key appear in the same order as they are encountered. 1682 * 1683 * <p>For example, 1684 * 1685 * <pre>{@code 1686 * List<String> badGuys = 1687 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde"); 1688 * Function<String, Integer> stringLengthFunction = ...; 1689 * Multimap<Integer, String> index = 1690 * Multimaps.index(badGuys.iterator(), stringLengthFunction); 1691 * System.out.println(index); 1692 * }</pre> 1693 * 1694 * <p>prints 1695 * 1696 * <pre>{@code 1697 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]} 1698 * }</pre> 1699 * 1700 * <p>The returned multimap is serializable if its keys and values are all serializable. 1701 * 1702 * @param values the values to use when constructing the {@code ImmutableListMultimap} 1703 * @param keyFunction the function used to produce the key for each value 1704 * @return {@code ImmutableListMultimap} mapping the result of evaluating the function {@code 1705 * keyFunction} on each value in the input collection to that value 1706 * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code 1707 * keyFunction} produces {@code null} for any key 1708 * @since 10.0 1709 */ 1710 public static <K, V> ImmutableListMultimap<K, V> index( 1711 Iterator<V> values, Function<? super V, K> keyFunction) { 1712 checkNotNull(keyFunction); 1713 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 1714 while (values.hasNext()) { 1715 V value = values.next(); 1716 checkNotNull(value, values); 1717 builder.put(keyFunction.apply(value), value); 1718 } 1719 return builder.build(); 1720 } 1721 1722 static class Keys<K extends @Nullable Object, V extends @Nullable Object> 1723 extends AbstractMultiset<K> { 1724 @Weak final Multimap<K, V> multimap; 1725 1726 Keys(Multimap<K, V> multimap) { 1727 this.multimap = multimap; 1728 } 1729 1730 @Override 1731 Iterator<Multiset.Entry<K>> entryIterator() { 1732 return new TransformedIterator<Map.Entry<K, Collection<V>>, Multiset.Entry<K>>( 1733 multimap.asMap().entrySet().iterator()) { 1734 @Override 1735 Multiset.Entry<K> transform(final Map.Entry<K, Collection<V>> backingEntry) { 1736 return new Multisets.AbstractEntry<K>() { 1737 @Override 1738 @ParametricNullness 1739 public K getElement() { 1740 return backingEntry.getKey(); 1741 } 1742 1743 @Override 1744 public int getCount() { 1745 return backingEntry.getValue().size(); 1746 } 1747 }; 1748 } 1749 }; 1750 } 1751 1752 @Override 1753 public Spliterator<K> spliterator() { 1754 return CollectSpliterators.map(multimap.entries().spliterator(), Map.Entry::getKey); 1755 } 1756 1757 @Override 1758 public void forEach(Consumer<? super K> consumer) { 1759 checkNotNull(consumer); 1760 multimap.entries().forEach(entry -> consumer.accept(entry.getKey())); 1761 } 1762 1763 @Override 1764 int distinctElements() { 1765 return multimap.asMap().size(); 1766 } 1767 1768 @Override 1769 public int size() { 1770 return multimap.size(); 1771 } 1772 1773 @Override 1774 public boolean contains(@CheckForNull Object element) { 1775 return multimap.containsKey(element); 1776 } 1777 1778 @Override 1779 public Iterator<K> iterator() { 1780 return Maps.keyIterator(multimap.entries().iterator()); 1781 } 1782 1783 @Override 1784 public int count(@CheckForNull Object element) { 1785 Collection<V> values = Maps.safeGet(multimap.asMap(), element); 1786 return (values == null) ? 0 : values.size(); 1787 } 1788 1789 @Override 1790 public int remove(@CheckForNull Object element, int occurrences) { 1791 checkNonnegative(occurrences, "occurrences"); 1792 if (occurrences == 0) { 1793 return count(element); 1794 } 1795 1796 Collection<V> values = Maps.safeGet(multimap.asMap(), element); 1797 1798 if (values == null) { 1799 return 0; 1800 } 1801 1802 int oldCount = values.size(); 1803 if (occurrences >= oldCount) { 1804 values.clear(); 1805 } else { 1806 Iterator<V> iterator = values.iterator(); 1807 for (int i = 0; i < occurrences; i++) { 1808 iterator.next(); 1809 iterator.remove(); 1810 } 1811 } 1812 return oldCount; 1813 } 1814 1815 @Override 1816 public void clear() { 1817 multimap.clear(); 1818 } 1819 1820 @Override 1821 public Set<K> elementSet() { 1822 return multimap.keySet(); 1823 } 1824 1825 @Override 1826 Iterator<K> elementIterator() { 1827 throw new AssertionError("should never be called"); 1828 } 1829 } 1830 1831 /** A skeleton implementation of {@link Multimap#entries()}. */ 1832 abstract static class Entries<K extends @Nullable Object, V extends @Nullable Object> 1833 extends AbstractCollection<Map.Entry<K, V>> { 1834 abstract Multimap<K, V> multimap(); 1835 1836 @Override 1837 public int size() { 1838 return multimap().size(); 1839 } 1840 1841 @Override 1842 public boolean contains(@CheckForNull Object o) { 1843 if (o instanceof Map.Entry) { 1844 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1845 return multimap().containsEntry(entry.getKey(), entry.getValue()); 1846 } 1847 return false; 1848 } 1849 1850 @Override 1851 public boolean remove(@CheckForNull Object o) { 1852 if (o instanceof Map.Entry) { 1853 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1854 return multimap().remove(entry.getKey(), entry.getValue()); 1855 } 1856 return false; 1857 } 1858 1859 @Override 1860 public void clear() { 1861 multimap().clear(); 1862 } 1863 } 1864 1865 /** A skeleton implementation of {@link Multimap#asMap()}. */ 1866 static final class AsMap<K extends @Nullable Object, V extends @Nullable Object> 1867 extends Maps.ViewCachingAbstractMap<K, Collection<V>> { 1868 @Weak private final Multimap<K, V> multimap; 1869 1870 AsMap(Multimap<K, V> multimap) { 1871 this.multimap = checkNotNull(multimap); 1872 } 1873 1874 @Override 1875 public int size() { 1876 return multimap.keySet().size(); 1877 } 1878 1879 @Override 1880 protected Set<Entry<K, Collection<V>>> createEntrySet() { 1881 return new EntrySet(); 1882 } 1883 1884 void removeValuesForKey(@CheckForNull Object key) { 1885 multimap.keySet().remove(key); 1886 } 1887 1888 @WeakOuter 1889 class EntrySet extends Maps.EntrySet<K, Collection<V>> { 1890 @Override 1891 Map<K, Collection<V>> map() { 1892 return AsMap.this; 1893 } 1894 1895 @Override 1896 public Iterator<Entry<K, Collection<V>>> iterator() { 1897 return Maps.asMapEntryIterator( 1898 multimap.keySet(), 1899 new Function<K, Collection<V>>() { 1900 @Override 1901 public Collection<V> apply(@ParametricNullness K key) { 1902 return multimap.get(key); 1903 } 1904 }); 1905 } 1906 1907 @Override 1908 public boolean remove(@CheckForNull Object o) { 1909 if (!contains(o)) { 1910 return false; 1911 } 1912 // requireNonNull is safe because of the contains check. 1913 Map.Entry<?, ?> entry = requireNonNull((Map.Entry<?, ?>) o); 1914 removeValuesForKey(entry.getKey()); 1915 return true; 1916 } 1917 } 1918 1919 @SuppressWarnings("unchecked") 1920 @Override 1921 @CheckForNull 1922 public Collection<V> get(@CheckForNull Object key) { 1923 return containsKey(key) ? multimap.get((K) key) : null; 1924 } 1925 1926 @Override 1927 @CheckForNull 1928 public Collection<V> remove(@CheckForNull Object key) { 1929 return containsKey(key) ? multimap.removeAll(key) : null; 1930 } 1931 1932 @Override 1933 public Set<K> keySet() { 1934 return multimap.keySet(); 1935 } 1936 1937 @Override 1938 public boolean isEmpty() { 1939 return multimap.isEmpty(); 1940 } 1941 1942 @Override 1943 public boolean containsKey(@CheckForNull Object key) { 1944 return multimap.containsKey(key); 1945 } 1946 1947 @Override 1948 public void clear() { 1949 multimap.clear(); 1950 } 1951 } 1952 1953 /** 1954 * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a 1955 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect 1956 * the other. 1957 * 1958 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 1959 * other methods are supported by the multimap and its views. When adding a key that doesn't 1960 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code 1961 * replaceValues()} methods throw an {@link IllegalArgumentException}. 1962 * 1963 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 1964 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the 1965 * underlying multimap. 1966 * 1967 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 1968 * 1969 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 1970 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 1971 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 1972 * copy. 1973 * 1974 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at 1975 * {@link Predicate#apply}. Do not provide a predicate such as {@code 1976 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. 1977 * 1978 * @since 11.0 1979 */ 1980 public static <K extends @Nullable Object, V extends @Nullable Object> Multimap<K, V> filterKeys( 1981 Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { 1982 if (unfiltered instanceof SetMultimap) { 1983 return filterKeys((SetMultimap<K, V>) unfiltered, keyPredicate); 1984 } else if (unfiltered instanceof ListMultimap) { 1985 return filterKeys((ListMultimap<K, V>) unfiltered, keyPredicate); 1986 } else if (unfiltered instanceof FilteredKeyMultimap) { 1987 FilteredKeyMultimap<K, V> prev = (FilteredKeyMultimap<K, V>) unfiltered; 1988 return new FilteredKeyMultimap<>( 1989 prev.unfiltered, Predicates.<K>and(prev.keyPredicate, keyPredicate)); 1990 } else if (unfiltered instanceof FilteredMultimap) { 1991 FilteredMultimap<K, V> prev = (FilteredMultimap<K, V>) unfiltered; 1992 return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate)); 1993 } else { 1994 return new FilteredKeyMultimap<>(unfiltered, keyPredicate); 1995 } 1996 } 1997 1998 /** 1999 * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a 2000 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect 2001 * the other. 2002 * 2003 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 2004 * other methods are supported by the multimap and its views. When adding a key that doesn't 2005 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code 2006 * replaceValues()} methods throw an {@link IllegalArgumentException}. 2007 * 2008 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 2009 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the 2010 * underlying multimap. 2011 * 2012 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 2013 * 2014 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 2015 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 2016 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 2017 * copy. 2018 * 2019 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at 2020 * {@link Predicate#apply}. Do not provide a predicate such as {@code 2021 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. 2022 * 2023 * @since 14.0 2024 */ 2025 public static <K extends @Nullable Object, V extends @Nullable Object> 2026 SetMultimap<K, V> filterKeys( 2027 SetMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { 2028 if (unfiltered instanceof FilteredKeySetMultimap) { 2029 FilteredKeySetMultimap<K, V> prev = (FilteredKeySetMultimap<K, V>) unfiltered; 2030 return new FilteredKeySetMultimap<>( 2031 prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate)); 2032 } else if (unfiltered instanceof FilteredSetMultimap) { 2033 FilteredSetMultimap<K, V> prev = (FilteredSetMultimap<K, V>) unfiltered; 2034 return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate)); 2035 } else { 2036 return new FilteredKeySetMultimap<>(unfiltered, keyPredicate); 2037 } 2038 } 2039 2040 /** 2041 * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a 2042 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect 2043 * the other. 2044 * 2045 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 2046 * other methods are supported by the multimap and its views. When adding a key that doesn't 2047 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code 2048 * replaceValues()} methods throw an {@link IllegalArgumentException}. 2049 * 2050 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 2051 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the 2052 * underlying multimap. 2053 * 2054 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 2055 * 2056 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 2057 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 2058 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 2059 * copy. 2060 * 2061 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at 2062 * {@link Predicate#apply}. Do not provide a predicate such as {@code 2063 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. 2064 * 2065 * @since 14.0 2066 */ 2067 public static <K extends @Nullable Object, V extends @Nullable Object> 2068 ListMultimap<K, V> filterKeys( 2069 ListMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { 2070 if (unfiltered instanceof FilteredKeyListMultimap) { 2071 FilteredKeyListMultimap<K, V> prev = (FilteredKeyListMultimap<K, V>) unfiltered; 2072 return new FilteredKeyListMultimap<>( 2073 prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate)); 2074 } else { 2075 return new FilteredKeyListMultimap<>(unfiltered, keyPredicate); 2076 } 2077 } 2078 2079 /** 2080 * Returns a multimap containing the mappings in {@code unfiltered} whose values satisfy a 2081 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect 2082 * the other. 2083 * 2084 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 2085 * other methods are supported by the multimap and its views. When adding a value that doesn't 2086 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code 2087 * replaceValues()} methods throw an {@link IllegalArgumentException}. 2088 * 2089 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 2090 * multimap or its views, only mappings whose value satisfy the filter will be removed from the 2091 * underlying multimap. 2092 * 2093 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 2094 * 2095 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 2096 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 2097 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 2098 * copy. 2099 * 2100 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented 2101 * at {@link Predicate#apply}. Do not provide a predicate such as {@code 2102 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. 2103 * 2104 * @since 11.0 2105 */ 2106 public static <K extends @Nullable Object, V extends @Nullable Object> 2107 Multimap<K, V> filterValues( 2108 Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) { 2109 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate)); 2110 } 2111 2112 /** 2113 * Returns a multimap containing the mappings in {@code unfiltered} whose values satisfy a 2114 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect 2115 * the other. 2116 * 2117 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 2118 * other methods are supported by the multimap and its views. When adding a value that doesn't 2119 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code 2120 * replaceValues()} methods throw an {@link IllegalArgumentException}. 2121 * 2122 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 2123 * multimap or its views, only mappings whose value satisfy the filter will be removed from the 2124 * underlying multimap. 2125 * 2126 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 2127 * 2128 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 2129 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 2130 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 2131 * copy. 2132 * 2133 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented 2134 * at {@link Predicate#apply}. Do not provide a predicate such as {@code 2135 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. 2136 * 2137 * @since 14.0 2138 */ 2139 public static <K extends @Nullable Object, V extends @Nullable Object> 2140 SetMultimap<K, V> filterValues( 2141 SetMultimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) { 2142 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate)); 2143 } 2144 2145 /** 2146 * Returns a multimap containing the mappings in {@code unfiltered} that satisfy a predicate. The 2147 * returned multimap is a live view of {@code unfiltered}; changes to one affect the other. 2148 * 2149 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 2150 * other methods are supported by the multimap and its views. When adding a key/value pair that 2151 * doesn't satisfy the predicate, multimap's {@code put()}, {@code putAll()}, and {@code 2152 * replaceValues()} methods throw an {@link IllegalArgumentException}. 2153 * 2154 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 2155 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the 2156 * underlying multimap. 2157 * 2158 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 2159 * 2160 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 2161 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 2162 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 2163 * copy. 2164 * 2165 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented 2166 * at {@link Predicate#apply}. 2167 * 2168 * @since 11.0 2169 */ 2170 public static <K extends @Nullable Object, V extends @Nullable Object> 2171 Multimap<K, V> filterEntries( 2172 Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) { 2173 checkNotNull(entryPredicate); 2174 if (unfiltered instanceof SetMultimap) { 2175 return filterEntries((SetMultimap<K, V>) unfiltered, entryPredicate); 2176 } 2177 return (unfiltered instanceof FilteredMultimap) 2178 ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate) 2179 : new FilteredEntryMultimap<K, V>(checkNotNull(unfiltered), entryPredicate); 2180 } 2181 2182 /** 2183 * Returns a multimap containing the mappings in {@code unfiltered} that satisfy a predicate. The 2184 * returned multimap is a live view of {@code unfiltered}; changes to one affect the other. 2185 * 2186 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all 2187 * other methods are supported by the multimap and its views. When adding a key/value pair that 2188 * doesn't satisfy the predicate, multimap's {@code put()}, {@code putAll()}, and {@code 2189 * replaceValues()} methods throw an {@link IllegalArgumentException}. 2190 * 2191 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered 2192 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the 2193 * underlying multimap. 2194 * 2195 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is. 2196 * 2197 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every 2198 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a 2199 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the 2200 * copy. 2201 * 2202 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented 2203 * at {@link Predicate#apply}. 2204 * 2205 * @since 14.0 2206 */ 2207 public static <K extends @Nullable Object, V extends @Nullable Object> 2208 SetMultimap<K, V> filterEntries( 2209 SetMultimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) { 2210 checkNotNull(entryPredicate); 2211 return (unfiltered instanceof FilteredSetMultimap) 2212 ? filterFiltered((FilteredSetMultimap<K, V>) unfiltered, entryPredicate) 2213 : new FilteredEntrySetMultimap<K, V>(checkNotNull(unfiltered), entryPredicate); 2214 } 2215 2216 /** 2217 * Support removal operations when filtering a filtered multimap. Since a filtered multimap has 2218 * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would 2219 * lead to a multimap whose removal operations would fail. This method combines the predicates to 2220 * avoid that problem. 2221 */ 2222 private static <K extends @Nullable Object, V extends @Nullable Object> 2223 Multimap<K, V> filterFiltered( 2224 FilteredMultimap<K, V> multimap, Predicate<? super Entry<K, V>> entryPredicate) { 2225 Predicate<Entry<K, V>> predicate = 2226 Predicates.<Entry<K, V>>and(multimap.entryPredicate(), entryPredicate); 2227 return new FilteredEntryMultimap<>(multimap.unfiltered(), predicate); 2228 } 2229 2230 /** 2231 * Support removal operations when filtering a filtered multimap. Since a filtered multimap has 2232 * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would 2233 * lead to a multimap whose removal operations would fail. This method combines the predicates to 2234 * avoid that problem. 2235 */ 2236 private static <K extends @Nullable Object, V extends @Nullable Object> 2237 SetMultimap<K, V> filterFiltered( 2238 FilteredSetMultimap<K, V> multimap, Predicate<? super Entry<K, V>> entryPredicate) { 2239 Predicate<Entry<K, V>> predicate = 2240 Predicates.<Entry<K, V>>and(multimap.entryPredicate(), entryPredicate); 2241 return new FilteredEntrySetMultimap<>(multimap.unfiltered(), predicate); 2242 } 2243 2244 static boolean equalsImpl(Multimap<?, ?> multimap, @CheckForNull Object object) { 2245 if (object == multimap) { 2246 return true; 2247 } 2248 if (object instanceof Multimap) { 2249 Multimap<?, ?> that = (Multimap<?, ?>) object; 2250 return multimap.asMap().equals(that.asMap()); 2251 } 2252 return false; 2253 } 2254 2255 // TODO(jlevy): Create methods that filter a SortedSetMultimap. 2256}