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