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  
21  import com.google.common.annotations.Beta;
22  import com.google.common.annotations.GwtCompatible;
23  import com.google.common.annotations.GwtIncompatible;
24  import com.google.common.base.Preconditions;
25  import com.google.errorprone.annotations.CanIgnoreReturnValue;
26  import com.google.errorprone.annotations.concurrent.LazyInit;
27  import com.google.j2objc.annotations.RetainedWith;
28  import java.io.IOException;
29  import java.io.InvalidObjectException;
30  import java.io.ObjectInputStream;
31  import java.io.ObjectOutputStream;
32  import java.util.Collection;
33  import java.util.Comparator;
34  import java.util.Map.Entry;
35  import java.util.function.Function;
36  import java.util.stream.Collector;
37  import java.util.stream.Collectors;
38  import java.util.stream.Stream;
39  import javax.annotation.Nullable;
40  
41  /**
42   * A {@link ListMultimap} whose contents will never change, with many other important properties
43   * detailed at {@link ImmutableCollection}.
44   *
45   * <p>See the Guava User Guide article on <a href=
46   * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
47   * immutable collections</a>.
48   *
49   * @author Jared Levy
50   * @since 2.0
51   */
52  @GwtCompatible(serializable = true, emulated = true)
53  public class ImmutableListMultimap<K, V> extends ImmutableMultimap<K, V>
54      implements ListMultimap<K, V> {
55    /**
56     * Returns a {@link Collector} that accumulates elements into an {@code ImmutableListMultimap}
57     * whose keys and values are the result of applying the provided mapping functions to the input
58     * elements.
59     *
60     * <p>For streams with {@linkplain java.util.stream#Ordering defined encounter order}, that order
61     * is preserved, but entries are {@linkplain ImmutableMultimap#iteration grouped by key}.
62     *
63     * Example:
64     * <pre>   {@code
65     *
66     *   static final Multimap<Character, String> FIRST_LETTER_MULTIMAP =
67     *       Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
68     *           .collect(toImmutableListMultimap(str -> str.charAt(0), str -> str.substring(1)));
69     *
70     *   // is equivalent to
71     *
72     *   static final Multimap<Character, String> FIRST_LETTER_MULTIMAP =
73     *       new ImmutableListMultimap.Builder<Character, String>()
74     *           .put('b', "anana")
75     *           .putAll('a', "pple", "sparagus")
76     *           .putAll('c', "arrot", "herry")
77     *           .build();}</pre>
78     *
79     * @since 21.0
80     */
81    @Beta
82    public static <T, K, V> Collector<T, ?, ImmutableListMultimap<K, V>> toImmutableListMultimap(
83        Function<? super T, ? extends K> keyFunction,
84        Function<? super T, ? extends V> valueFunction) {
85      checkNotNull(keyFunction, "keyFunction");
86      checkNotNull(valueFunction, "valueFunction");
87      return Collector.of(
88          ImmutableListMultimap::<K, V>builder,
89          (builder, t) -> builder.put(keyFunction.apply(t), valueFunction.apply(t)),
90          ImmutableListMultimap.Builder::combine,
91          ImmutableListMultimap.Builder::build);
92    }
93    
94    /**
95     * Returns a {@code Collector} accumulating entries into an {@code ImmutableListMultimap}. Each
96     * input element is mapped to a key and a stream of values, each of which are put into the
97     * resulting {@code Multimap}, in the encounter order of the stream and the encounter order of the
98     * streams of values.
99     *
100    * <p>Example:
101    *
102    * <pre>{@code
103    * static final ImmutableListMultimap<Character, Character> FIRST_LETTER_MULTIMAP =
104    *     Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
105    *         .collect(
106    *             flatteningToImmutableListMultimap(
107    *                  str -> str.charAt(0),
108    *                  str -> str.substring(1).chars().mapToObj(c -> (char) c));
109    *
110    * // is equivalent to
111    *
112    * static final ImmutableListMultimap<Character, Character> FIRST_LETTER_MULTIMAP =
113    *     ImmutableListMultimap.<Character, Character>builder()
114    *         .putAll('b', Arrays.asList('a', 'n', 'a', 'n', 'a'))
115    *         .putAll('a', Arrays.asList('p', 'p', 'l', 'e'))
116    *         .putAll('c', Arrays.asList('a', 'r', 'r', 'o', 't'))
117    *         .putAll('a', Arrays.asList('s', 'p', 'a', 'r', 'a', 'g', 'u', 's'))
118    *         .putAll('c', Arrays.asList('h', 'e', 'r', 'r', 'y'))
119    *         .build();
120    * }
121    * }</pre>
122    *
123    * @since 21.0
124    */
125   @Beta
126   public static <T, K, V>
127       Collector<T, ?, ImmutableListMultimap<K, V>> flatteningToImmutableListMultimap(
128           Function<? super T, ? extends K> keyFunction,
129           Function<? super T, ? extends Stream<? extends V>> valuesFunction) {
130     checkNotNull(keyFunction);
131     checkNotNull(valuesFunction);
132     return Collectors.collectingAndThen(
133         Multimaps.flatteningToMultimap(
134             input -> checkNotNull(keyFunction.apply(input)),
135             input -> valuesFunction.apply(input).peek(Preconditions::checkNotNull),
136             MultimapBuilder.linkedHashKeys().arrayListValues()::<K, V>build),
137         ImmutableListMultimap::copyOf);
138   }
139 
140   /** Returns the empty multimap. */
141   // Casting is safe because the multimap will never hold any elements.
142   @SuppressWarnings("unchecked")
143   public static <K, V> ImmutableListMultimap<K, V> of() {
144     return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE;
145   }
146 
147   /**
148    * Returns an immutable multimap containing a single entry.
149    */
150   public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) {
151     ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
152     builder.put(k1, v1);
153     return builder.build();
154   }
155 
156   /**
157    * Returns an immutable multimap containing the given entries, in order.
158    */
159   public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) {
160     ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
161     builder.put(k1, v1);
162     builder.put(k2, v2);
163     return builder.build();
164   }
165 
166   /**
167    * Returns an immutable multimap containing the given entries, in order.
168    */
169   public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
170     ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
171     builder.put(k1, v1);
172     builder.put(k2, v2);
173     builder.put(k3, v3);
174     return builder.build();
175   }
176 
177   /**
178    * Returns an immutable multimap containing the given entries, in order.
179    */
180   public static <K, V> ImmutableListMultimap<K, V> of(
181       K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
182     ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
183     builder.put(k1, v1);
184     builder.put(k2, v2);
185     builder.put(k3, v3);
186     builder.put(k4, v4);
187     return builder.build();
188   }
189 
190   /**
191    * Returns an immutable multimap containing the given entries, in order.
192    */
193   public static <K, V> ImmutableListMultimap<K, V> of(
194       K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
195     ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
196     builder.put(k1, v1);
197     builder.put(k2, v2);
198     builder.put(k3, v3);
199     builder.put(k4, v4);
200     builder.put(k5, v5);
201     return builder.build();
202   }
203 
204   // looking for of() with > 5 entries? Use the builder instead.
205 
206   /**
207    * Returns a new builder. The generated builder is equivalent to the builder
208    * created by the {@link Builder} constructor.
209    */
210   public static <K, V> Builder<K, V> builder() {
211     return new Builder<>();
212   }
213 
214   /**
215    * A builder for creating immutable {@code ListMultimap} instances, especially
216    * {@code public static final} multimaps ("constant multimaps"). Example:
217    * <pre>   {@code
218    *
219    *   static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
220    *       new ImmutableListMultimap.Builder<String, Integer>()
221    *           .put("one", 1)
222    *           .putAll("several", 1, 2, 3)
223    *           .putAll("many", 1, 2, 3, 4, 5)
224    *           .build();}</pre>
225    *
226    * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
227    * times to build multiple multimaps in series. Each multimap contains the
228    * key-value mappings in the previously created multimaps.
229    *
230    * @since 2.0
231    */
232   public static final class Builder<K, V> extends ImmutableMultimap.Builder<K, V> {
233     /**
234      * Creates a new builder. The returned builder is equivalent to the builder
235      * generated by {@link ImmutableListMultimap#builder}.
236      */
237     public Builder() {}
238 
239     @CanIgnoreReturnValue
240     @Override
241     public Builder<K, V> put(K key, V value) {
242       super.put(key, value);
243       return this;
244     }
245 
246     /**
247      * {@inheritDoc}
248      *
249      * @since 11.0
250      */
251     @CanIgnoreReturnValue
252     @Override
253     public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
254       super.put(entry);
255       return this;
256     }
257 
258     /**
259      * {@inheritDoc}
260      *
261      * @since 19.0
262      */
263     @CanIgnoreReturnValue
264     @Beta
265     @Override
266     public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
267       super.putAll(entries);
268       return this;
269     }
270 
271     @CanIgnoreReturnValue
272     @Override
273     public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
274       super.putAll(key, values);
275       return this;
276     }
277 
278     @CanIgnoreReturnValue
279     @Override
280     public Builder<K, V> putAll(K key, V... values) {
281       super.putAll(key, values);
282       return this;
283     }
284 
285     @CanIgnoreReturnValue
286     @Override
287     public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
288       super.putAll(multimap);
289       return this;
290     }
291 
292     @CanIgnoreReturnValue
293     @Override
294     Builder<K, V> combine(ImmutableMultimap.Builder<K, V> other) {
295       super.combine(other);
296       return this;
297     }
298 
299     /**
300      * {@inheritDoc}
301      *
302      * @since 8.0
303      */
304     @CanIgnoreReturnValue
305     @Override
306     public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
307       super.orderKeysBy(keyComparator);
308       return this;
309     }
310 
311     /**
312      * {@inheritDoc}
313      *
314      * @since 8.0
315      */
316     @CanIgnoreReturnValue
317     @Override
318     public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
319       super.orderValuesBy(valueComparator);
320       return this;
321     }
322 
323     /**
324      * Returns a newly-created immutable list multimap.
325      */
326     @Override
327     public ImmutableListMultimap<K, V> build() {
328       return (ImmutableListMultimap<K, V>) super.build();
329     }
330   }
331 
332   /**
333    * Returns an immutable multimap containing the same mappings as {@code
334    * multimap}. The generated multimap's key and value orderings correspond to
335    * the iteration ordering of the {@code multimap.asMap()} view.
336    *
337    * <p>Despite the method name, this method attempts to avoid actually copying
338    * the data when it is safe to do so. The exact circumstances under which a
339    * copy will or will not be performed are undocumented and subject to change.
340    *
341    * @throws NullPointerException if any key or value in {@code multimap} is
342    *         null
343    */
344   public static <K, V> ImmutableListMultimap<K, V> copyOf(
345       Multimap<? extends K, ? extends V> multimap) {
346     if (multimap.isEmpty()) {
347       return of();
348     }
349 
350     // TODO(lowasser): copy ImmutableSetMultimap by using asList() on the sets
351     if (multimap instanceof ImmutableListMultimap) {
352       @SuppressWarnings("unchecked") // safe since multimap is not writable
353       ImmutableListMultimap<K, V> kvMultimap = (ImmutableListMultimap<K, V>) multimap;
354       if (!kvMultimap.isPartialView()) {
355         return kvMultimap;
356       }
357     }
358 
359     ImmutableMap.Builder<K, ImmutableList<V>> builder =
360         new ImmutableMap.Builder<>(multimap.asMap().size());
361     int size = 0;
362 
363     for (Entry<? extends K, ? extends Collection<? extends V>> entry :
364         multimap.asMap().entrySet()) {
365       ImmutableList<V> list = ImmutableList.copyOf(entry.getValue());
366       if (!list.isEmpty()) {
367         builder.put(entry.getKey(), list);
368         size += list.size();
369       }
370     }
371 
372     return new ImmutableListMultimap<>(builder.build(), size);
373   }
374 
375   /**
376    * Returns an immutable multimap containing the specified entries.  The
377    * returned multimap iterates over keys in the order they were first
378    * encountered in the input, and the values for each key are iterated in the
379    * order they were encountered.
380    *
381    * @throws NullPointerException if any key, value, or entry is null
382    * @since 19.0
383    */
384   @Beta
385   public static <K, V> ImmutableListMultimap<K, V> copyOf(
386       Iterable<? extends Entry<? extends K, ? extends V>> entries) {
387     return new Builder<K, V>().putAll(entries).build();
388   }
389 
390   ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) {
391     super(map, size);
392   }
393 
394   // views
395 
396   /**
397    * Returns an immutable list of the values for the given key.  If no mappings
398    * in the multimap have the provided key, an empty immutable list is
399    * returned. The values are in the same order as the parameters used to build
400    * this multimap.
401    */
402   @Override
403   public ImmutableList<V> get(@Nullable K key) {
404     // This cast is safe as its type is known in constructor.
405     ImmutableList<V> list = (ImmutableList<V>) map.get(key);
406     return (list == null) ? ImmutableList.<V>of() : list;
407   }
408 
409   @LazyInit
410   @RetainedWith
411   private transient ImmutableListMultimap<V, K> inverse;
412 
413   /**
414    * {@inheritDoc}
415    *
416    * <p>Because an inverse of a list multimap can contain multiple pairs with
417    * the same key and value, this method returns an {@code
418    * ImmutableListMultimap} rather than the {@code ImmutableMultimap} specified
419    * in the {@code ImmutableMultimap} class.
420    *
421    * @since 11.0
422    */
423   @Override
424   public ImmutableListMultimap<V, K> inverse() {
425     ImmutableListMultimap<V, K> result = inverse;
426     return (result == null) ? (inverse = invert()) : result;
427   }
428 
429   private ImmutableListMultimap<V, K> invert() {
430     Builder<V, K> builder = builder();
431     for (Entry<K, V> entry : entries()) {
432       builder.put(entry.getValue(), entry.getKey());
433     }
434     ImmutableListMultimap<V, K> invertedMultimap = builder.build();
435     invertedMultimap.inverse = this;
436     return invertedMultimap;
437   }
438 
439   /**
440    * Guaranteed to throw an exception and leave the multimap unmodified.
441    *
442    * @throws UnsupportedOperationException always
443    * @deprecated Unsupported operation.
444    */
445   @CanIgnoreReturnValue
446   @Deprecated
447   @Override
448   public ImmutableList<V> removeAll(Object key) {
449     throw new UnsupportedOperationException();
450   }
451 
452   /**
453    * Guaranteed to throw an exception and leave the multimap unmodified.
454    *
455    * @throws UnsupportedOperationException always
456    * @deprecated Unsupported operation.
457    */
458   @CanIgnoreReturnValue
459   @Deprecated
460   @Override
461   public ImmutableList<V> replaceValues(K key, Iterable<? extends V> values) {
462     throw new UnsupportedOperationException();
463   }
464 
465   /**
466    * @serialData number of distinct keys, and then for each distinct key: the
467    *     key, the number of values for that key, and the key's values
468    */
469   @GwtIncompatible // java.io.ObjectOutputStream
470   private void writeObject(ObjectOutputStream stream) throws IOException {
471     stream.defaultWriteObject();
472     Serialization.writeMultimap(this, stream);
473   }
474 
475   @GwtIncompatible // java.io.ObjectInputStream
476   private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
477     stream.defaultReadObject();
478     int keyCount = stream.readInt();
479     if (keyCount < 0) {
480       throw new InvalidObjectException("Invalid key count " + keyCount);
481     }
482     ImmutableMap.Builder<Object, ImmutableList<Object>> builder = ImmutableMap.builder();
483     int tmpSize = 0;
484 
485     for (int i = 0; i < keyCount; i++) {
486       Object key = stream.readObject();
487       int valueCount = stream.readInt();
488       if (valueCount <= 0) {
489         throw new InvalidObjectException("Invalid value count " + valueCount);
490       }
491 
492       ImmutableList.Builder<Object> valuesBuilder = ImmutableList.builder();
493       for (int j = 0; j < valueCount; j++) {
494         valuesBuilder.add(stream.readObject());
495       }
496       builder.put(key, valuesBuilder.build());
497       tmpSize += valueCount;
498     }
499 
500     ImmutableMap<Object, ImmutableList<Object>> tmpMap;
501     try {
502       tmpMap = builder.build();
503     } catch (IllegalArgumentException e) {
504       throw (InvalidObjectException) new InvalidObjectException(e.getMessage()).initCause(e);
505     }
506 
507     FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
508     FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
509   }
510 
511   @GwtIncompatible // Not needed in emulated source
512   private static final long serialVersionUID = 0;
513 }