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