001/* 002 * Copyright (C) 2008 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.checkEntryNotNull; 021 022import com.google.common.annotations.Beta; 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.GwtIncompatible; 025import com.google.errorprone.annotations.CanIgnoreReturnValue; 026import com.google.j2objc.annotations.Weak; 027import com.google.j2objc.annotations.WeakOuter; 028import java.io.Serializable; 029import java.util.Arrays; 030import java.util.Collection; 031import java.util.Collections; 032import java.util.Comparator; 033import java.util.Iterator; 034import java.util.List; 035import java.util.Map; 036import java.util.Map.Entry; 037import java.util.Spliterator; 038import java.util.function.BiConsumer; 039import javax.annotation.Nullable; 040 041/** 042 * A {@link Multimap} whose contents will never change, with many other important properties 043 * detailed at {@link ImmutableCollection}. 044 * 045 * <p><b>Warning:</b> avoid <i>direct</i> usage of {@link ImmutableMultimap} as a type (as with 046 * {@link Multimap} itself). Prefer subtypes such as {@link ImmutableSetMultimap} or {@link 047 * ImmutableListMultimap}, which have well-defined {@link #equals} semantics, thus avoiding a common 048 * source of bugs and confusion. 049 * 050 * <p><b>Note:</b> every {@link ImmutableMultimap} offers an {@link #inverse} view, so there is no 051 * need for a distinct {@code ImmutableBiMultimap} type. 052 * 053 * <a name="iteration"></a> 054 * <p><b>Key-grouped iteration.</b> All view collections follow the same iteration order. In all 055 * current implementations, the iteration order always keeps multiple entries with the same key 056 * together. Any creation method that would customarily respect insertion order (such as {@link 057 * #copyOf(Multimap)}) instead preserves key-grouped order by inserting entries for an existing key 058 * immediately after the last entry having that key. 059 * 060 * <p>See the Guava User Guide article on <a href= 061 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> 062 * immutable collections</a>. 063 * 064 * @author Jared Levy 065 * @since 2.0 066 */ 067@GwtCompatible(emulated = true) 068public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> 069 implements Serializable { 070 071 /** Returns an empty multimap. */ 072 public static <K, V> ImmutableMultimap<K, V> of() { 073 return ImmutableListMultimap.of(); 074 } 075 076 /** 077 * Returns an immutable multimap containing a single entry. 078 */ 079 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) { 080 return ImmutableListMultimap.of(k1, v1); 081 } 082 083 /** 084 * Returns an immutable multimap containing the given entries, in order. 085 */ 086 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) { 087 return ImmutableListMultimap.of(k1, v1, k2, v2); 088 } 089 090 /** 091 * Returns an immutable multimap containing the given entries, in the 092 * "key-grouped" insertion order described in the 093 * <a href="#iteration">class documentation</a>. 094 */ 095 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) { 096 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3); 097 } 098 099 /** 100 * Returns an immutable multimap containing the given entries, in the 101 * "key-grouped" insertion order described in the 102 * <a href="#iteration">class documentation</a>. 103 */ 104 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 105 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4); 106 } 107 108 /** 109 * Returns an immutable multimap containing the given entries, in the 110 * "key-grouped" insertion order described in the 111 * <a href="#iteration">class documentation</a>. 112 */ 113 public static <K, V> ImmutableMultimap<K, V> of( 114 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 115 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5); 116 } 117 118 // looking for of() with > 5 entries? Use the builder instead. 119 120 /** 121 * Returns a new builder. The generated builder is equivalent to the builder 122 * created by the {@link Builder} constructor. 123 */ 124 public static <K, V> Builder<K, V> builder() { 125 return new Builder<K, V>(); 126 } 127 128 /** 129 * A builder for creating immutable multimap instances, especially 130 * {@code public static final} multimaps ("constant multimaps"). Example: 131 * <pre> {@code 132 * 133 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP = 134 * new ImmutableMultimap.Builder<String, Integer>() 135 * .put("one", 1) 136 * .putAll("several", 1, 2, 3) 137 * .putAll("many", 1, 2, 3, 4, 5) 138 * .build();}</pre> 139 * 140 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple 141 * times to build multiple multimaps in series. Each multimap contains the 142 * key-value mappings in the previously created multimaps. 143 * 144 * @since 2.0 145 */ 146 public static class Builder<K, V> { 147 Multimap<K, V> builderMultimap; 148 Comparator<? super K> keyComparator; 149 Comparator<? super V> valueComparator; 150 151 /** 152 * Creates a new builder. The returned builder is equivalent to the builder 153 * generated by {@link ImmutableMultimap#builder}. 154 */ 155 public Builder() { 156 this(MultimapBuilder.linkedHashKeys().arrayListValues().<K, V>build()); 157 } 158 159 Builder(Multimap<K, V> builderMultimap) { 160 this.builderMultimap = builderMultimap; 161 } 162 163 /** 164 * Adds a key-value mapping to the built multimap. 165 */ 166 @CanIgnoreReturnValue 167 public Builder<K, V> put(K key, V value) { 168 checkEntryNotNull(key, value); 169 builderMultimap.put(key, value); 170 return this; 171 } 172 173 /** 174 * Adds an entry to the built multimap. 175 * 176 * @since 11.0 177 */ 178 @CanIgnoreReturnValue 179 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 180 return put(entry.getKey(), entry.getValue()); 181 } 182 183 /** 184 * Adds entries to the built multimap. 185 * 186 * @since 19.0 187 */ 188 @CanIgnoreReturnValue 189 @Beta 190 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 191 for (Entry<? extends K, ? extends V> entry : entries) { 192 put(entry); 193 } 194 return this; 195 } 196 197 /** 198 * Stores a collection of values with the same key in the built multimap. 199 * 200 * @throws NullPointerException if {@code key}, {@code values}, or any 201 * element in {@code values} is null. The builder is left in an invalid 202 * state. 203 */ 204 @CanIgnoreReturnValue 205 public Builder<K, V> putAll(K key, Iterable<? extends V> values) { 206 if (key == null) { 207 throw new NullPointerException("null key in entry: null=" + Iterables.toString(values)); 208 } 209 Collection<V> valueList = builderMultimap.get(key); 210 for (V value : values) { 211 checkEntryNotNull(key, value); 212 valueList.add(value); 213 } 214 return this; 215 } 216 217 /** 218 * Stores an array of values with the same key in the built multimap. 219 * 220 * @throws NullPointerException if the key or any value is null. The builder 221 * is left in an invalid state. 222 */ 223 @CanIgnoreReturnValue 224 public Builder<K, V> putAll(K key, V... values) { 225 return putAll(key, Arrays.asList(values)); 226 } 227 228 /** 229 * Stores another multimap's entries in the built multimap. The generated 230 * multimap's key and value orderings correspond to the iteration ordering 231 * of the {@code multimap.asMap()} view, with new keys and values following 232 * any existing keys and values. 233 * 234 * @throws NullPointerException if any key or value in {@code multimap} is 235 * null. The builder is left in an invalid state. 236 */ 237 @CanIgnoreReturnValue 238 public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) { 239 for (Entry<? extends K, ? extends Collection<? extends V>> entry : 240 multimap.asMap().entrySet()) { 241 putAll(entry.getKey(), entry.getValue()); 242 } 243 return this; 244 } 245 246 /** 247 * Specifies the ordering of the generated multimap's keys. 248 * 249 * @since 8.0 250 */ 251 @CanIgnoreReturnValue 252 public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) { 253 this.keyComparator = checkNotNull(keyComparator); 254 return this; 255 } 256 257 /** 258 * Specifies the ordering of the generated multimap's values for each key. 259 * 260 * @since 8.0 261 */ 262 @CanIgnoreReturnValue 263 public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) { 264 this.valueComparator = checkNotNull(valueComparator); 265 return this; 266 } 267 268 @CanIgnoreReturnValue 269 Builder<K, V> combine(Builder<K, V> other) { 270 putAll(other.builderMultimap); 271 return this; 272 } 273 274 /** 275 * Returns a newly-created immutable multimap. 276 */ 277 public ImmutableMultimap<K, V> build() { 278 if (valueComparator != null) { 279 for (Collection<V> values : builderMultimap.asMap().values()) { 280 List<V> list = (List<V>) values; 281 Collections.sort(list, valueComparator); 282 } 283 } 284 if (keyComparator != null) { 285 Multimap<K, V> sortedCopy = 286 MultimapBuilder.linkedHashKeys().arrayListValues().<K, V>build(); 287 List<Map.Entry<K, Collection<V>>> entries = 288 Ordering.from(keyComparator) 289 .<K>onKeys() 290 .immutableSortedCopy(builderMultimap.asMap().entrySet()); 291 for (Map.Entry<K, Collection<V>> entry : entries) { 292 sortedCopy.putAll(entry.getKey(), entry.getValue()); 293 } 294 builderMultimap = sortedCopy; 295 } 296 return copyOf(builderMultimap); 297 } 298 } 299 300 /** 301 * Returns an immutable multimap containing the same mappings as {@code 302 * multimap}, in the "key-grouped" iteration order described in the class 303 * documentation. 304 * 305 * <p>Despite the method name, this method attempts to avoid actually copying 306 * the data when it is safe to do so. The exact circumstances under which a 307 * copy will or will not be performed are undocumented and subject to change. 308 * 309 * @throws NullPointerException if any key or value in {@code multimap} is 310 * null 311 */ 312 public static <K, V> ImmutableMultimap<K, V> copyOf(Multimap<? extends K, ? extends V> multimap) { 313 if (multimap instanceof ImmutableMultimap) { 314 @SuppressWarnings("unchecked") // safe since multimap is not writable 315 ImmutableMultimap<K, V> kvMultimap = (ImmutableMultimap<K, V>) multimap; 316 if (!kvMultimap.isPartialView()) { 317 return kvMultimap; 318 } 319 } 320 return ImmutableListMultimap.copyOf(multimap); 321 } 322 323 /** 324 * Returns an immutable multimap containing the specified entries. The 325 * returned multimap iterates over keys in the order they were first 326 * encountered in the input, and the values for each key are iterated in the 327 * order they were encountered. 328 * 329 * @throws NullPointerException if any key, value, or entry is null 330 * @since 19.0 331 */ 332 @Beta 333 public static <K, V> ImmutableMultimap<K, V> copyOf( 334 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 335 return ImmutableListMultimap.copyOf(entries); 336 } 337 338 final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map; 339 final transient int size; 340 341 // These constants allow the deserialization code to set final fields. This 342 // holder class makes sure they are not initialized unless an instance is 343 // deserialized. 344 @GwtIncompatible // java serialization is not supported 345 static class FieldSettersHolder { 346 static final Serialization.FieldSetter<ImmutableMultimap> MAP_FIELD_SETTER = 347 Serialization.getFieldSetter(ImmutableMultimap.class, "map"); 348 static final Serialization.FieldSetter<ImmutableMultimap> SIZE_FIELD_SETTER = 349 Serialization.getFieldSetter(ImmutableMultimap.class, "size"); 350 static final Serialization.FieldSetter<ImmutableSetMultimap> EMPTY_SET_FIELD_SETTER = 351 Serialization.getFieldSetter(ImmutableSetMultimap.class, "emptySet"); 352 } 353 354 ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, int size) { 355 this.map = map; 356 this.size = size; 357 } 358 359 // mutators (not supported) 360 361 /** 362 * Guaranteed to throw an exception and leave the multimap unmodified. 363 * 364 * @throws UnsupportedOperationException always 365 * @deprecated Unsupported operation. 366 */ 367 @CanIgnoreReturnValue 368 @Deprecated 369 @Override 370 public ImmutableCollection<V> removeAll(Object key) { 371 throw new UnsupportedOperationException(); 372 } 373 374 /** 375 * Guaranteed to throw an exception and leave the multimap unmodified. 376 * 377 * @throws UnsupportedOperationException always 378 * @deprecated Unsupported operation. 379 */ 380 @CanIgnoreReturnValue 381 @Deprecated 382 @Override 383 public ImmutableCollection<V> replaceValues(K key, Iterable<? extends V> values) { 384 throw new UnsupportedOperationException(); 385 } 386 387 /** 388 * Guaranteed to throw an exception and leave the multimap unmodified. 389 * 390 * @throws UnsupportedOperationException always 391 * @deprecated Unsupported operation. 392 */ 393 @Deprecated 394 @Override 395 public void clear() { 396 throw new UnsupportedOperationException(); 397 } 398 399 /** 400 * Returns an immutable collection of the values for the given key. If no 401 * mappings in the multimap have the provided key, an empty immutable 402 * collection is returned. The values are in the same order as the parameters 403 * used to build this multimap. 404 */ 405 @Override 406 public abstract ImmutableCollection<V> get(K key); 407 408 /** 409 * Returns an immutable multimap which is the inverse of this one. For every 410 * key-value mapping in the original, the result will have a mapping with 411 * key and value reversed. 412 * 413 * @since 11.0 414 */ 415 public abstract ImmutableMultimap<V, K> inverse(); 416 417 /** 418 * Guaranteed to throw an exception and leave the multimap unmodified. 419 * 420 * @throws UnsupportedOperationException always 421 * @deprecated Unsupported operation. 422 */ 423 @CanIgnoreReturnValue 424 @Deprecated 425 @Override 426 public boolean put(K key, V value) { 427 throw new UnsupportedOperationException(); 428 } 429 430 /** 431 * Guaranteed to throw an exception and leave the multimap unmodified. 432 * 433 * @throws UnsupportedOperationException always 434 * @deprecated Unsupported operation. 435 */ 436 @CanIgnoreReturnValue 437 @Deprecated 438 @Override 439 public boolean putAll(K key, Iterable<? extends V> values) { 440 throw new UnsupportedOperationException(); 441 } 442 443 /** 444 * Guaranteed to throw an exception and leave the multimap unmodified. 445 * 446 * @throws UnsupportedOperationException always 447 * @deprecated Unsupported operation. 448 */ 449 @CanIgnoreReturnValue 450 @Deprecated 451 @Override 452 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 453 throw new UnsupportedOperationException(); 454 } 455 456 /** 457 * Guaranteed to throw an exception and leave the multimap unmodified. 458 * 459 * @throws UnsupportedOperationException always 460 * @deprecated Unsupported operation. 461 */ 462 @CanIgnoreReturnValue 463 @Deprecated 464 @Override 465 public boolean remove(Object key, Object value) { 466 throw new UnsupportedOperationException(); 467 } 468 469 /** 470 * Returns {@code true} if this immutable multimap's implementation contains references to 471 * user-created objects that aren't accessible via this multimap's methods. This is generally 472 * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid 473 * memory leaks. 474 */ 475 boolean isPartialView() { 476 return map.isPartialView(); 477 } 478 479 // accessors 480 481 @Override 482 public boolean containsKey(@Nullable Object key) { 483 return map.containsKey(key); 484 } 485 486 @Override 487 public boolean containsValue(@Nullable Object value) { 488 return value != null && super.containsValue(value); 489 } 490 491 @Override 492 public int size() { 493 return size; 494 } 495 496 // views 497 498 /** 499 * Returns an immutable set of the distinct keys in this multimap, in the same 500 * order as they appear in this multimap. 501 */ 502 @Override 503 public ImmutableSet<K> keySet() { 504 return map.keySet(); 505 } 506 507 /** 508 * Returns an immutable map that associates each key with its corresponding 509 * values in the multimap. Keys and values appear in the same order as in this 510 * multimap. 511 */ 512 @Override 513 @SuppressWarnings("unchecked") // a widening cast 514 public ImmutableMap<K, Collection<V>> asMap() { 515 return (ImmutableMap) map; 516 } 517 518 @Override 519 Map<K, Collection<V>> createAsMap() { 520 throw new AssertionError("should never be called"); 521 } 522 523 /** 524 * Returns an immutable collection of all key-value pairs in the multimap. 525 */ 526 @Override 527 public ImmutableCollection<Entry<K, V>> entries() { 528 return (ImmutableCollection<Entry<K, V>>) super.entries(); 529 } 530 531 @Override 532 ImmutableCollection<Entry<K, V>> createEntries() { 533 return new EntryCollection<K, V>(this); 534 } 535 536 private static class EntryCollection<K, V> extends ImmutableCollection<Entry<K, V>> { 537 @Weak final ImmutableMultimap<K, V> multimap; 538 539 EntryCollection(ImmutableMultimap<K, V> multimap) { 540 this.multimap = multimap; 541 } 542 543 @Override 544 public UnmodifiableIterator<Entry<K, V>> iterator() { 545 return multimap.entryIterator(); 546 } 547 548 @Override 549 boolean isPartialView() { 550 return multimap.isPartialView(); 551 } 552 553 @Override 554 public int size() { 555 return multimap.size(); 556 } 557 558 @Override 559 public boolean contains(Object object) { 560 if (object instanceof Entry) { 561 Entry<?, ?> entry = (Entry<?, ?>) object; 562 return multimap.containsEntry(entry.getKey(), entry.getValue()); 563 } 564 return false; 565 } 566 567 private static final long serialVersionUID = 0; 568 } 569 570 private abstract class Itr<T> extends UnmodifiableIterator<T> { 571 final Iterator<Entry<K, Collection<V>>> mapIterator = asMap().entrySet().iterator(); 572 K key = null; 573 Iterator<V> valueIterator = Iterators.emptyIterator(); 574 575 abstract T output(K key, V value); 576 577 @Override 578 public boolean hasNext() { 579 return mapIterator.hasNext() || valueIterator.hasNext(); 580 } 581 582 @Override 583 public T next() { 584 if (!valueIterator.hasNext()) { 585 Entry<K, Collection<V>> mapEntry = mapIterator.next(); 586 key = mapEntry.getKey(); 587 valueIterator = mapEntry.getValue().iterator(); 588 } 589 return output(key, valueIterator.next()); 590 } 591 } 592 593 @Override 594 UnmodifiableIterator<Entry<K, V>> entryIterator() { 595 return new Itr<Entry<K, V>>() { 596 @Override 597 Entry<K, V> output(K key, V value) { 598 return Maps.immutableEntry(key, value); 599 } 600 }; 601 } 602 603 @Override 604 Spliterator<Entry<K, V>> entrySpliterator() { 605 return CollectSpliterators.flatMap( 606 asMap().entrySet().spliterator(), 607 keyToValueCollectionEntry -> { 608 K key = keyToValueCollectionEntry.getKey(); 609 Collection<V> valueCollection = keyToValueCollectionEntry.getValue(); 610 return CollectSpliterators.map( 611 valueCollection.spliterator(), (V value) -> Maps.immutableEntry(key, value)); 612 }, 613 Spliterator.SIZED | (this instanceof SetMultimap ? Spliterator.DISTINCT : 0), 614 size()); 615 } 616 617 @Override 618 public void forEach(BiConsumer<? super K, ? super V> action) { 619 checkNotNull(action); 620 asMap() 621 .forEach( 622 (key, valueCollection) -> valueCollection.forEach(value -> action.accept(key, value))); 623 } 624 625 /** 626 * Returns an immutable multiset containing all the keys in this multimap, in 627 * the same order and with the same frequencies as they appear in this 628 * multimap; to get only a single occurrence of each key, use {@link #keySet}. 629 */ 630 @Override 631 public ImmutableMultiset<K> keys() { 632 return (ImmutableMultiset<K>) super.keys(); 633 } 634 635 @Override 636 ImmutableMultiset<K> createKeys() { 637 return new Keys(); 638 } 639 640 @SuppressWarnings("serial") // Uses writeReplace, not default serialization 641 @WeakOuter 642 class Keys extends ImmutableMultiset<K> { 643 @Override 644 public boolean contains(@Nullable Object object) { 645 return containsKey(object); 646 } 647 648 @Override 649 public int count(@Nullable Object element) { 650 Collection<V> values = map.get(element); 651 return (values == null) ? 0 : values.size(); 652 } 653 654 @Override 655 public ImmutableSet<K> elementSet() { 656 return keySet(); 657 } 658 659 @Override 660 public int size() { 661 return ImmutableMultimap.this.size(); 662 } 663 664 @Override 665 Multiset.Entry<K> getEntry(int index) { 666 Map.Entry<K, ? extends Collection<V>> entry = map.entrySet().asList().get(index); 667 return Multisets.immutableEntry(entry.getKey(), entry.getValue().size()); 668 } 669 670 @Override 671 boolean isPartialView() { 672 return true; 673 } 674 } 675 676 /** 677 * Returns an immutable collection of the values in this multimap. Its 678 * iterator traverses the values for the first key, the values for the second 679 * key, and so on. 680 */ 681 @Override 682 public ImmutableCollection<V> values() { 683 return (ImmutableCollection<V>) super.values(); 684 } 685 686 @Override 687 ImmutableCollection<V> createValues() { 688 return new Values<K, V>(this); 689 } 690 691 @Override 692 UnmodifiableIterator<V> valueIterator() { 693 return new Itr<V>() { 694 @Override 695 V output(K key, V value) { 696 return value; 697 } 698 }; 699 } 700 701 private static final class Values<K, V> extends ImmutableCollection<V> { 702 @Weak private final transient ImmutableMultimap<K, V> multimap; 703 704 Values(ImmutableMultimap<K, V> multimap) { 705 this.multimap = multimap; 706 } 707 708 @Override 709 public boolean contains(@Nullable Object object) { 710 return multimap.containsValue(object); 711 } 712 713 @Override 714 public UnmodifiableIterator<V> iterator() { 715 return multimap.valueIterator(); 716 } 717 718 @GwtIncompatible // not present in emulated superclass 719 @Override 720 int copyIntoArray(Object[] dst, int offset) { 721 for (ImmutableCollection<V> valueCollection : multimap.map.values()) { 722 offset = valueCollection.copyIntoArray(dst, offset); 723 } 724 return offset; 725 } 726 727 @Override 728 public int size() { 729 return multimap.size(); 730 } 731 732 @Override 733 boolean isPartialView() { 734 return true; 735 } 736 737 private static final long serialVersionUID = 0; 738 } 739 740 private static final long serialVersionUID = 0; 741}