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