1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.base.Preconditions.checkNotNull; 21import static com.google.common.base.Preconditions.checkState; 22 23import com.google.common.annotations.Beta; 24import com.google.common.annotations.GwtCompatible; 25import com.google.common.base.Function; 26import com.google.common.base.Joiner; 27import com.google.common.base.Joiner.MapJoiner; 28import com.google.common.base.Objects; 29import com.google.common.base.Predicate; 30import com.google.common.base.Predicates; 31import com.google.common.base.Supplier; 32import com.google.common.collect.Collections2.TransformedCollection; 33import com.google.common.collect.Maps.EntryTransformer; 34 35import java.io.Serializable; 36import java.util.AbstractCollection; 37import java.util.AbstractSet; 38import java.util.Collection; 39import java.util.Collections; 40import java.util.Comparator; 41import java.util.HashSet; 42import java.util.Iterator; 43import java.util.List; 44import java.util.Map; 45import java.util.Map.Entry; 46import java.util.NoSuchElementException; 47import java.util.Set; 48import java.util.SortedSet; 49 50import javax.annotation.Nullable; 51 52/** 53 * Provides static methods acting on or generating a {@code Multimap}. 54 * 55 * @author Jared Levy 56 * @author Robert Konigsberg 57 * @author Mike Bostock 58 * @author Louis Wasserman 59 * @since 2.0 (imported from Google Collections Library) 60 */ 61@GwtCompatible(emulated = true) 62public final class Multimaps { 63 private Multimaps() {} 64 65 /** 66 * Creates a new {@code Multimap} that uses the provided map and factory. It 67 * can generate a multimap based on arbitrary {@link Map} and 68 * {@link Collection} classes. 69 * 70 * <p>The {@code factory}-generated and {@code map} classes determine the 71 * multimap iteration order. They also specify the behavior of the 72 * {@code equals}, {@code hashCode}, and {@code toString} methods for the 73 * multimap and its returned views. However, the multimap's {@code get} 74 * method returns instances of a different class than {@code factory.get()} 75 * does. 76 * 77 * <p>The multimap is serializable if {@code map}, {@code factory}, the 78 * collections generated by {@code factory}, and the multimap contents are all 79 * serializable. 80 * 81 * <p>The multimap is not threadsafe when any concurrent operations update the 82 * multimap, even if {@code map} and the instances generated by 83 * {@code factory} are. Concurrent read operations will work correctly. To 84 * allow concurrent update operations, wrap the multimap with a call to 85 * {@link #synchronizedMultimap}. 86 * 87 * <p>Call this method only when the simpler methods 88 * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()}, 89 * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()}, 90 * {@link TreeMultimap#create()}, and 91 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice. 92 * 93 * <p>Note: the multimap assumes complete ownership over of {@code map} and 94 * the collections returned by {@code factory}. Those objects should not be 95 * manually updated and they should not use soft, weak, or phantom references. 96 * 97 * @param map place to store the mapping from each key to its corresponding 98 * values 99 * @param factory supplier of new, empty collections that will each hold all 100 * values for a given key 101 * @throws IllegalArgumentException if {@code map} is not empty 102 */ 103 public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map, 104 final Supplier<? extends Collection<V>> factory) { 105 return new CustomMultimap<K, V>(map, factory); 106 } 107 108 private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> { 109 transient Supplier<? extends Collection<V>> factory; 110 111 CustomMultimap(Map<K, Collection<V>> map, 112 Supplier<? extends Collection<V>> factory) { 113 super(map); 114 this.factory = checkNotNull(factory); 115 } 116 117 @Override protected Collection<V> createCollection() { 118 return factory.get(); 119 } 120 121 // can't use Serialization writeMultimap and populateMultimap methods since 122 // there's no way to generate the empty backing map. 123 } 124 125 /** 126 * Creates a new {@code ListMultimap} that uses the provided map and factory. 127 * It can generate a multimap based on arbitrary {@link Map} and {@link List} 128 * classes. 129 * 130 * <p>The {@code factory}-generated and {@code map} classes determine the 131 * multimap iteration order. They also specify the behavior of the 132 * {@code equals}, {@code hashCode}, and {@code toString} methods for the 133 * multimap and its returned views. The multimap's {@code get}, {@code 134 * removeAll}, and {@code replaceValues} methods return {@code RandomAccess} 135 * lists if the factory does. However, the multimap's {@code get} method 136 * returns instances of a different class than does {@code factory.get()}. 137 * 138 * <p>The multimap is serializable if {@code map}, {@code factory}, the 139 * lists generated by {@code factory}, and the multimap contents are all 140 * serializable. 141 * 142 * <p>The multimap is not threadsafe when any concurrent operations update the 143 * multimap, even if {@code map} and the instances generated by 144 * {@code factory} are. Concurrent read operations will work correctly. To 145 * allow concurrent update operations, wrap the multimap with a call to 146 * {@link #synchronizedListMultimap}. 147 * 148 * <p>Call this method only when the simpler methods 149 * {@link ArrayListMultimap#create()} and {@link LinkedListMultimap#create()} 150 * won't suffice. 151 * 152 * <p>Note: the multimap assumes complete ownership over of {@code map} and 153 * the lists returned by {@code factory}. Those objects should not be manually 154 * updated, they should be empty when provided, and they should not use soft, 155 * weak, or phantom references. 156 * 157 * @param map place to store the mapping from each key to its corresponding 158 * values 159 * @param factory supplier of new, empty lists that will each hold all values 160 * for a given key 161 * @throws IllegalArgumentException if {@code map} is not empty 162 */ 163 public static <K, V> ListMultimap<K, V> newListMultimap( 164 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) { 165 return new CustomListMultimap<K, V>(map, factory); 166 } 167 168 private static class CustomListMultimap<K, V> 169 extends AbstractListMultimap<K, V> { 170 transient Supplier<? extends List<V>> factory; 171 172 CustomListMultimap(Map<K, Collection<V>> map, 173 Supplier<? extends List<V>> factory) { 174 super(map); 175 this.factory = checkNotNull(factory); 176 } 177 178 @Override protected List<V> createCollection() { 179 return factory.get(); 180 } 181 } 182 183 /** 184 * Creates a new {@code SetMultimap} that uses the provided map and factory. 185 * It can generate a multimap based on arbitrary {@link Map} and {@link Set} 186 * classes. 187 * 188 * <p>The {@code factory}-generated and {@code map} classes determine the 189 * multimap iteration order. They also specify the behavior of the 190 * {@code equals}, {@code hashCode}, and {@code toString} methods for the 191 * multimap and its returned views. However, the multimap's {@code get} 192 * method returns instances of a different class than {@code factory.get()} 193 * does. 194 * 195 * <p>The multimap is serializable if {@code map}, {@code factory}, the 196 * sets generated by {@code factory}, and the multimap contents are all 197 * serializable. 198 * 199 * <p>The multimap is not threadsafe when any concurrent operations update the 200 * multimap, even if {@code map} and the instances generated by 201 * {@code factory} are. Concurrent read operations will work correctly. To 202 * allow concurrent update operations, wrap the multimap with a call to 203 * {@link #synchronizedSetMultimap}. 204 * 205 * <p>Call this method only when the simpler methods 206 * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()}, 207 * {@link TreeMultimap#create()}, and 208 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice. 209 * 210 * <p>Note: the multimap assumes complete ownership over of {@code map} and 211 * the sets returned by {@code factory}. Those objects should not be manually 212 * updated and they should not use soft, weak, or phantom references. 213 * 214 * @param map place to store the mapping from each key to its corresponding 215 * values 216 * @param factory supplier of new, empty sets that will each hold all values 217 * for a given key 218 * @throws IllegalArgumentException if {@code map} is not empty 219 */ 220 public static <K, V> SetMultimap<K, V> newSetMultimap( 221 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) { 222 return new CustomSetMultimap<K, V>(map, factory); 223 } 224 225 private static class CustomSetMultimap<K, V> 226 extends AbstractSetMultimap<K, V> { 227 transient Supplier<? extends Set<V>> factory; 228 229 CustomSetMultimap(Map<K, Collection<V>> map, 230 Supplier<? extends Set<V>> factory) { 231 super(map); 232 this.factory = checkNotNull(factory); 233 } 234 235 @Override protected Set<V> createCollection() { 236 return factory.get(); 237 } 238 } 239 240 /** 241 * Creates a new {@code SortedSetMultimap} that uses the provided map and 242 * factory. It can generate a multimap based on arbitrary {@link Map} and 243 * {@link SortedSet} classes. 244 * 245 * <p>The {@code factory}-generated and {@code map} classes determine the 246 * multimap iteration order. They also specify the behavior of the 247 * {@code equals}, {@code hashCode}, and {@code toString} methods for the 248 * multimap and its returned views. However, the multimap's {@code get} 249 * method returns instances of a different class than {@code factory.get()} 250 * does. 251 * 252 * <p>The multimap is serializable if {@code map}, {@code factory}, the 253 * sets generated by {@code factory}, and the multimap contents are all 254 * serializable. 255 * 256 * <p>The multimap is not threadsafe when any concurrent operations update the 257 * multimap, even if {@code map} and the instances generated by 258 * {@code factory} are. Concurrent read operations will work correctly. To 259 * allow concurrent update operations, wrap the multimap with a call to 260 * {@link #synchronizedSortedSetMultimap}. 261 * 262 * <p>Call this method only when the simpler methods 263 * {@link TreeMultimap#create()} and 264 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice. 265 * 266 * <p>Note: the multimap assumes complete ownership over of {@code map} and 267 * the sets returned by {@code factory}. Those objects should not be manually 268 * updated and they should not use soft, weak, or phantom references. 269 * 270 * @param map place to store the mapping from each key to its corresponding 271 * values 272 * @param factory supplier of new, empty sorted sets that will each hold 273 * all values for a given key 274 * @throws IllegalArgumentException if {@code map} is not empty 275 */ 276 public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap( 277 Map<K, Collection<V>> map, 278 final Supplier<? extends SortedSet<V>> factory) { 279 return new CustomSortedSetMultimap<K, V>(map, factory); 280 } 281 282 private static class CustomSortedSetMultimap<K, V> 283 extends AbstractSortedSetMultimap<K, V> { 284 transient Supplier<? extends SortedSet<V>> factory; 285 transient Comparator<? super V> valueComparator; 286 287 CustomSortedSetMultimap(Map<K, Collection<V>> map, 288 Supplier<? extends SortedSet<V>> factory) { 289 super(map); 290 this.factory = checkNotNull(factory); 291 valueComparator = factory.get().comparator(); 292 } 293 294 @Override protected SortedSet<V> createCollection() { 295 return factory.get(); 296 } 297 298 @Override public Comparator<? super V> valueComparator() { 299 return valueComparator; 300 } 301 } 302 303 /** 304 * Copies each key-value mapping in {@code source} into {@code dest}, with 305 * its key and value reversed. 306 * 307 * <p>If {@code source} is an {@link ImmutableMultimap}, consider using 308 * {@link ImmutableMultimap#inverse} instead. 309 * 310 * @param source any multimap 311 * @param dest the multimap to copy into; usually empty 312 * @return {@code dest} 313 */ 314 public static <K, V, M extends Multimap<K, V>> M invertFrom( 315 Multimap<? extends V, ? extends K> source, M dest) { 316 checkNotNull(dest); 317 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) { 318 dest.put(entry.getValue(), entry.getKey()); 319 } 320 return dest; 321 } 322 323 /** 324 * Returns a synchronized (thread-safe) multimap backed by the specified 325 * multimap. In order to guarantee serial access, it is critical that 326 * <b>all</b> access to the backing multimap is accomplished through the 327 * returned multimap. 328 * 329 * <p>It is imperative that the user manually synchronize on the returned 330 * multimap when accessing any of its collection views: <pre> {@code 331 * 332 * Multimap<K, V> m = Multimaps.synchronizedMultimap( 333 * HashMultimap.<K, V>create()); 334 * ... 335 * Set<K> s = m.keySet(); // Needn't be in synchronized block 336 * ... 337 * synchronized (m) { // Synchronizing on m, not s! 338 * Iterator<K> i = s.iterator(); // Must be in synchronized block 339 * while (i.hasNext()) { 340 * foo(i.next()); 341 * } 342 * }}</pre> 343 * 344 * Failure to follow this advice may result in non-deterministic behavior. 345 * 346 * <p>Note that the generated multimap's {@link Multimap#removeAll} and 347 * {@link Multimap#replaceValues} methods return collections that aren't 348 * synchronized. 349 * 350 * <p>The returned multimap will be serializable if the specified multimap is 351 * serializable. 352 * 353 * @param multimap the multimap to be wrapped in a synchronized view 354 * @return a synchronized view of the specified multimap 355 */ 356 public static <K, V> Multimap<K, V> synchronizedMultimap( 357 Multimap<K, V> multimap) { 358 return Synchronized.multimap(multimap, null); 359 } 360 361 /** 362 * Returns an unmodifiable view of the specified multimap. Query operations on 363 * the returned multimap "read through" to the specified multimap, and 364 * attempts to modify the returned multimap, either directly or through the 365 * multimap's views, result in an {@code UnsupportedOperationException}. 366 * 367 * <p>Note that the generated multimap's {@link Multimap#removeAll} and 368 * {@link Multimap#replaceValues} methods return collections that are 369 * modifiable. 370 * 371 * <p>The returned multimap will be serializable if the specified multimap is 372 * serializable. 373 * 374 * @param delegate the multimap for which an unmodifiable view is to be 375 * returned 376 * @return an unmodifiable view of the specified multimap 377 */ 378 public static <K, V> Multimap<K, V> unmodifiableMultimap( 379 Multimap<K, V> delegate) { 380 if (delegate instanceof UnmodifiableMultimap || 381 delegate instanceof ImmutableMultimap) { 382 return delegate; 383 } 384 return new UnmodifiableMultimap<K, V>(delegate); 385 } 386 387 /** 388 * Simply returns its argument. 389 * 390 * @deprecated no need to use this 391 * @since 10.0 392 */ 393 @Deprecated public static <K, V> Multimap<K, V> unmodifiableMultimap( 394 ImmutableMultimap<K, V> delegate) { 395 return checkNotNull(delegate); 396 } 397 398 private static class UnmodifiableMultimap<K, V> 399 extends ForwardingMultimap<K, V> implements Serializable { 400 final Multimap<K, V> delegate; 401 transient Collection<Entry<K, V>> entries; 402 transient Multiset<K> keys; 403 transient Set<K> keySet; 404 transient Collection<V> values; 405 transient Map<K, Collection<V>> map; 406 407 UnmodifiableMultimap(final Multimap<K, V> delegate) { 408 this.delegate = checkNotNull(delegate); 409 } 410 411 @Override protected Multimap<K, V> delegate() { 412 return delegate; 413 } 414 415 @Override public void clear() { 416 throw new UnsupportedOperationException(); 417 } 418 419 @Override public Map<K, Collection<V>> asMap() { 420 Map<K, Collection<V>> result = map; 421 if (result == null) { 422 final Map<K, Collection<V>> unmodifiableMap 423 = Collections.unmodifiableMap(delegate.asMap()); 424 map = result = new ForwardingMap<K, Collection<V>>() { 425 @Override protected Map<K, Collection<V>> delegate() { 426 return unmodifiableMap; 427 } 428 429 Set<Entry<K, Collection<V>>> entrySet; 430 431 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() { 432 Set<Entry<K, Collection<V>>> result = entrySet; 433 return (result == null) 434 ? entrySet 435 = unmodifiableAsMapEntries(unmodifiableMap.entrySet()) 436 : result; 437 } 438 439 @Override public Collection<V> get(Object key) { 440 Collection<V> collection = unmodifiableMap.get(key); 441 return (collection == null) 442 ? null : unmodifiableValueCollection(collection); 443 } 444 445 Collection<Collection<V>> asMapValues; 446 447 @Override public Collection<Collection<V>> values() { 448 Collection<Collection<V>> result = asMapValues; 449 return (result == null) 450 ? asMapValues 451 = new UnmodifiableAsMapValues<V>(unmodifiableMap.values()) 452 : result; 453 } 454 455 @Override public boolean containsValue(Object o) { 456 return values().contains(o); 457 } 458 }; 459 } 460 return result; 461 } 462 463 @Override public Collection<Entry<K, V>> entries() { 464 Collection<Entry<K, V>> result = entries; 465 if (result == null) { 466 entries = result = unmodifiableEntries(delegate.entries()); 467 } 468 return result; 469 } 470 471 @Override public Collection<V> get(K key) { 472 return unmodifiableValueCollection(delegate.get(key)); 473 } 474 475 @Override public Multiset<K> keys() { 476 Multiset<K> result = keys; 477 if (result == null) { 478 keys = result = Multisets.unmodifiableMultiset(delegate.keys()); 479 } 480 return result; 481 } 482 483 @Override public Set<K> keySet() { 484 Set<K> result = keySet; 485 if (result == null) { 486 keySet = result = Collections.unmodifiableSet(delegate.keySet()); 487 } 488 return result; 489 } 490 491 @Override public boolean put(K key, V value) { 492 throw new UnsupportedOperationException(); 493 } 494 495 @Override public boolean putAll(K key, Iterable<? extends V> values) { 496 throw new UnsupportedOperationException(); 497 } 498 499 @Override 500 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 501 throw new UnsupportedOperationException(); 502 } 503 504 @Override public boolean remove(Object key, Object value) { 505 throw new UnsupportedOperationException(); 506 } 507 508 @Override public Collection<V> removeAll(Object key) { 509 throw new UnsupportedOperationException(); 510 } 511 512 @Override public Collection<V> replaceValues( 513 K key, Iterable<? extends V> values) { 514 throw new UnsupportedOperationException(); 515 } 516 517 @Override public Collection<V> values() { 518 Collection<V> result = values; 519 if (result == null) { 520 values = result = Collections.unmodifiableCollection(delegate.values()); 521 } 522 return result; 523 } 524 525 private static final long serialVersionUID = 0; 526 } 527 528 private static class UnmodifiableAsMapValues<V> 529 extends ForwardingCollection<Collection<V>> { 530 final Collection<Collection<V>> delegate; 531 UnmodifiableAsMapValues(Collection<Collection<V>> delegate) { 532 this.delegate = Collections.unmodifiableCollection(delegate); 533 } 534 @Override protected Collection<Collection<V>> delegate() { 535 return delegate; 536 } 537 @Override public Iterator<Collection<V>> iterator() { 538 final Iterator<Collection<V>> iterator = delegate.iterator(); 539 return new Iterator<Collection<V>>() { 540 @Override 541 public boolean hasNext() { 542 return iterator.hasNext(); 543 } 544 @Override 545 public Collection<V> next() { 546 return unmodifiableValueCollection(iterator.next()); 547 } 548 @Override 549 public void remove() { 550 throw new UnsupportedOperationException(); 551 } 552 }; 553 } 554 @Override public Object[] toArray() { 555 return standardToArray(); 556 } 557 @Override public <T> T[] toArray(T[] array) { 558 return standardToArray(array); 559 } 560 @Override public boolean contains(Object o) { 561 return standardContains(o); 562 } 563 @Override public boolean containsAll(Collection<?> c) { 564 return standardContainsAll(c); 565 } 566 } 567 568 private static class UnmodifiableListMultimap<K, V> 569 extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> { 570 UnmodifiableListMultimap(ListMultimap<K, V> delegate) { 571 super(delegate); 572 } 573 @Override public ListMultimap<K, V> delegate() { 574 return (ListMultimap<K, V>) super.delegate(); 575 } 576 @Override public List<V> get(K key) { 577 return Collections.unmodifiableList(delegate().get(key)); 578 } 579 @Override public List<V> removeAll(Object key) { 580 throw new UnsupportedOperationException(); 581 } 582 @Override public List<V> replaceValues( 583 K key, Iterable<? extends V> values) { 584 throw new UnsupportedOperationException(); 585 } 586 private static final long serialVersionUID = 0; 587 } 588 589 private static class UnmodifiableSetMultimap<K, V> 590 extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> { 591 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) { 592 super(delegate); 593 } 594 @Override public SetMultimap<K, V> delegate() { 595 return (SetMultimap<K, V>) super.delegate(); 596 } 597 @Override public Set<V> get(K key) { 598 /* 599 * Note that this doesn't return a SortedSet when delegate is a 600 * SortedSetMultiset, unlike (SortedSet<V>) super.get(). 601 */ 602 return Collections.unmodifiableSet(delegate().get(key)); 603 } 604 @Override public Set<Map.Entry<K, V>> entries() { 605 return Maps.unmodifiableEntrySet(delegate().entries()); 606 } 607 @Override public Set<V> removeAll(Object key) { 608 throw new UnsupportedOperationException(); 609 } 610 @Override public Set<V> replaceValues( 611 K key, Iterable<? extends V> values) { 612 throw new UnsupportedOperationException(); 613 } 614 private static final long serialVersionUID = 0; 615 } 616 617 private static class UnmodifiableSortedSetMultimap<K, V> 618 extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> { 619 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) { 620 super(delegate); 621 } 622 @Override public SortedSetMultimap<K, V> delegate() { 623 return (SortedSetMultimap<K, V>) super.delegate(); 624 } 625 @Override public SortedSet<V> get(K key) { 626 return Collections.unmodifiableSortedSet(delegate().get(key)); 627 } 628 @Override public SortedSet<V> removeAll(Object key) { 629 throw new UnsupportedOperationException(); 630 } 631 @Override public SortedSet<V> replaceValues( 632 K key, Iterable<? extends V> values) { 633 throw new UnsupportedOperationException(); 634 } 635 @Override 636 public Comparator<? super V> valueComparator() { 637 return delegate().valueComparator(); 638 } 639 private static final long serialVersionUID = 0; 640 } 641 642 /** 643 * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the 644 * specified multimap. 645 * 646 * <p>You must follow the warnings described in {@link #synchronizedMultimap}. 647 * 648 * <p>The returned multimap will be serializable if the specified multimap is 649 * serializable. 650 * 651 * @param multimap the multimap to be wrapped 652 * @return a synchronized view of the specified multimap 653 */ 654 public static <K, V> SetMultimap<K, V> synchronizedSetMultimap( 655 SetMultimap<K, V> multimap) { 656 return Synchronized.setMultimap(multimap, null); 657 } 658 659 /** 660 * Returns an unmodifiable view of the specified {@code SetMultimap}. Query 661 * operations on the returned multimap "read through" to the specified 662 * multimap, and attempts to modify the returned multimap, either directly or 663 * through the multimap's views, result in an 664 * {@code UnsupportedOperationException}. 665 * 666 * <p>Note that the generated multimap's {@link Multimap#removeAll} and 667 * {@link Multimap#replaceValues} methods return collections that are 668 * modifiable. 669 * 670 * <p>The returned multimap will be serializable if the specified multimap is 671 * serializable. 672 * 673 * @param delegate the multimap for which an unmodifiable view is to be 674 * returned 675 * @return an unmodifiable view of the specified multimap 676 */ 677 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap( 678 SetMultimap<K, V> delegate) { 679 if (delegate instanceof UnmodifiableSetMultimap || 680 delegate instanceof ImmutableSetMultimap) { 681 return delegate; 682 } 683 return new UnmodifiableSetMultimap<K, V>(delegate); 684 } 685 686 /** 687 * Simply returns its argument. 688 * 689 * @deprecated no need to use this 690 * @since 10.0 691 */ 692 @Deprecated public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap( 693 ImmutableSetMultimap<K, V> delegate) { 694 return checkNotNull(delegate); 695 } 696 697 /** 698 * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by 699 * the specified multimap. 700 * 701 * <p>You must follow the warnings described in {@link #synchronizedMultimap}. 702 * 703 * <p>The returned multimap will be serializable if the specified multimap is 704 * serializable. 705 * 706 * @param multimap the multimap to be wrapped 707 * @return a synchronized view of the specified multimap 708 */ 709 public static <K, V> SortedSetMultimap<K, V> 710 synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) { 711 return Synchronized.sortedSetMultimap(multimap, null); 712 } 713 714 /** 715 * Returns an unmodifiable view of the specified {@code SortedSetMultimap}. 716 * Query operations on the returned multimap "read through" to the specified 717 * multimap, and attempts to modify the returned multimap, either directly or 718 * through the multimap's views, result in an 719 * {@code UnsupportedOperationException}. 720 * 721 * <p>Note that the generated multimap's {@link Multimap#removeAll} and 722 * {@link Multimap#replaceValues} methods return collections that are 723 * modifiable. 724 * 725 * <p>The returned multimap will be serializable if the specified multimap is 726 * serializable. 727 * 728 * @param delegate the multimap for which an unmodifiable view is to be 729 * returned 730 * @return an unmodifiable view of the specified multimap 731 */ 732 public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap( 733 SortedSetMultimap<K, V> delegate) { 734 if (delegate instanceof UnmodifiableSortedSetMultimap) { 735 return delegate; 736 } 737 return new UnmodifiableSortedSetMultimap<K, V>(delegate); 738 } 739 740 /** 741 * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the 742 * specified multimap. 743 * 744 * <p>You must follow the warnings described in {@link #synchronizedMultimap}. 745 * 746 * @param multimap the multimap to be wrapped 747 * @return a synchronized view of the specified multimap 748 */ 749 public static <K, V> ListMultimap<K, V> synchronizedListMultimap( 750 ListMultimap<K, V> multimap) { 751 return Synchronized.listMultimap(multimap, null); 752 } 753 754 /** 755 * Returns an unmodifiable view of the specified {@code ListMultimap}. Query 756 * operations on the returned multimap "read through" to the specified 757 * multimap, and attempts to modify the returned multimap, either directly or 758 * through the multimap's views, result in an 759 * {@code UnsupportedOperationException}. 760 * 761 * <p>Note that the generated multimap's {@link Multimap#removeAll} and 762 * {@link Multimap#replaceValues} methods return collections that are 763 * modifiable. 764 * 765 * <p>The returned multimap will be serializable if the specified multimap is 766 * serializable. 767 * 768 * @param delegate the multimap for which an unmodifiable view is to be 769 * returned 770 * @return an unmodifiable view of the specified multimap 771 */ 772 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap( 773 ListMultimap<K, V> delegate) { 774 if (delegate instanceof UnmodifiableListMultimap || 775 delegate instanceof ImmutableListMultimap) { 776 return delegate; 777 } 778 return new UnmodifiableListMultimap<K, V>(delegate); 779 } 780 781 /** 782 * Simply returns its argument. 783 * 784 * @deprecated no need to use this 785 * @since 10.0 786 */ 787 @Deprecated public static <K, V> ListMultimap<K, V> unmodifiableListMultimap( 788 ImmutableListMultimap<K, V> delegate) { 789 return checkNotNull(delegate); 790 } 791 792 /** 793 * Returns an unmodifiable view of the specified collection, preserving the 794 * interface for instances of {@code SortedSet}, {@code Set}, {@code List} and 795 * {@code Collection}, in that order of preference. 796 * 797 * @param collection the collection for which to return an unmodifiable view 798 * @return an unmodifiable view of the collection 799 */ 800 private static <V> Collection<V> unmodifiableValueCollection( 801 Collection<V> collection) { 802 if (collection instanceof SortedSet) { 803 return Collections.unmodifiableSortedSet((SortedSet<V>) collection); 804 } else if (collection instanceof Set) { 805 return Collections.unmodifiableSet((Set<V>) collection); 806 } else if (collection instanceof List) { 807 return Collections.unmodifiableList((List<V>) collection); 808 } 809 return Collections.unmodifiableCollection(collection); 810 } 811 812 /** 813 * Returns an unmodifiable view of the specified multimap {@code asMap} entry. 814 * The {@link Entry#setValue} operation throws an {@link 815 * UnsupportedOperationException}, and the collection returned by {@code 816 * getValue} is also an unmodifiable (type-preserving) view. This also has the 817 * side-effect of redefining equals to comply with the Map.Entry contract, and 818 * to avoid a possible nefarious implementation of equals. 819 * 820 * @param entry the entry for which to return an unmodifiable view 821 * @return an unmodifiable view of the entry 822 */ 823 private static <K, V> Map.Entry<K, Collection<V>> unmodifiableAsMapEntry( 824 final Map.Entry<K, Collection<V>> entry) { 825 checkNotNull(entry); 826 return new AbstractMapEntry<K, Collection<V>>() { 827 @Override public K getKey() { 828 return entry.getKey(); 829 } 830 831 @Override public Collection<V> getValue() { 832 return unmodifiableValueCollection(entry.getValue()); 833 } 834 }; 835 } 836 837 /** 838 * Returns an unmodifiable view of the specified collection of entries. The 839 * {@link Entry#setValue} operation throws an {@link 840 * UnsupportedOperationException}. If the specified collection is a {@code 841 * Set}, the returned collection is also a {@code Set}. 842 * 843 * @param entries the entries for which to return an unmodifiable view 844 * @return an unmodifiable view of the entries 845 */ 846 private static <K, V> Collection<Entry<K, V>> unmodifiableEntries( 847 Collection<Entry<K, V>> entries) { 848 if (entries instanceof Set) { 849 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries); 850 } 851 return new Maps.UnmodifiableEntries<K, V>( 852 Collections.unmodifiableCollection(entries)); 853 } 854 855 /** 856 * Returns an unmodifiable view of the specified set of {@code asMap} entries. 857 * The {@link Entry#setValue} operation throws an {@link 858 * UnsupportedOperationException}, as do any operations that attempt to modify 859 * the returned collection. 860 * 861 * @param asMapEntries the {@code asMap} entries for which to return an 862 * unmodifiable view 863 * @return an unmodifiable view of the collection entries 864 */ 865 private static <K, V> Set<Entry<K, Collection<V>>> unmodifiableAsMapEntries( 866 Set<Entry<K, Collection<V>>> asMapEntries) { 867 return new UnmodifiableAsMapEntries<K, V>( 868 Collections.unmodifiableSet(asMapEntries)); 869 } 870 871 /** @see Multimaps#unmodifiableAsMapEntries */ 872 static class UnmodifiableAsMapEntries<K, V> 873 extends ForwardingSet<Entry<K, Collection<V>>> { 874 private final Set<Entry<K, Collection<V>>> delegate; 875 UnmodifiableAsMapEntries(Set<Entry<K, Collection<V>>> delegate) { 876 this.delegate = delegate; 877 } 878 879 @Override protected Set<Entry<K, Collection<V>>> delegate() { 880 return delegate; 881 } 882 883 @Override public Iterator<Entry<K, Collection<V>>> iterator() { 884 final Iterator<Entry<K, Collection<V>>> iterator = delegate.iterator(); 885 return new ForwardingIterator<Entry<K, Collection<V>>>() { 886 @Override protected Iterator<Entry<K, Collection<V>>> delegate() { 887 return iterator; 888 } 889 @Override public Entry<K, Collection<V>> next() { 890 return unmodifiableAsMapEntry(iterator.next()); 891 } 892 }; 893 } 894 895 @Override public Object[] toArray() { 896 return standardToArray(); 897 } 898 899 @Override public <T> T[] toArray(T[] array) { 900 return standardToArray(array); 901 } 902 903 @Override public boolean contains(Object o) { 904 return Maps.containsEntryImpl(delegate(), o); 905 } 906 907 @Override public boolean containsAll(Collection<?> c) { 908 return standardContainsAll(c); 909 } 910 911 @Override public boolean equals(@Nullable Object object) { 912 return standardEquals(object); 913 } 914 } 915 916 /** 917 * Returns a multimap view of the specified map. The multimap is backed by the 918 * map, so changes to the map are reflected in the multimap, and vice versa. 919 * If the map is modified while an iteration over one of the multimap's 920 * collection views is in progress (except through the iterator's own {@code 921 * remove} operation, or through the {@code setValue} operation on a map entry 922 * returned by the iterator), the results of the iteration are undefined. 923 * 924 * <p>The multimap supports mapping removal, which removes the corresponding 925 * mapping from the map. It does not support any operations which might add 926 * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}. 927 * 928 * <p>The returned multimap will be serializable if the specified map is 929 * serializable. 930 * 931 * @param map the backing map for the returned multimap view 932 */ 933 public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) { 934 return new MapMultimap<K, V>(map); 935 } 936 937 /** @see Multimaps#forMap */ 938 private static class MapMultimap<K, V> 939 implements SetMultimap<K, V>, Serializable { 940 final Map<K, V> map; 941 transient Map<K, Collection<V>> asMap; 942 943 MapMultimap(Map<K, V> map) { 944 this.map = checkNotNull(map); 945 } 946 947 @Override 948 public int size() { 949 return map.size(); 950 } 951 952 @Override 953 public boolean isEmpty() { 954 return map.isEmpty(); 955 } 956 957 @Override 958 public boolean containsKey(Object key) { 959 return map.containsKey(key); 960 } 961 962 @Override 963 public boolean containsValue(Object value) { 964 return map.containsValue(value); 965 } 966 967 @Override 968 public boolean containsEntry(Object key, Object value) { 969 return map.entrySet().contains(Maps.immutableEntry(key, value)); 970 } 971 972 @Override 973 public Set<V> get(final K key) { 974 return new AbstractSet<V>() { 975 @Override public Iterator<V> iterator() { 976 return new Iterator<V>() { 977 int i; 978 979 @Override 980 public boolean hasNext() { 981 return (i == 0) && map.containsKey(key); 982 } 983 984 @Override 985 public V next() { 986 if (!hasNext()) { 987 throw new NoSuchElementException(); 988 } 989 i++; 990 return map.get(key); 991 } 992 993 @Override 994 public void remove() { 995 checkState(i == 1); 996 i = -1; 997 map.remove(key); 998 } 999 }; 1000 } 1001 1002 @Override public int size() { 1003 return map.containsKey(key) ? 1 : 0; 1004 } 1005 }; 1006 } 1007 1008 @Override 1009 public boolean put(K key, V value) { 1010 throw new UnsupportedOperationException(); 1011 } 1012 1013 @Override 1014 public boolean putAll(K key, Iterable<? extends V> values) { 1015 throw new UnsupportedOperationException(); 1016 } 1017 1018 @Override 1019 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 1020 throw new UnsupportedOperationException(); 1021 } 1022 1023 @Override 1024 public Set<V> replaceValues(K key, Iterable<? extends V> values) { 1025 throw new UnsupportedOperationException(); 1026 } 1027 1028 @Override 1029 public boolean remove(Object key, Object value) { 1030 return map.entrySet().remove(Maps.immutableEntry(key, value)); 1031 } 1032 1033 @Override 1034 public Set<V> removeAll(Object key) { 1035 Set<V> values = new HashSet<V>(2); 1036 if (!map.containsKey(key)) { 1037 return values; 1038 } 1039 values.add(map.remove(key)); 1040 return values; 1041 } 1042 1043 @Override 1044 public void clear() { 1045 map.clear(); 1046 } 1047 1048 @Override 1049 public Set<K> keySet() { 1050 return map.keySet(); 1051 } 1052 1053 @Override 1054 public Multiset<K> keys() { 1055 return Multisets.forSet(map.keySet()); 1056 } 1057 1058 @Override 1059 public Collection<V> values() { 1060 return map.values(); 1061 } 1062 1063 @Override 1064 public Set<Entry<K, V>> entries() { 1065 return map.entrySet(); 1066 } 1067 1068 @Override 1069 public Map<K, Collection<V>> asMap() { 1070 Map<K, Collection<V>> result = asMap; 1071 if (result == null) { 1072 asMap = result = new AsMap(); 1073 } 1074 return result; 1075 } 1076 1077 @Override public boolean equals(@Nullable Object object) { 1078 if (object == this) { 1079 return true; 1080 } 1081 if (object instanceof Multimap) { 1082 Multimap<?, ?> that = (Multimap<?, ?>) object; 1083 return this.size() == that.size() && asMap().equals(that.asMap()); 1084 } 1085 return false; 1086 } 1087 1088 @Override public int hashCode() { 1089 return map.hashCode(); 1090 } 1091 1092 private static final MapJoiner JOINER 1093 = Joiner.on("], ").withKeyValueSeparator("=[").useForNull("null"); 1094 1095 @Override public String toString() { 1096 if (map.isEmpty()) { 1097 return "{}"; 1098 } 1099 StringBuilder builder 1100 = Collections2.newStringBuilderForCollection(map.size()).append('{'); 1101 JOINER.appendTo(builder, map); 1102 return builder.append("]}").toString(); 1103 } 1104 1105 /** @see MapMultimap#asMap */ 1106 class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> { 1107 @Override public int size() { 1108 return map.size(); 1109 } 1110 1111 @Override public Iterator<Entry<K, Collection<V>>> iterator() { 1112 return new Iterator<Entry<K, Collection<V>>>() { 1113 final Iterator<K> keys = map.keySet().iterator(); 1114 1115 @Override 1116 public boolean hasNext() { 1117 return keys.hasNext(); 1118 } 1119 @Override 1120 public Entry<K, Collection<V>> next() { 1121 final K key = keys.next(); 1122 return new AbstractMapEntry<K, Collection<V>>() { 1123 @Override public K getKey() { 1124 return key; 1125 } 1126 @Override public Collection<V> getValue() { 1127 return get(key); 1128 } 1129 }; 1130 } 1131 @Override 1132 public void remove() { 1133 keys.remove(); 1134 } 1135 }; 1136 } 1137 1138 @Override public boolean contains(Object o) { 1139 if (!(o instanceof Entry)) { 1140 return false; 1141 } 1142 Entry<?, ?> entry = (Entry<?, ?>) o; 1143 if (!(entry.getValue() instanceof Set)) { 1144 return false; 1145 } 1146 Set<?> set = (Set<?>) entry.getValue(); 1147 return (set.size() == 1) 1148 && containsEntry(entry.getKey(), set.iterator().next()); 1149 } 1150 1151 @Override public boolean remove(Object o) { 1152 if (!(o instanceof Entry)) { 1153 return false; 1154 } 1155 Entry<?, ?> entry = (Entry<?, ?>) o; 1156 if (!(entry.getValue() instanceof Set)) { 1157 return false; 1158 } 1159 Set<?> set = (Set<?>) entry.getValue(); 1160 return (set.size() == 1) 1161 && map.entrySet().remove( 1162 Maps.immutableEntry(entry.getKey(), set.iterator().next())); 1163 } 1164 } 1165 1166 /** @see MapMultimap#asMap */ 1167 class AsMap extends Maps.ImprovedAbstractMap<K, Collection<V>> { 1168 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() { 1169 return new AsMapEntries(); 1170 } 1171 1172 // The following methods are included for performance. 1173 1174 @Override public boolean containsKey(Object key) { 1175 return map.containsKey(key); 1176 } 1177 1178 @SuppressWarnings("unchecked") 1179 @Override public Collection<V> get(Object key) { 1180 Collection<V> collection = MapMultimap.this.get((K) key); 1181 return collection.isEmpty() ? null : collection; 1182 } 1183 1184 @Override public Collection<V> remove(Object key) { 1185 Collection<V> collection = removeAll(key); 1186 return collection.isEmpty() ? null : collection; 1187 } 1188 } 1189 private static final long serialVersionUID = 7845222491160860175L; 1190 } 1191 1192 /** 1193 * Returns a view of a multimap where each value is transformed by a function. 1194 * All other properties of the multimap, such as iteration order, are left 1195 * intact. For example, the code: <pre> {@code 1196 * 1197 * Multimap<String, Integer> multimap = 1198 * ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6); 1199 * Function<Integer, String> square = new Function<Integer, String>() { 1200 * public String apply(Integer in) { 1201 * return Integer.toString(in * in); 1202 * } 1203 * }; 1204 * Multimap<String, String> transformed = 1205 * Multimaps.transformValues(multimap, square); 1206 * System.out.println(transformed);}</pre> 1207 * 1208 * ... prints {@code {a=[4, 16], b=[9, 9], c=[6]}}. 1209 * 1210 * <p>Changes in the underlying multimap are reflected in this view. 1211 * Conversely, this view supports removal operations, and these are reflected 1212 * in the underlying multimap. 1213 * 1214 * <p>It's acceptable for the underlying multimap to contain null keys, and 1215 * even null values provided that the function is capable of accepting null 1216 * input. The transformed multimap might contain null values, if the function 1217 * sometimes gives a null result. 1218 * 1219 * <p>The returned multimap is not thread-safe or serializable, even if the 1220 * underlying multimap is. The {@code equals} and {@code hashCode} methods 1221 * of the returned multimap are meaningless, since there is not a definition 1222 * of {@code equals} or {@code hashCode} for general collections, and 1223 * {@code get()} will return a general {@code Collection} as opposed to a 1224 * {@code List} or a {@code Set}. 1225 * 1226 * <p>The function is applied lazily, invoked when needed. This is necessary 1227 * for the returned multimap to be a view, but it means that the function will 1228 * be applied many times for bulk operations like 1229 * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to 1230 * perform well, {@code function} should be fast. To avoid lazy evaluation 1231 * when the returned multimap doesn't need to be a view, copy the returned 1232 * multimap into a new multimap of your choosing. 1233 * 1234 * @since 7.0 1235 */ 1236 @Beta 1237 public static <K, V1, V2> Multimap<K, V2> transformValues( 1238 Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) { 1239 checkNotNull(function); 1240 EntryTransformer<K, V1, V2> transformer = 1241 new EntryTransformer<K, V1, V2>() { 1242 @Override 1243 public V2 transformEntry(K key, V1 value) { 1244 return function.apply(value); 1245 } 1246 }; 1247 return transformEntries(fromMultimap, transformer); 1248 } 1249 1250 /** 1251 * Returns a view of a multimap whose values are derived from the original 1252 * multimap's entries. In contrast to {@link #transformValues}, this method's 1253 * entry-transformation logic may depend on the key as well as the value. 1254 * 1255 * <p>All other properties of the transformed multimap, such as iteration 1256 * order, are left intact. For example, the code: <pre> {@code 1257 * 1258 * SetMultimap<String, Integer> multimap = 1259 * ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6); 1260 * EntryTransformer<String, Integer, String> transformer = 1261 * new EntryTransformer<String, Integer, String>() { 1262 * public String transformEntry(String key, Integer value) { 1263 * return (value >= 0) ? key : "no" + key; 1264 * } 1265 * }; 1266 * Multimap<String, String> transformed = 1267 * Multimaps.transformEntries(multimap, transformer); 1268 * System.out.println(transformed);}</pre> 1269 * 1270 * ... prints {@code {a=[a, a], b=[nob]}}. 1271 * 1272 * <p>Changes in the underlying multimap are reflected in this view. 1273 * Conversely, this view supports removal operations, and these are reflected 1274 * in the underlying multimap. 1275 * 1276 * <p>It's acceptable for the underlying multimap to contain null keys and 1277 * null values provided that the transformer is capable of accepting null 1278 * inputs. The transformed multimap might contain null values if the 1279 * transformer sometimes gives a null result. 1280 * 1281 * <p>The returned multimap is not thread-safe or serializable, even if the 1282 * underlying multimap is. The {@code equals} and {@code hashCode} methods 1283 * of the returned multimap are meaningless, since there is not a definition 1284 * of {@code equals} or {@code hashCode} for general collections, and 1285 * {@code get()} will return a general {@code Collection} as opposed to a 1286 * {@code List} or a {@code Set}. 1287 * 1288 * <p>The transformer is applied lazily, invoked when needed. This is 1289 * necessary for the returned multimap to be a view, but it means that the 1290 * transformer will be applied many times for bulk operations like {@link 1291 * Multimap#containsValue} and {@link Object#toString}. For this to perform 1292 * well, {@code transformer} should be fast. To avoid lazy evaluation when the 1293 * returned multimap doesn't need to be a view, copy the returned multimap 1294 * into a new multimap of your choosing. 1295 * 1296 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 1297 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies 1298 * that {@code k2} is also of type {@code K}. Using an {@code 1299 * EntryTransformer} key type for which this may not hold, such as {@code 1300 * ArrayList}, may risk a {@code ClassCastException} when calling methods on 1301 * the transformed multimap. 1302 * 1303 * @since 7.0 1304 */ 1305 @Beta 1306 public static <K, V1, V2> Multimap<K, V2> transformEntries( 1307 Multimap<K, V1> fromMap, 1308 EntryTransformer<? super K, ? super V1, V2> transformer) { 1309 return new TransformedEntriesMultimap<K, V1, V2>(fromMap, transformer); 1310 } 1311 1312 private static class TransformedEntriesMultimap<K, V1, V2> 1313 implements Multimap<K, V2> { 1314 final Multimap<K, V1> fromMultimap; 1315 final EntryTransformer<? super K, ? super V1, V2> transformer; 1316 1317 TransformedEntriesMultimap(Multimap<K, V1> fromMultimap, 1318 final EntryTransformer<? super K, ? super V1, V2> transformer) { 1319 this.fromMultimap = checkNotNull(fromMultimap); 1320 this.transformer = checkNotNull(transformer); 1321 } 1322 1323 Collection<V2> transform(final K key, Collection<V1> values) { 1324 return Collections2.transform(values, new Function<V1, V2>() { 1325 @Override public V2 apply(V1 value) { 1326 return transformer.transformEntry(key, value); 1327 } 1328 }); 1329 } 1330 1331 private transient Map<K, Collection<V2>> asMap; 1332 1333 @Override public Map<K, Collection<V2>> asMap() { 1334 if (asMap == null) { 1335 Map<K, Collection<V2>> aM = Maps.transformEntries(fromMultimap.asMap(), 1336 new EntryTransformer<K, Collection<V1>, Collection<V2>>() { 1337 1338 @Override public Collection<V2> transformEntry( 1339 K key, Collection<V1> value) { 1340 return transform(key, value); 1341 } 1342 }); 1343 asMap = aM; 1344 return aM; 1345 } 1346 return asMap; 1347 } 1348 1349 @Override public void clear() { 1350 fromMultimap.clear(); 1351 } 1352 1353 @SuppressWarnings("unchecked") 1354 @Override public boolean containsEntry(Object key, Object value) { 1355 Collection<V2> values = get((K) key); 1356 return values.contains(value); 1357 } 1358 1359 @Override public boolean containsKey(Object key) { 1360 return fromMultimap.containsKey(key); 1361 } 1362 1363 @Override public boolean containsValue(Object value) { 1364 return values().contains(value); 1365 } 1366 1367 private transient Collection<Entry<K, V2>> entries; 1368 1369 @Override public Collection<Entry<K, V2>> entries() { 1370 if (entries == null) { 1371 Collection<Entry<K, V2>> es = new TransformedEntries(transformer); 1372 entries = es; 1373 return es; 1374 } 1375 return entries; 1376 } 1377 1378 private class TransformedEntries 1379 extends TransformedCollection<Entry<K, V1>, Entry<K, V2>> { 1380 1381 TransformedEntries( 1382 final EntryTransformer<? super K, ? super V1, V2> transformer) { 1383 super(fromMultimap.entries(), 1384 new Function<Entry<K, V1>, Entry<K, V2>>() { 1385 @Override public Entry<K, V2> apply(final Entry<K, V1> entry) { 1386 return new AbstractMapEntry<K, V2>() { 1387 1388 @Override public K getKey() { 1389 return entry.getKey(); 1390 } 1391 1392 @Override public V2 getValue() { 1393 return transformer.transformEntry( 1394 entry.getKey(), entry.getValue()); 1395 } 1396 }; 1397 } 1398 }); 1399 } 1400 1401 @Override public boolean contains(Object o) { 1402 if (o instanceof Entry) { 1403 Entry<?, ?> entry = (Entry<?, ?>) o; 1404 return containsEntry(entry.getKey(), entry.getValue()); 1405 } 1406 return false; 1407 } 1408 1409 @SuppressWarnings("unchecked") 1410 @Override public boolean remove(Object o) { 1411 if (o instanceof Entry) { 1412 Entry<?, ?> entry = (Entry<?, ?>) o; 1413 Collection<V2> values = get((K) entry.getKey()); 1414 return values.remove(entry.getValue()); 1415 } 1416 return false; 1417 } 1418 1419 } 1420 1421 @Override public Collection<V2> get(final K key) { 1422 return transform(key, fromMultimap.get(key)); 1423 } 1424 1425 @Override public boolean isEmpty() { 1426 return fromMultimap.isEmpty(); 1427 } 1428 1429 @Override public Set<K> keySet() { 1430 return fromMultimap.keySet(); 1431 } 1432 1433 @Override public Multiset<K> keys() { 1434 return fromMultimap.keys(); 1435 } 1436 1437 @Override public boolean put(K key, V2 value) { 1438 throw new UnsupportedOperationException(); 1439 } 1440 1441 @Override public boolean putAll(K key, Iterable<? extends V2> values) { 1442 throw new UnsupportedOperationException(); 1443 } 1444 1445 @Override public boolean putAll( 1446 Multimap<? extends K, ? extends V2> multimap) { 1447 throw new UnsupportedOperationException(); 1448 } 1449 1450 @SuppressWarnings("unchecked") 1451 @Override public boolean remove(Object key, Object value) { 1452 return get((K) key).remove(value); 1453 } 1454 1455 @SuppressWarnings("unchecked") 1456 @Override public Collection<V2> removeAll(Object key) { 1457 return transform((K) key, fromMultimap.removeAll(key)); 1458 } 1459 1460 @Override public Collection<V2> replaceValues( 1461 K key, Iterable<? extends V2> values) { 1462 throw new UnsupportedOperationException(); 1463 } 1464 1465 @Override public int size() { 1466 return fromMultimap.size(); 1467 } 1468 1469 private transient Collection<V2> values; 1470 1471 @Override public Collection<V2> values() { 1472 if (values == null) { 1473 Collection<V2> vs = Collections2.transform( 1474 fromMultimap.entries(), new Function<Entry<K, V1>, V2>() { 1475 1476 @Override public V2 apply(Entry<K, V1> entry) { 1477 return transformer.transformEntry( 1478 entry.getKey(), entry.getValue()); 1479 } 1480 }); 1481 values = vs; 1482 return vs; 1483 } 1484 return values; 1485 } 1486 1487 @Override public boolean equals(Object obj) { 1488 if (obj instanceof Multimap) { 1489 Multimap<?, ?> other = (Multimap<?, ?>) obj; 1490 return asMap().equals(other.asMap()); 1491 } 1492 return false; 1493 } 1494 1495 @Override public int hashCode() { 1496 return asMap().hashCode(); 1497 } 1498 1499 @Override public String toString() { 1500 return asMap().toString(); 1501 } 1502 } 1503 1504 /** 1505 * Returns a view of a {@code ListMultimap} where each value is transformed by 1506 * a function. All other properties of the multimap, such as iteration order, 1507 * are left intact. For example, the code: <pre> {@code 1508 * 1509 * ListMultimap<String, Integer> multimap 1510 * = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9); 1511 * Function<Integer, Double> sqrt = 1512 * new Function<Integer, Double>() { 1513 * public Double apply(Integer in) { 1514 * return Math.sqrt((int) in); 1515 * } 1516 * }; 1517 * ListMultimap<String, Double> transformed = Multimaps.transformValues(map, 1518 * sqrt); 1519 * System.out.println(transformed);}</pre> 1520 * 1521 * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}. 1522 * 1523 * <p>Changes in the underlying multimap are reflected in this view. 1524 * Conversely, this view supports removal operations, and these are reflected 1525 * in the underlying multimap. 1526 * 1527 * <p>It's acceptable for the underlying multimap to contain null keys, and 1528 * even null values provided that the function is capable of accepting null 1529 * input. The transformed multimap might contain null values, if the function 1530 * sometimes gives a null result. 1531 * 1532 * <p>The returned multimap is not thread-safe or serializable, even if the 1533 * underlying multimap is. 1534 * 1535 * <p>The function is applied lazily, invoked when needed. This is necessary 1536 * for the returned multimap to be a view, but it means that the function will 1537 * be applied many times for bulk operations like 1538 * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to 1539 * perform well, {@code function} should be fast. To avoid lazy evaluation 1540 * when the returned multimap doesn't need to be a view, copy the returned 1541 * multimap into a new multimap of your choosing. 1542 * 1543 * @since 7.0 1544 */ 1545 @Beta 1546 public static <K, V1, V2> ListMultimap<K, V2> transformValues( 1547 ListMultimap<K, V1> fromMultimap, 1548 final Function<? super V1, V2> function) { 1549 checkNotNull(function); 1550 EntryTransformer<K, V1, V2> transformer = 1551 new EntryTransformer<K, V1, V2>() { 1552 @Override 1553 public V2 transformEntry(K key, V1 value) { 1554 return function.apply(value); 1555 } 1556 }; 1557 return transformEntries(fromMultimap, transformer); 1558 } 1559 1560 /** 1561 * Returns a view of a {@code ListMultimap} whose values are derived from the 1562 * original multimap's entries. In contrast to 1563 * {@link #transformValues(ListMultimap, Function)}, this method's 1564 * entry-transformation logic may depend on the key as well as the value. 1565 * 1566 * <p>All other properties of the transformed multimap, such as iteration 1567 * order, are left intact. For example, the code: <pre> {@code 1568 * 1569 * Multimap<String, Integer> multimap = 1570 * ImmutableMultimap.of("a", 1, "a", 4, "b", 6); 1571 * EntryTransformer<String, Integer, String> transformer = 1572 * new EntryTransformer<String, Integer, String>() { 1573 * public String transformEntry(String key, Integer value) { 1574 * return key + value; 1575 * } 1576 * }; 1577 * Multimap<String, String> transformed = 1578 * Multimaps.transformEntries(multimap, transformer); 1579 * System.out.println(transformed);}</pre> 1580 * 1581 * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}. 1582 * 1583 * <p>Changes in the underlying multimap are reflected in this view. 1584 * Conversely, this view supports removal operations, and these are reflected 1585 * in the underlying multimap. 1586 * 1587 * <p>It's acceptable for the underlying multimap to contain null keys and 1588 * null values provided that the transformer is capable of accepting null 1589 * inputs. The transformed multimap might contain null values if the 1590 * transformer sometimes gives a null result. 1591 * 1592 * <p>The returned multimap is not thread-safe or serializable, even if the 1593 * underlying multimap is. 1594 * 1595 * <p>The transformer is applied lazily, invoked when needed. This is 1596 * necessary for the returned multimap to be a view, but it means that the 1597 * transformer will be applied many times for bulk operations like {@link 1598 * Multimap#containsValue} and {@link Object#toString}. For this to perform 1599 * well, {@code transformer} should be fast. To avoid lazy evaluation when the 1600 * returned multimap doesn't need to be a view, copy the returned multimap 1601 * into a new multimap of your choosing. 1602 * 1603 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 1604 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies 1605 * that {@code k2} is also of type {@code K}. Using an {@code 1606 * EntryTransformer} key type for which this may not hold, such as {@code 1607 * ArrayList}, may risk a {@code ClassCastException} when calling methods on 1608 * the transformed multimap. 1609 * 1610 * @since 7.0 1611 */ 1612 @Beta 1613 public static <K, V1, V2> ListMultimap<K, V2> transformEntries( 1614 ListMultimap<K, V1> fromMap, 1615 EntryTransformer<? super K, ? super V1, V2> transformer) { 1616 return new TransformedEntriesListMultimap<K, V1, V2>(fromMap, transformer); 1617 } 1618 1619 private static final class TransformedEntriesListMultimap<K, V1, V2> 1620 extends TransformedEntriesMultimap<K, V1, V2> 1621 implements ListMultimap<K, V2> { 1622 1623 TransformedEntriesListMultimap(ListMultimap<K, V1> fromMultimap, 1624 EntryTransformer<? super K, ? super V1, V2> transformer) { 1625 super(fromMultimap, transformer); 1626 } 1627 1628 @Override List<V2> transform(final K key, Collection<V1> values) { 1629 return Lists.transform((List<V1>) values, new Function<V1, V2>() { 1630 @Override public V2 apply(V1 value) { 1631 return transformer.transformEntry(key, value); 1632 } 1633 }); 1634 } 1635 1636 @Override public List<V2> get(K key) { 1637 return transform(key, fromMultimap.get(key)); 1638 } 1639 1640 @SuppressWarnings("unchecked") 1641 @Override public List<V2> removeAll(Object key) { 1642 return transform((K) key, fromMultimap.removeAll(key)); 1643 } 1644 1645 @Override public List<V2> replaceValues( 1646 K key, Iterable<? extends V2> values) { 1647 throw new UnsupportedOperationException(); 1648 } 1649 } 1650 1651 /** 1652 * Creates an index {@code ImmutableListMultimap} that contains the results of 1653 * applying a specified function to each item in an {@code Iterable} of 1654 * values. Each value will be stored as a value in the resulting multimap, 1655 * yielding a multimap with the same size as the input iterable. The key used 1656 * to store that value in the multimap will be the result of calling the 1657 * function on that value. The resulting multimap is created as an immutable 1658 * snapshot. In the returned multimap, keys appear in the order they are first 1659 * encountered, and the values corresponding to each key appear in the same 1660 * order as they are encountered. 1661 * 1662 * <p>For example, <pre> {@code 1663 * 1664 * List<String> badGuys = 1665 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde"); 1666 * Function<String, Integer> stringLengthFunction = ...; 1667 * Multimap<Integer, String> index = 1668 * Multimaps.index(badGuys, stringLengthFunction); 1669 * System.out.println(index);}</pre> 1670 * 1671 * prints <pre> {@code 1672 * 1673 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre> 1674 * 1675 * The returned multimap is serializable if its keys and values are all 1676 * serializable. 1677 * 1678 * @param values the values to use when constructing the {@code 1679 * ImmutableListMultimap} 1680 * @param keyFunction the function used to produce the key for each value 1681 * @return {@code ImmutableListMultimap} mapping the result of evaluating the 1682 * function {@code keyFunction} on each value in the input collection to 1683 * that value 1684 * @throws NullPointerException if any of the following cases is true: 1685 * <ul> 1686 * <li>{@code values} is null 1687 * <li>{@code keyFunction} is null 1688 * <li>An element in {@code values} is null 1689 * <li>{@code keyFunction} returns {@code null} for any element of {@code 1690 * values} 1691 * </ul> 1692 */ 1693 public static <K, V> ImmutableListMultimap<K, V> index( 1694 Iterable<V> values, Function<? super V, K> keyFunction) { 1695 return index(values.iterator(), keyFunction); 1696 } 1697 1698 /** 1699 * <b>Deprecated.</b> 1700 * 1701 * @since 10.0 1702 * @deprecated use {@link #index(Iterator, Function)} by casting {@code 1703 * values} to {@code Iterator<V>}, or better yet, by implementing only 1704 * {@code Iterator} and not {@code Iterable}. <b>This method is scheduled 1705 * for deletion in March 2012.</b> 1706 */ 1707 @Beta 1708 @Deprecated 1709 public static <K, V, I extends Object & Iterable<V> & Iterator<V>> 1710 ImmutableListMultimap<K, V> index( 1711 I values, Function<? super V, K> keyFunction) { 1712 Iterable<V> valuesIterable = checkNotNull(values); 1713 return index(valuesIterable, keyFunction); 1714 } 1715 1716 /** 1717 * Creates an index {@code ImmutableListMultimap} that contains the results of 1718 * applying a specified function to each item in an {@code Iterator} of 1719 * values. Each value will be stored as a value in the resulting multimap, 1720 * yielding a multimap with the same size as the input iterator. The key used 1721 * to store that value in the multimap will be the result of calling the 1722 * function on that value. The resulting multimap is created as an immutable 1723 * snapshot. In the returned multimap, keys appear in the order they are first 1724 * encountered, and the values corresponding to each key appear in the same 1725 * order as they are encountered. 1726 * 1727 * <p>For example, <pre> {@code 1728 * 1729 * List<String> badGuys = 1730 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde"); 1731 * Function<String, Integer> stringLengthFunction = ...; 1732 * Multimap<Integer, String> index = 1733 * Multimaps.index(badGuys.iterator(), stringLengthFunction); 1734 * System.out.println(index);}</pre> 1735 * 1736 * prints <pre> {@code 1737 * 1738 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre> 1739 * 1740 * The returned multimap is serializable if its keys and values are all 1741 * serializable. 1742 * 1743 * @param values the values to use when constructing the {@code 1744 * ImmutableListMultimap} 1745 * @param keyFunction the function used to produce the key for each value 1746 * @return {@code ImmutableListMultimap} mapping the result of evaluating the 1747 * function {@code keyFunction} on each value in the input collection to 1748 * that value 1749 * @throws NullPointerException if any of the following cases is true: 1750 * <ul> 1751 * <li>{@code values} is null 1752 * <li>{@code keyFunction} is null 1753 * <li>An element in {@code values} is null 1754 * <li>{@code keyFunction} returns {@code null} for any element of {@code 1755 * values} 1756 * </ul> 1757 * @since 10.0 1758 */ 1759 public static <K, V> ImmutableListMultimap<K, V> index( 1760 Iterator<V> values, Function<? super V, K> keyFunction) { 1761 checkNotNull(keyFunction); 1762 ImmutableListMultimap.Builder<K, V> builder 1763 = ImmutableListMultimap.builder(); 1764 while (values.hasNext()) { 1765 V value = values.next(); 1766 checkNotNull(value, values); 1767 builder.put(keyFunction.apply(value), value); 1768 } 1769 return builder.build(); 1770 } 1771 1772 static abstract class Keys<K, V> extends AbstractMultiset<K> { 1773 abstract Multimap<K, V> multimap(); 1774 1775 @Override Iterator<Multiset.Entry<K>> entryIterator() { 1776 final Iterator<Map.Entry<K, Collection<V>>> backingIterator = 1777 multimap().asMap().entrySet().iterator(); 1778 return new Iterator<Multiset.Entry<K>>() { 1779 @Override public boolean hasNext() { 1780 return backingIterator.hasNext(); 1781 } 1782 1783 @Override public Multiset.Entry<K> next() { 1784 final Map.Entry<K, Collection<V>> backingEntry = 1785 backingIterator.next(); 1786 return new Multisets.AbstractEntry<K>() { 1787 @Override public K getElement() { 1788 return backingEntry.getKey(); 1789 } 1790 1791 @Override public int getCount() { 1792 return backingEntry.getValue().size(); 1793 } 1794 }; 1795 } 1796 1797 @Override public void remove() { 1798 backingIterator.remove(); 1799 } 1800 }; 1801 } 1802 1803 @Override int distinctElements() { 1804 return multimap().asMap().size(); 1805 } 1806 1807 @Override Set<Multiset.Entry<K>> createEntrySet() { 1808 return new KeysEntrySet(); 1809 } 1810 1811 class KeysEntrySet extends Multisets.EntrySet<K> { 1812 @Override Multiset<K> multiset() { 1813 return Keys.this; 1814 } 1815 1816 @Override public Iterator<Multiset.Entry<K>> iterator() { 1817 return entryIterator(); 1818 } 1819 1820 @Override public int size() { 1821 return distinctElements(); 1822 } 1823 1824 @Override public boolean isEmpty() { 1825 return multimap().isEmpty(); 1826 } 1827 1828 @Override public boolean contains(@Nullable Object o) { 1829 if (o instanceof Multiset.Entry<?>) { 1830 Multiset.Entry<?> entry = (Multiset.Entry<?>) o; 1831 Collection<V> collection = multimap().asMap().get(entry.getElement()); 1832 return collection != null && collection.size() == entry.getCount(); 1833 } 1834 return false; 1835 } 1836 1837 @Override public boolean remove(@Nullable Object o) { 1838 if (o instanceof Multiset.Entry<?>) { 1839 Multiset.Entry<?> entry = (Multiset.Entry<?>) o; 1840 Collection<V> collection = multimap().asMap().get(entry.getElement()); 1841 if (collection != null && collection.size() == entry.getCount()) { 1842 collection.clear(); 1843 return true; 1844 } 1845 } 1846 return false; 1847 } 1848 } 1849 1850 @Override public boolean contains(@Nullable Object element) { 1851 return multimap().containsKey(element); 1852 } 1853 1854 @Override public Iterator<K> iterator() { 1855 return Iterators.transform(multimap().entries().iterator(), 1856 new Function<Map.Entry<K, V>, K>() { 1857 @Override public K apply(Map.Entry<K, V> entry) { 1858 return entry.getKey(); 1859 } 1860 }); 1861 } 1862 1863 @Override public int count(@Nullable Object element) { 1864 try { 1865 if (multimap().containsKey(element)) { 1866 Collection<V> values = multimap().asMap().get(element); 1867 return (values == null) ? 0 : values.size(); 1868 } 1869 return 0; 1870 } catch (ClassCastException e) { 1871 return 0; 1872 } catch (NullPointerException e) { 1873 return 0; 1874 } 1875 } 1876 1877 @Override public int remove(@Nullable Object element, int occurrences) { 1878 checkArgument(occurrences >= 0); 1879 if (occurrences == 0) { 1880 return count(element); 1881 } 1882 1883 Collection<V> values; 1884 try { 1885 values = multimap().asMap().get(element); 1886 } catch (ClassCastException e) { 1887 return 0; 1888 } catch (NullPointerException e) { 1889 return 0; 1890 } 1891 1892 if (values == null) { 1893 return 0; 1894 } 1895 1896 int oldCount = values.size(); 1897 if (occurrences >= oldCount) { 1898 values.clear(); 1899 } else { 1900 Iterator<V> iterator = values.iterator(); 1901 for (int i = 0; i < occurrences; i++) { 1902 iterator.next(); 1903 iterator.remove(); 1904 } 1905 } 1906 return oldCount; 1907 } 1908 1909 @Override public void clear() { 1910 multimap().clear(); 1911 } 1912 1913 @Override public Set<K> elementSet() { 1914 return multimap().keySet(); 1915 } 1916 } 1917 1918 static abstract class Values<K, V> extends AbstractCollection<V> { 1919 abstract Multimap<K, V> multimap(); 1920 1921 @Override public Iterator<V> iterator() { 1922 final Iterator<Map.Entry<K, V>> backingIterator = 1923 multimap().entries().iterator(); 1924 return new Iterator<V>() { 1925 @Override public boolean hasNext() { 1926 return backingIterator.hasNext(); 1927 } 1928 1929 @Override public V next() { 1930 return backingIterator.next().getValue(); 1931 } 1932 1933 @Override public void remove() { 1934 backingIterator.remove(); 1935 } 1936 }; 1937 } 1938 1939 @Override public int size() { 1940 return multimap().size(); 1941 } 1942 1943 @Override public boolean contains(@Nullable Object o) { 1944 return multimap().containsValue(o); 1945 } 1946 1947 @Override public void clear() { 1948 multimap().clear(); 1949 } 1950 } 1951 1952 /** 1953 * A skeleton implementation of {@link Multimap#entries()}. 1954 */ 1955 static abstract class Entries<K, V> extends 1956 AbstractCollection<Map.Entry<K, V>> { 1957 abstract Multimap<K, V> multimap(); 1958 1959 @Override public int size() { 1960 return multimap().size(); 1961 } 1962 1963 @Override public boolean contains(@Nullable Object o) { 1964 if (o instanceof Map.Entry<?, ?>) { 1965 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1966 return multimap().containsEntry(entry.getKey(), entry.getValue()); 1967 } 1968 return false; 1969 } 1970 1971 @Override public boolean remove(@Nullable Object o) { 1972 if (o instanceof Map.Entry<?, ?>) { 1973 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1974 return multimap().remove(entry.getKey(), entry.getValue()); 1975 } 1976 return false; 1977 } 1978 1979 @Override public void clear() { 1980 multimap().clear(); 1981 } 1982 } 1983 1984 /** 1985 * A skeleton implementation of {@link SetMultimap#entries()}. 1986 */ 1987 static abstract class EntrySet<K, V> extends Entries<K, V> implements 1988 Set<Map.Entry<K, V>> { 1989 @Override public int hashCode() { 1990 return Sets.hashCodeImpl(this); 1991 } 1992 1993 @Override public boolean equals(@Nullable Object obj) { 1994 return Sets.equalsImpl(this, obj); 1995 } 1996 } 1997 1998 /** 1999 * A skeleton implementation of {@link Multimap#asMap()}. 2000 */ 2001 static abstract class AsMap<K, V> extends 2002 Maps.ImprovedAbstractMap<K, Collection<V>> { 2003 abstract Multimap<K, V> multimap(); 2004 2005 @Override public abstract int size(); 2006 2007 abstract Iterator<Entry<K, Collection<V>>> entryIterator(); 2008 2009 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() { 2010 return new EntrySet(); 2011 } 2012 2013 void removeValuesForKey(Object key){ 2014 multimap().removeAll(key); 2015 } 2016 2017 class EntrySet extends Maps.EntrySet<K, Collection<V>> { 2018 @Override Map<K, Collection<V>> map() { 2019 return AsMap.this; 2020 } 2021 2022 @Override public Iterator<Entry<K, Collection<V>>> iterator() { 2023 return entryIterator(); 2024 } 2025 2026 @Override public boolean remove(Object o) { 2027 if (!contains(o)) { 2028 return false; 2029 } 2030 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 2031 removeValuesForKey(entry.getKey()); 2032 return true; 2033 } 2034 } 2035 2036 @SuppressWarnings("unchecked") 2037 @Override public Collection<V> get(Object key) { 2038 return containsKey(key) ? multimap().get((K) key) : null; 2039 } 2040 2041 @Override public Collection<V> remove(Object key) { 2042 return containsKey(key) ? multimap().removeAll(key) : null; 2043 } 2044 2045 @Override public Set<K> keySet() { 2046 return multimap().keySet(); 2047 } 2048 2049 @Override public boolean isEmpty() { 2050 return multimap().isEmpty(); 2051 } 2052 2053 @Override public boolean containsKey(Object key) { 2054 return multimap().containsKey(key); 2055 } 2056 2057 @Override public void clear() { 2058 multimap().clear(); 2059 } 2060 } 2061 2062 /** 2063 * Support removal operations when filtering a filtered multimap. Since a 2064 * filtered multimap has iterators that don't support remove, passing one to 2065 * the FilteredMultimap constructor would lead to a multimap whose removal 2066 * operations would fail. This method combines the predicates to avoid that 2067 * problem. 2068 */ 2069 private static <K, V> Multimap<K, V> filterFiltered(FilteredMultimap<K, V> map, 2070 Predicate<? super Entry<K, V>> entryPredicate) { 2071 Predicate<Entry<K, V>> predicate 2072 = Predicates.and(map.predicate, entryPredicate); 2073 return new FilteredMultimap<K, V>(map.unfiltered, predicate); 2074 } 2075 2076 private static class FilteredMultimap<K, V> implements Multimap<K, V> { 2077 final Multimap<K, V> unfiltered; 2078 final Predicate<? super Entry<K, V>> predicate; 2079 2080 FilteredMultimap(Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) { 2081 this.unfiltered = unfiltered; 2082 this.predicate = predicate; 2083 } 2084 2085 @Override public int size() { 2086 return entries().size(); 2087 } 2088 2089 @Override public boolean isEmpty() { 2090 return entries().isEmpty(); 2091 } 2092 2093 @Override public boolean containsKey(Object key) { 2094 return asMap().containsKey(key); 2095 } 2096 2097 @Override public boolean containsValue(Object value) { 2098 return values().contains(value); 2099 } 2100 2101 // This method should be called only when key is a K and value is a V. 2102 @SuppressWarnings("unchecked") 2103 boolean satisfiesPredicate(Object key, Object value) { 2104 return predicate.apply(Maps.immutableEntry((K) key, (V) value)); 2105 } 2106 2107 @Override public boolean containsEntry(Object key, Object value) { 2108 return unfiltered.containsEntry(key, value) && satisfiesPredicate(key, value); 2109 } 2110 2111 @Override public boolean put(K key, V value) { 2112 checkArgument(satisfiesPredicate(key, value)); 2113 return unfiltered.put(key, value); 2114 } 2115 2116 @Override public boolean remove(Object key, Object value) { 2117 return containsEntry(key, value) ? unfiltered.remove(key, value) : false; 2118 } 2119 2120 @Override public boolean putAll(K key, Iterable<? extends V> values) { 2121 for (V value : values) { 2122 checkArgument(satisfiesPredicate(key, value)); 2123 } 2124 return unfiltered.putAll(key, values); 2125 } 2126 2127 @Override public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 2128 for (Entry<? extends K, ? extends V> entry : multimap.entries()) { 2129 checkArgument(satisfiesPredicate(entry.getKey(), entry.getValue())); 2130 } 2131 return unfiltered.putAll(multimap); 2132 } 2133 2134 @Override public Collection<V> replaceValues(K key, Iterable<? extends V> values) { 2135 for (V value : values) { 2136 checkArgument(satisfiesPredicate(key, value)); 2137 } 2138 // Not calling unfiltered.replaceValues() since values that don't satisify 2139 // the filter should remain in the multimap. 2140 Collection<V> oldValues = removeAll(key); 2141 unfiltered.putAll(key, values); 2142 return oldValues; 2143 } 2144 2145 @Override public Collection<V> removeAll(Object key) { 2146 List<V> removed = Lists.newArrayList(); 2147 Collection<V> values = unfiltered.asMap().get(key); 2148 if (values != null) { 2149 Iterator<V> iterator = values.iterator(); 2150 while (iterator.hasNext()) { 2151 V value = iterator.next(); 2152 if (satisfiesPredicate(key, value)) { 2153 removed.add(value); 2154 iterator.remove(); 2155 } 2156 } 2157 } 2158 if (unfiltered instanceof SetMultimap) { 2159 return Collections.unmodifiableSet(Sets.newLinkedHashSet(removed)); 2160 } else { 2161 return Collections.unmodifiableList(removed); 2162 } 2163 } 2164 2165 @Override public void clear() { 2166 entries().clear(); 2167 } 2168 2169 @Override public boolean equals(@Nullable Object object) { 2170 if (object == this) { 2171 return true; 2172 } 2173 if (object instanceof Multimap) { 2174 Multimap<?, ?> that = (Multimap<?, ?>) object; 2175 return asMap().equals(that.asMap()); 2176 } 2177 return false; 2178 } 2179 2180 @Override public int hashCode() { 2181 return asMap().hashCode(); 2182 } 2183 2184 @Override public String toString() { 2185 return asMap().toString(); 2186 } 2187 2188 class ValuePredicate implements Predicate<V> { 2189 final K key; 2190 ValuePredicate(K key) { 2191 this.key = key; 2192 } 2193 @Override public boolean apply(V value) { 2194 return satisfiesPredicate(key, value); 2195 } 2196 } 2197 2198 Collection<V> filterCollection(Collection<V> collection, Predicate<V> predicate) { 2199 if (collection instanceof Set) { 2200 return Sets.filter((Set<V>) collection, predicate); 2201 } else { 2202 return Collections2.filter(collection, predicate); 2203 } 2204 } 2205 2206 @Override public Collection<V> get(K key) { 2207 return filterCollection(unfiltered.get(key), new ValuePredicate(key)); 2208 } 2209 2210 @Override public Set<K> keySet() { 2211 return asMap().keySet(); 2212 } 2213 2214 Collection<V> values; 2215 2216 @Override public Collection<V> values() { 2217 return (values == null) ? values = new Values() : values; 2218 } 2219 2220 class Values extends Multimaps.Values<K, V> { 2221 @Override Multimap<K, V> multimap() { 2222 return FilteredMultimap.this; 2223 } 2224 2225 @Override public boolean contains(@Nullable Object o) { 2226 return Iterators.contains(iterator(), o); 2227 } 2228 2229 // Override remove methods since iterator doesn't support remove. 2230 2231 @Override public boolean remove(Object o) { 2232 Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator(); 2233 while (iterator.hasNext()) { 2234 Entry<K, V> entry = iterator.next(); 2235 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) { 2236 iterator.remove(); 2237 return true; 2238 } 2239 } 2240 return false; 2241 } 2242 2243 @Override public boolean removeAll(Collection<?> c) { 2244 boolean changed = false; 2245 Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator(); 2246 while (iterator.hasNext()) { 2247 Entry<K, V> entry = iterator.next(); 2248 if (c.contains(entry.getValue()) && predicate.apply(entry)) { 2249 iterator.remove(); 2250 changed = true; 2251 } 2252 } 2253 return changed; 2254 } 2255 2256 @Override public boolean retainAll(Collection<?> c) { 2257 boolean changed = false; 2258 Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator(); 2259 while (iterator.hasNext()) { 2260 Entry<K, V> entry = iterator.next(); 2261 if (!c.contains(entry.getValue()) && predicate.apply(entry)) { 2262 iterator.remove(); 2263 changed = true; 2264 } 2265 } 2266 return changed; 2267 } 2268 } 2269 2270 Collection<Entry<K, V>> entries; 2271 2272 @Override public Collection<Entry<K, V>> entries() { 2273 return (entries == null) 2274 ? entries = Collections2.filter(unfiltered.entries(), predicate) 2275 : entries; 2276 } 2277 2278 /** 2279 * Remove all filtered asMap() entries that satisfy the predicate. 2280 */ 2281 boolean removeEntriesIf(Predicate<Map.Entry<K, Collection<V>>> removalPredicate) { 2282 Iterator<Map.Entry<K, Collection<V>>> iterator = unfiltered.asMap().entrySet().iterator(); 2283 boolean changed = false; 2284 while (iterator.hasNext()) { 2285 // Determine whether to remove the filtered values with this key. 2286 Map.Entry<K, Collection<V>> entry = iterator.next(); 2287 K key = entry.getKey(); 2288 Collection<V> collection = entry.getValue(); 2289 Predicate<V> valuePredicate = new ValuePredicate(key); 2290 Collection<V> filteredCollection = filterCollection(collection, valuePredicate); 2291 Map.Entry<K, Collection<V>> filteredEntry = Maps.immutableEntry(key, filteredCollection); 2292 if (removalPredicate.apply(filteredEntry) && !filteredCollection.isEmpty()) { 2293 changed = true; 2294 if (Iterables.all(collection, valuePredicate)) { 2295 iterator.remove(); // Remove all values for the key. 2296 } else { 2297 filteredCollection.clear(); // Remove the filtered values only. 2298 } 2299 } 2300 } 2301 return changed; 2302 } 2303 2304 Map<K, Collection<V>> asMap; 2305 2306 @Override public Map<K, Collection<V>> asMap() { 2307 return (asMap == null) ? asMap = createAsMap() : asMap; 2308 } 2309 2310 static final Predicate<Collection<?>> NOT_EMPTY = new Predicate<Collection<?>>() { 2311 @Override public boolean apply(Collection<?> input) { 2312 return !input.isEmpty(); 2313 } 2314 }; 2315 2316 Map<K, Collection<V>> createAsMap() { 2317 // Select the values that satisify the predicate. 2318 EntryTransformer<K, Collection<V>, Collection<V>> transformer 2319 = new EntryTransformer<K, Collection<V>, Collection<V>>() { 2320 @Override public Collection<V> transformEntry(K key, Collection<V> collection) { 2321 return filterCollection(collection, new ValuePredicate(key)); 2322 } 2323 }; 2324 Map<K, Collection<V>> transformed 2325 = Maps.transformEntries(unfiltered.asMap(), transformer); 2326 2327 // Select the keys that have at least one value remaining. 2328 Map<K, Collection<V>> filtered = Maps.filterValues(transformed, NOT_EMPTY); 2329 2330 // Override the removal methods, since removing a map entry should not 2331 // affect values that don't satisfy the filter. 2332 return new AsMap(filtered); 2333 } 2334 2335 class AsMap extends ForwardingMap<K, Collection<V>> { 2336 final Map<K, Collection<V>> delegate; 2337 2338 AsMap(Map<K, Collection<V>> delegate) { 2339 this.delegate = delegate; 2340 } 2341 2342 @Override protected Map<K, Collection<V>> delegate() { 2343 return delegate; 2344 } 2345 2346 @Override public Collection<V> remove(Object o) { 2347 Collection<V> output = FilteredMultimap.this.removeAll(o); 2348 return output.isEmpty() ? null : output; 2349 } 2350 2351 @Override public void clear() { 2352 FilteredMultimap.this.clear(); 2353 } 2354 2355 Set<K> keySet; 2356 2357 @Override public Set<K> keySet() { 2358 return (keySet == null) ? keySet = new KeySet() : keySet; 2359 } 2360 2361 class KeySet extends Maps.KeySet<K, Collection<V>> { 2362 @Override Map<K, Collection<V>> map() { 2363 return AsMap.this; 2364 } 2365 2366 @Override public boolean remove(Object o) { 2367 Collection<V> collection = delegate.get(o); 2368 if (collection == null) { 2369 return false; 2370 } 2371 collection.clear(); 2372 return true; 2373 } 2374 2375 @Override public boolean removeAll(Collection<?> c) { 2376 return Sets.removeAllImpl(this, c); 2377 } 2378 2379 @Override public boolean retainAll(final Collection<?> c) { 2380 Predicate<Map.Entry<K, Collection<V>>> removalPredicate 2381 = new Predicate<Map.Entry<K, Collection<V>>>() { 2382 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { 2383 return !c.contains(entry.getKey()); 2384 } 2385 }; 2386 return removeEntriesIf(removalPredicate); 2387 } 2388 } 2389 2390 Values asMapValues; 2391 2392 @Override public Collection<Collection<V>> values() { 2393 return (asMapValues == null) ? asMapValues = new Values() : asMapValues; 2394 } 2395 2396 class Values extends Maps.Values<K, Collection<V>> { 2397 @Override Map<K, Collection<V>> map() { 2398 return AsMap.this; 2399 } 2400 2401 @Override public boolean remove(Object o) { 2402 for (Collection<V> collection : this) { 2403 if (collection.equals(o)) { 2404 collection.clear(); 2405 return true; 2406 } 2407 } 2408 return false; 2409 } 2410 2411 @Override public boolean removeAll(final Collection<?> c) { 2412 Predicate<Map.Entry<K, Collection<V>>> removalPredicate 2413 = new Predicate<Map.Entry<K, Collection<V>>>() { 2414 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { 2415 return c.contains(entry.getValue()); 2416 } 2417 }; 2418 return removeEntriesIf(removalPredicate); 2419 } 2420 2421 @Override public boolean retainAll(final Collection<?> c) { 2422 Predicate<Map.Entry<K, Collection<V>>> removalPredicate 2423 = new Predicate<Map.Entry<K, Collection<V>>>() { 2424 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { 2425 return !c.contains(entry.getValue()); 2426 } 2427 }; 2428 return removeEntriesIf(removalPredicate); 2429 } 2430 } 2431 2432 EntrySet entrySet; 2433 2434 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() { 2435 return (entrySet == null) ? entrySet = new EntrySet(super.entrySet()) : entrySet; 2436 } 2437 2438 class EntrySet extends Maps.EntrySet<K, Collection<V>> { 2439 Set<Map.Entry<K, Collection<V>>> delegateEntries; 2440 2441 public EntrySet(Set<Map.Entry<K, Collection<V>>> delegateEntries) { 2442 this.delegateEntries = delegateEntries; 2443 } 2444 2445 @Override Map<K, Collection<V>> map() { 2446 return AsMap.this; 2447 } 2448 2449 @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() { 2450 return delegateEntries.iterator(); 2451 } 2452 2453 @Override public boolean remove(Object o) { 2454 if (o instanceof Entry<?, ?>) { 2455 Entry<?, ?> entry = (Entry<?, ?>) o; 2456 Collection<V> collection = delegate.get(entry.getKey()); 2457 if (collection != null && collection.equals(entry.getValue())) { 2458 collection.clear(); 2459 return true; 2460 } 2461 } 2462 return false; 2463 } 2464 2465 @Override public boolean removeAll(Collection<?> c) { 2466 return Sets.removeAllImpl(this, c); 2467 } 2468 2469 @Override public boolean retainAll(final Collection<?> c) { 2470 Predicate<Map.Entry<K, Collection<V>>> removalPredicate 2471 = new Predicate<Map.Entry<K, Collection<V>>>() { 2472 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { 2473 return !c.contains(entry); 2474 } 2475 }; 2476 return removeEntriesIf(removalPredicate); 2477 } 2478 } 2479 } 2480 2481 AbstractMultiset<K> keys; 2482 2483 @Override public Multiset<K> keys() { 2484 return (keys == null) ? keys = new Keys() : keys; 2485 } 2486 2487 class Keys extends Multimaps.Keys<K, V> { 2488 @Override Multimap<K, V> multimap() { 2489 return FilteredMultimap.this; 2490 } 2491 2492 @Override public int remove(Object o, int occurrences) { 2493 checkArgument(occurrences >= 0); 2494 Collection<V> values = unfiltered.asMap().get(o); 2495 if (values == null) { 2496 return 0; 2497 } 2498 int priorCount = 0; 2499 int removed = 0; 2500 Iterator<V> iterator = values.iterator(); 2501 while (iterator.hasNext()) { 2502 if (satisfiesPredicate(o, iterator.next())) { 2503 priorCount++; 2504 if (removed < occurrences) { 2505 iterator.remove(); 2506 removed++; 2507 } 2508 } 2509 } 2510 return priorCount; 2511 } 2512 2513 @Override Set<Multiset.Entry<K>> createEntrySet() { 2514 return new EntrySet(); 2515 } 2516 2517 class EntrySet extends Multimaps.Keys<K, V>.KeysEntrySet { 2518 @Override public boolean removeAll(Collection<?> c) { 2519 return Sets.removeAllImpl(this, c); 2520 } 2521 2522 @Override public boolean retainAll(final Collection<?> c) { 2523 Predicate<Map.Entry<K, Collection<V>>> removalPredicate 2524 = new Predicate<Map.Entry<K, Collection<V>>>() { 2525 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { 2526 Multiset.Entry<K> multisetEntry 2527 = Multisets.immutableEntry(entry.getKey(), entry.getValue().size()); 2528 return !c.contains(multisetEntry); 2529 } 2530 }; 2531 return removeEntriesIf(removalPredicate); 2532 } 2533 } 2534 } 2535 } 2536 2537 // TODO(jlevy): Create methods that filter a SetMultimap or SortedSetMultimap. 2538} 2539 2540