View Javadoc
1   /*
2    * Copyright (C) 2008 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
21  
22  import com.google.common.annotations.Beta;
23  import com.google.common.annotations.GwtCompatible;
24  import com.google.common.annotations.GwtIncompatible;
25  import com.google.errorprone.annotations.CanIgnoreReturnValue;
26  import com.google.j2objc.annotations.Weak;
27  import com.google.j2objc.annotations.WeakOuter;
28  import java.io.Serializable;
29  import java.util.Arrays;
30  import java.util.Collection;
31  import java.util.Collections;
32  import java.util.Comparator;
33  import java.util.Iterator;
34  import java.util.List;
35  import java.util.Map;
36  import java.util.Map.Entry;
37  import java.util.Spliterator;
38  import java.util.function.BiConsumer;
39  import javax.annotation.Nullable;
40  
41  /**
42   * A {@link Multimap} whose contents will never change, with many other important properties
43   * detailed at {@link ImmutableCollection}.
44   *
45   * <p><b>Warning:</b> avoid <i>direct</i> usage of {@link ImmutableMultimap} as a type (as with
46   * {@link Multimap} itself). Prefer subtypes such as {@link ImmutableSetMultimap} or {@link
47   * ImmutableListMultimap}, which have well-defined {@link #equals} semantics, thus avoiding a common
48   * source of bugs and confusion.
49   *
50   * <p><b>Note:</b> every {@link ImmutableMultimap} offers an {@link #inverse} view, so there is no
51   * need for a distinct {@code ImmutableBiMultimap} type.
52   *
53   * <a name="iteration"></a>
54   * <p><b>Key-grouped iteration.</b> All view collections follow the same iteration order. In all
55   * current implementations, the iteration order always keeps multiple entries with the same key
56   * together. Any creation method that would customarily respect insertion order (such as {@link
57   * #copyOf(Multimap)}) instead preserves key-grouped order by inserting entries for an existing key
58   * immediately after the last entry having that key.
59   *
60   * <p>See the Guava User Guide article on <a href=
61   * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
62   * immutable collections</a>.
63   *
64   * @author Jared Levy
65   * @since 2.0
66   */
67  @GwtCompatible(emulated = true)
68  public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V>
69      implements Serializable {
70  
71    /** Returns an empty multimap. */
72    public static <K, V> ImmutableMultimap<K, V> of() {
73      return ImmutableListMultimap.of();
74    }
75  
76    /**
77     * Returns an immutable multimap containing a single entry.
78     */
79    public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) {
80      return ImmutableListMultimap.of(k1, v1);
81    }
82  
83    /**
84     * Returns an immutable multimap containing the given entries, in order.
85     */
86    public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) {
87      return ImmutableListMultimap.of(k1, v1, k2, v2);
88    }
89  
90    /**
91     * Returns an immutable multimap containing the given entries, in the
92     * "key-grouped" insertion order described in the
93     * <a href="#iteration">class documentation</a>.
94     */
95    public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
96      return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3);
97    }
98  
99    /**
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 }