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