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