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.j2objc.annotations.Weak;
026import com.google.j2objc.annotations.WeakOuter;
027
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.Set;
038
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<K, V>();
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    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    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
178      return put(entry.getKey(), entry.getValue());
179    }
180
181    /**
182     * Adds entries to the built multimap.
183     *
184     * @since 19.0
185     */
186    @Beta
187    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
188      for (Entry<? extends K, ? extends V> entry : entries) {
189        put(entry);
190      }
191      return this;
192    }
193
194    /**
195     * Stores a collection of values with the same key in the built multimap.
196     *
197     * @throws NullPointerException if {@code key}, {@code values}, or any
198     *     element in {@code values} is null. The builder is left in an invalid
199     *     state.
200     */
201    public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
202      if (key == null) {
203        throw new NullPointerException("null key in entry: null=" + Iterables.toString(values));
204      }
205      Collection<V> valueList = builderMultimap.get(key);
206      for (V value : values) {
207        checkEntryNotNull(key, value);
208        valueList.add(value);
209      }
210      return this;
211    }
212
213    /**
214     * Stores an array of values with the same key in the built multimap.
215     *
216     * @throws NullPointerException if the key or any value is null. The builder
217     *     is left in an invalid state.
218     */
219    public Builder<K, V> putAll(K key, V... values) {
220      return putAll(key, Arrays.asList(values));
221    }
222
223    /**
224     * Stores another multimap's entries in the built multimap. The generated
225     * multimap's key and value orderings correspond to the iteration ordering
226     * of the {@code multimap.asMap()} view, with new keys and values following
227     * any existing keys and values.
228     *
229     * @throws NullPointerException if any key or value in {@code multimap} is
230     *     null. The builder is left in an invalid state.
231     */
232    public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
233      for (Entry<? extends K, ? extends Collection<? extends V>> entry :
234          multimap.asMap().entrySet()) {
235        putAll(entry.getKey(), entry.getValue());
236      }
237      return this;
238    }
239
240    /**
241     * Specifies the ordering of the generated multimap's keys.
242     *
243     * @since 8.0
244     */
245    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
246      this.keyComparator = checkNotNull(keyComparator);
247      return this;
248    }
249
250    /**
251     * Specifies the ordering of the generated multimap's values for each key.
252     *
253     * @since 8.0
254     */
255    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
256      this.valueComparator = checkNotNull(valueComparator);
257      return this;
258    }
259
260    /**
261     * Returns a newly-created immutable multimap.
262     */
263    public ImmutableMultimap<K, V> build() {
264      if (valueComparator != null) {
265        for (Collection<V> values : builderMultimap.asMap().values()) {
266          List<V> list = (List<V>) values;
267          Collections.sort(list, valueComparator);
268        }
269      }
270      if (keyComparator != null) {
271        Multimap<K, V> sortedCopy =
272            MultimapBuilder.linkedHashKeys().arrayListValues().<K, V>build();
273        List<Map.Entry<K, Collection<V>>> entries =
274            Ordering.from(keyComparator)
275                .<K>onKeys()
276                .immutableSortedCopy(builderMultimap.asMap().entrySet());
277        for (Map.Entry<K, Collection<V>> entry : entries) {
278          sortedCopy.putAll(entry.getKey(), entry.getValue());
279        }
280        builderMultimap = sortedCopy;
281      }
282      return copyOf(builderMultimap);
283    }
284  }
285
286  /**
287   * Returns an immutable multimap containing the same mappings as {@code
288   * multimap}, in the "key-grouped" iteration order described in the class
289   * documentation.
290   *
291   * <p>Despite the method name, this method attempts to avoid actually copying
292   * the data when it is safe to do so. The exact circumstances under which a
293   * copy will or will not be performed are undocumented and subject to change.
294   *
295   * @throws NullPointerException if any key or value in {@code multimap} is
296   *         null
297   */
298  public static <K, V> ImmutableMultimap<K, V> copyOf(Multimap<? extends K, ? extends V> multimap) {
299    if (multimap instanceof ImmutableMultimap) {
300      @SuppressWarnings("unchecked") // safe since multimap is not writable
301      ImmutableMultimap<K, V> kvMultimap = (ImmutableMultimap<K, V>) multimap;
302      if (!kvMultimap.isPartialView()) {
303        return kvMultimap;
304      }
305    }
306    return ImmutableListMultimap.copyOf(multimap);
307  }
308
309  /**
310   * Returns an immutable multimap containing the specified entries.  The
311   * returned multimap iterates over keys in the order they were first
312   * encountered in the input, and the values for each key are iterated in the
313   * order they were encountered.
314   *
315   * @throws NullPointerException if any key, value, or entry is null
316   * @since 19.0
317   */
318  @Beta
319  public static <K, V> ImmutableMultimap<K, V> copyOf(
320      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
321    return ImmutableListMultimap.copyOf(entries);
322  }
323
324  final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map;
325  final transient int size;
326
327  // These constants allow the deserialization code to set final fields. This
328  // holder class makes sure they are not initialized unless an instance is
329  // deserialized.
330  @GwtIncompatible("java serialization is not supported")
331  static class FieldSettersHolder {
332    static final Serialization.FieldSetter<ImmutableMultimap> MAP_FIELD_SETTER =
333        Serialization.getFieldSetter(ImmutableMultimap.class, "map");
334    static final Serialization.FieldSetter<ImmutableMultimap> SIZE_FIELD_SETTER =
335        Serialization.getFieldSetter(ImmutableMultimap.class, "size");
336    static final Serialization.FieldSetter<ImmutableSetMultimap> EMPTY_SET_FIELD_SETTER =
337        Serialization.getFieldSetter(ImmutableSetMultimap.class, "emptySet");
338  }
339
340  ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, int size) {
341    this.map = map;
342    this.size = size;
343  }
344
345  // mutators (not supported)
346
347  /**
348   * Guaranteed to throw an exception and leave the multimap unmodified.
349   *
350   * @throws UnsupportedOperationException always
351   * @deprecated Unsupported operation.
352   */
353  @Deprecated
354  @Override
355  public ImmutableCollection<V> removeAll(Object key) {
356    throw new UnsupportedOperationException();
357  }
358
359  /**
360   * Guaranteed to throw an exception and leave the multimap unmodified.
361   *
362   * @throws UnsupportedOperationException always
363   * @deprecated Unsupported operation.
364   */
365  @Deprecated
366  @Override
367  public ImmutableCollection<V> replaceValues(K key, Iterable<? extends V> values) {
368    throw new UnsupportedOperationException();
369  }
370
371  /**
372   * Guaranteed to throw an exception and leave the multimap unmodified.
373   *
374   * @throws UnsupportedOperationException always
375   * @deprecated Unsupported operation.
376   */
377  @Deprecated
378  @Override
379  public void clear() {
380    throw new UnsupportedOperationException();
381  }
382
383  /**
384   * Returns an immutable collection of the values for the given key.  If no
385   * mappings in the multimap have the provided key, an empty immutable
386   * collection is returned. The values are in the same order as the parameters
387   * used to build this multimap.
388   */
389  @Override
390  public abstract ImmutableCollection<V> get(K key);
391
392  /**
393   * Returns an immutable multimap which is the inverse of this one. For every
394   * key-value mapping in the original, the result will have a mapping with
395   * key and value reversed.
396   *
397   * @since 11.0
398   */
399  public abstract ImmutableMultimap<V, K> inverse();
400
401  /**
402   * Guaranteed to throw an exception and leave the multimap unmodified.
403   *
404   * @throws UnsupportedOperationException always
405   * @deprecated Unsupported operation.
406   */
407  @Deprecated
408  @Override
409  public boolean put(K key, V value) {
410    throw new UnsupportedOperationException();
411  }
412
413  /**
414   * Guaranteed to throw an exception and leave the multimap unmodified.
415   *
416   * @throws UnsupportedOperationException always
417   * @deprecated Unsupported operation.
418   */
419  @Deprecated
420  @Override
421  public boolean putAll(K key, Iterable<? extends V> values) {
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  @Deprecated
432  @Override
433  public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
434    throw new UnsupportedOperationException();
435  }
436
437  /**
438   * Guaranteed to throw an exception and leave the multimap unmodified.
439   *
440   * @throws UnsupportedOperationException always
441   * @deprecated Unsupported operation.
442   */
443  @Deprecated
444  @Override
445  public boolean remove(Object key, Object value) {
446    throw new UnsupportedOperationException();
447  }
448
449  /**
450   * Returns {@code true} if this immutable multimap's implementation contains references to
451   * user-created objects that aren't accessible via this multimap's methods. This is generally
452   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
453   * memory leaks.
454   */
455  boolean isPartialView() {
456    return map.isPartialView();
457  }
458
459  // accessors
460
461  @Override
462  public boolean containsKey(@Nullable Object key) {
463    return map.containsKey(key);
464  }
465
466  @Override
467  public boolean containsValue(@Nullable Object value) {
468    return value != null && super.containsValue(value);
469  }
470
471  @Override
472  public int size() {
473    return size;
474  }
475
476  // views
477
478  /**
479   * Returns an immutable set of the distinct keys in this multimap, in the same
480   * order as they appear in this multimap.
481   */
482  @Override
483  public ImmutableSet<K> keySet() {
484    return map.keySet();
485  }
486
487  /**
488   * Returns an immutable map that associates each key with its corresponding
489   * values in the multimap. Keys and values appear in the same order as in this
490   * multimap.
491   */
492  @Override
493  @SuppressWarnings("unchecked") // a widening cast
494  public ImmutableMap<K, Collection<V>> asMap() {
495    return (ImmutableMap) map;
496  }
497
498  @Override
499  Map<K, Collection<V>> createAsMap() {
500    throw new AssertionError("should never be called");
501  }
502
503  /**
504   * Returns an immutable collection of all key-value pairs in the multimap.
505   */
506  @Override
507  public ImmutableCollection<Entry<K, V>> entries() {
508    return (ImmutableCollection<Entry<K, V>>) super.entries();
509  }
510
511  @Override
512  ImmutableCollection<Entry<K, V>> createEntries() {
513    return new EntryCollection<K, V>(this);
514  }
515
516  private static class EntryCollection<K, V> extends ImmutableCollection<Entry<K, V>> {
517    @Weak final ImmutableMultimap<K, V> multimap;
518
519    EntryCollection(ImmutableMultimap<K, V> multimap) {
520      this.multimap = multimap;
521    }
522
523    @Override
524    public UnmodifiableIterator<Entry<K, V>> iterator() {
525      return multimap.entryIterator();
526    }
527
528    @Override
529    boolean isPartialView() {
530      return multimap.isPartialView();
531    }
532
533    @Override
534    public int size() {
535      return multimap.size();
536    }
537
538    @Override
539    public boolean contains(Object object) {
540      if (object instanceof Entry) {
541        Entry<?, ?> entry = (Entry<?, ?>) object;
542        return multimap.containsEntry(entry.getKey(), entry.getValue());
543      }
544      return false;
545    }
546
547    private static final long serialVersionUID = 0;
548  }
549
550  private abstract class Itr<T> extends UnmodifiableIterator<T> {
551    final Iterator<Entry<K, Collection<V>>> mapIterator = asMap().entrySet().iterator();
552    K key = null;
553    Iterator<V> valueIterator = Iterators.emptyIterator();
554
555    abstract T output(K key, V value);
556
557    @Override
558    public boolean hasNext() {
559      return mapIterator.hasNext() || valueIterator.hasNext();
560    }
561
562    @Override
563    public T next() {
564      if (!valueIterator.hasNext()) {
565        Entry<K, Collection<V>> mapEntry = mapIterator.next();
566        key = mapEntry.getKey();
567        valueIterator = mapEntry.getValue().iterator();
568      }
569      return output(key, valueIterator.next());
570    }
571  }
572
573  @Override
574  UnmodifiableIterator<Entry<K, V>> entryIterator() {
575    return new Itr<Entry<K, V>>() {
576      @Override
577      Entry<K, V> output(K key, V value) {
578        return Maps.immutableEntry(key, value);
579      }
580    };
581  }
582
583  /**
584   * Returns an immutable multiset containing all the keys in this multimap, in
585   * the same order and with the same frequencies as they appear in this
586   * multimap; to get only a single occurrence of 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(@Nullable Object object) {
603      return containsKey(object);
604    }
605
606    @Override
607    public int count(@Nullable Object element) {
608      Collection<V> values = map.get(element);
609      return (values == null) ? 0 : values.size();
610    }
611
612    @Override
613    public Set<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
634  /**
635   * Returns an immutable collection of the values in this multimap. Its
636   * iterator traverses the values for the first key, the values for the second
637   * key, and so on.
638   */
639  @Override
640  public ImmutableCollection<V> values() {
641    return (ImmutableCollection<V>) super.values();
642  }
643
644  @Override
645  ImmutableCollection<V> createValues() {
646    return new Values<K, V>(this);
647  }
648
649  @Override
650  UnmodifiableIterator<V> valueIterator() {
651    return new Itr<V>() {
652      @Override
653      V output(K key, V value) {
654        return value;
655      }
656    };
657  }
658
659  private static final class Values<K, V> extends ImmutableCollection<V> {
660    @Weak private final transient ImmutableMultimap<K, V> multimap;
661
662    Values(ImmutableMultimap<K, V> multimap) {
663      this.multimap = multimap;
664    }
665
666    @Override
667    public boolean contains(@Nullable Object object) {
668      return multimap.containsValue(object);
669    }
670
671    @Override
672    public UnmodifiableIterator<V> iterator() {
673      return multimap.valueIterator();
674    }
675
676    @GwtIncompatible("not present in emulated superclass")
677    @Override
678    int copyIntoArray(Object[] dst, int offset) {
679      for (ImmutableCollection<V> valueCollection : multimap.map.values()) {
680        offset = valueCollection.copyIntoArray(dst, offset);
681      }
682      return offset;
683    }
684
685    @Override
686    public int size() {
687      return multimap.size();
688    }
689
690    @Override
691    boolean isPartialView() {
692      return true;
693    }
694
695    private static final long serialVersionUID = 0;
696  }
697
698  private static final long serialVersionUID = 0;
699}