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<>();
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<>(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<>(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}