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 com.google.common.annotations.GwtCompatible;
020import com.google.common.annotations.GwtIncompatible;
021import com.google.common.annotations.J2ktIncompatible;
022import com.google.errorprone.annotations.CanIgnoreReturnValue;
023import com.google.errorprone.annotations.DoNotCall;
024import com.google.errorprone.annotations.concurrent.LazyInit;
025import com.google.j2objc.annotations.RetainedWith;
026import java.io.IOException;
027import java.io.InvalidObjectException;
028import java.io.ObjectInputStream;
029import java.io.ObjectOutputStream;
030import java.util.Collection;
031import java.util.Comparator;
032import java.util.Map;
033import java.util.Map.Entry;
034import java.util.function.Function;
035import java.util.stream.Collector;
036import java.util.stream.Stream;
037import javax.annotation.CheckForNull;
038import org.checkerframework.checker.nullness.qual.Nullable;
039
040/**
041 * A {@link ListMultimap} whose contents will never change, with many other important properties
042 * detailed at {@link ImmutableCollection}.
043 *
044 * <p>See the Guava User Guide article on <a href=
045 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
046 *
047 * @author Jared Levy
048 * @since 2.0
049 */
050@GwtCompatible(serializable = true, emulated = true)
051@ElementTypesAreNonnullByDefault
052public class ImmutableListMultimap<K, V> extends ImmutableMultimap<K, V>
053    implements ListMultimap<K, V> {
054  /**
055   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableListMultimap}
056   * whose keys and values are the result of applying the provided mapping functions to the input
057   * elements.
058   *
059   * <p>For streams with defined encounter order (as defined in the Ordering section of the {@link
060   * java.util.stream} Javadoc), that order is preserved, but entries are <a
061   * href="ImmutableMultimap.html#iteration">grouped by key</a>.
062   *
063   * <p>Example:
064   *
065   * <pre>{@code
066   * static final Multimap<Character, String> FIRST_LETTER_MULTIMAP =
067   *     Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
068   *         .collect(toImmutableListMultimap(str -> str.charAt(0), str -> str.substring(1)));
069   *
070   * // is equivalent to
071   *
072   * static final Multimap<Character, String> FIRST_LETTER_MULTIMAP =
073   *     new ImmutableListMultimap.Builder<Character, String>()
074   *         .put('b', "anana")
075   *         .putAll('a', "pple", "sparagus")
076   *         .putAll('c', "arrot", "herry")
077   *         .build();
078   * }</pre>
079   *
080   * @since 21.0
081   */
082  public static <T extends @Nullable Object, K, V>
083      Collector<T, ?, ImmutableListMultimap<K, V>> toImmutableListMultimap(
084          Function<? super T, ? extends K> keyFunction,
085          Function<? super T, ? extends V> valueFunction) {
086    return CollectCollectors.toImmutableListMultimap(keyFunction, valueFunction);
087  }
088
089  /**
090   * Returns a {@code Collector} accumulating entries into an {@code ImmutableListMultimap}. Each
091   * input element is mapped to a key and a stream of values, each of which are put into the
092   * resulting {@code Multimap}, in the encounter order of the stream and the encounter order of the
093   * streams of values.
094   *
095   * <p>Example:
096   *
097   * <pre>{@code
098   * static final ImmutableListMultimap<Character, Character> FIRST_LETTER_MULTIMAP =
099   *     Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
100   *         .collect(
101   *             flatteningToImmutableListMultimap(
102   *                  str -> str.charAt(0),
103   *                  str -> str.substring(1).chars().mapToObj(c -> (char) c));
104   *
105   * // is equivalent to
106   *
107   * static final ImmutableListMultimap<Character, Character> FIRST_LETTER_MULTIMAP =
108   *     ImmutableListMultimap.<Character, Character>builder()
109   *         .putAll('b', Arrays.asList('a', 'n', 'a', 'n', 'a'))
110   *         .putAll('a', Arrays.asList('p', 'p', 'l', 'e'))
111   *         .putAll('c', Arrays.asList('a', 'r', 'r', 'o', 't'))
112   *         .putAll('a', Arrays.asList('s', 'p', 'a', 'r', 'a', 'g', 'u', 's'))
113   *         .putAll('c', Arrays.asList('h', 'e', 'r', 'r', 'y'))
114   *         .build();
115   * }
116   * }</pre>
117   *
118   * @since 21.0
119   */
120  public static <T extends @Nullable Object, K, V>
121      Collector<T, ?, ImmutableListMultimap<K, V>> flatteningToImmutableListMultimap(
122          Function<? super T, ? extends K> keyFunction,
123          Function<? super T, ? extends Stream<? extends V>> valuesFunction) {
124    return CollectCollectors.flatteningToImmutableListMultimap(keyFunction, valuesFunction);
125  }
126
127  /**
128   * Returns the empty multimap.
129   *
130   * <p><b>Performance note:</b> the instance returned is a singleton.
131   */
132  // Casting is safe because the multimap will never hold any elements.
133  @SuppressWarnings("unchecked")
134  public static <K, V> ImmutableListMultimap<K, V> of() {
135    return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE;
136  }
137
138  /** Returns an immutable multimap containing a single entry. */
139  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) {
140    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
141    builder.put(k1, v1);
142    return builder.build();
143  }
144
145  /** Returns an immutable multimap containing the given entries, in order. */
146  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) {
147    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
148    builder.put(k1, v1);
149    builder.put(k2, v2);
150    return builder.build();
151  }
152
153  /** Returns an immutable multimap containing the given entries, in order. */
154  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
155    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
156    builder.put(k1, v1);
157    builder.put(k2, v2);
158    builder.put(k3, v3);
159    return builder.build();
160  }
161
162  /** Returns an immutable multimap containing the given entries, in order. */
163  public static <K, V> ImmutableListMultimap<K, V> of(
164      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
165    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
166    builder.put(k1, v1);
167    builder.put(k2, v2);
168    builder.put(k3, v3);
169    builder.put(k4, v4);
170    return builder.build();
171  }
172
173  /** Returns an immutable multimap containing the given entries, in order. */
174  public static <K, V> ImmutableListMultimap<K, V> of(
175      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
176    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
177    builder.put(k1, v1);
178    builder.put(k2, v2);
179    builder.put(k3, v3);
180    builder.put(k4, v4);
181    builder.put(k5, v5);
182    return builder.build();
183  }
184
185  // looking for of() with > 5 entries? Use the builder instead.
186
187  /**
188   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
189   * Builder} constructor.
190   */
191  public static <K, V> Builder<K, V> builder() {
192    return new Builder<>();
193  }
194
195  /**
196   * A builder for creating immutable {@code ListMultimap} instances, especially {@code public
197   * static final} multimaps ("constant multimaps"). Example:
198   *
199   * <pre>{@code
200   * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
201   *     new ImmutableListMultimap.Builder<String, Integer>()
202   *         .put("one", 1)
203   *         .putAll("several", 1, 2, 3)
204   *         .putAll("many", 1, 2, 3, 4, 5)
205   *         .build();
206   * }</pre>
207   *
208   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
209   * multiple multimaps in series. Each multimap contains the key-value mappings in the previously
210   * created multimaps.
211   *
212   * @since 2.0
213   */
214  public static final class Builder<K, V> extends ImmutableMultimap.Builder<K, V> {
215    /**
216     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
217     * ImmutableListMultimap#builder}.
218     */
219    public Builder() {}
220
221    @CanIgnoreReturnValue
222    @Override
223    public Builder<K, V> put(K key, V value) {
224      super.put(key, value);
225      return this;
226    }
227
228    /**
229     * {@inheritDoc}
230     *
231     * @since 11.0
232     */
233    @CanIgnoreReturnValue
234    @Override
235    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
236      super.put(entry);
237      return this;
238    }
239
240    /**
241     * {@inheritDoc}
242     *
243     * @since 19.0
244     */
245    @CanIgnoreReturnValue
246    @Override
247    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
248      super.putAll(entries);
249      return this;
250    }
251
252    @CanIgnoreReturnValue
253    @Override
254    public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
255      super.putAll(key, values);
256      return this;
257    }
258
259    @CanIgnoreReturnValue
260    @Override
261    public Builder<K, V> putAll(K key, V... values) {
262      super.putAll(key, values);
263      return this;
264    }
265
266    @CanIgnoreReturnValue
267    @Override
268    public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
269      super.putAll(multimap);
270      return this;
271    }
272
273    @CanIgnoreReturnValue
274    @Override
275    Builder<K, V> combine(ImmutableMultimap.Builder<K, V> other) {
276      super.combine(other);
277      return this;
278    }
279
280    /**
281     * {@inheritDoc}
282     *
283     * @since 8.0
284     */
285    @CanIgnoreReturnValue
286    @Override
287    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
288      super.orderKeysBy(keyComparator);
289      return this;
290    }
291
292    /**
293     * {@inheritDoc}
294     *
295     * @since 8.0
296     */
297    @CanIgnoreReturnValue
298    @Override
299    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
300      super.orderValuesBy(valueComparator);
301      return this;
302    }
303
304    /** Returns a newly-created immutable list multimap. */
305    @Override
306    public ImmutableListMultimap<K, V> build() {
307      return (ImmutableListMultimap<K, V>) super.build();
308    }
309  }
310
311  /**
312   * Returns an immutable multimap containing the same mappings as {@code multimap}. The generated
313   * multimap's key and value orderings correspond to the iteration ordering of the {@code
314   * multimap.asMap()} view.
315   *
316   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
317   * safe to do so. The exact circumstances under which a copy will or will not be performed are
318   * undocumented and subject to change.
319   *
320   * @throws NullPointerException if any key or value in {@code multimap} is null
321   */
322  public static <K, V> ImmutableListMultimap<K, V> copyOf(
323      Multimap<? extends K, ? extends V> multimap) {
324    if (multimap.isEmpty()) {
325      return of();
326    }
327
328    // TODO(lowasser): copy ImmutableSetMultimap by using asList() on the sets
329    if (multimap instanceof ImmutableListMultimap) {
330      @SuppressWarnings("unchecked") // safe since multimap is not writable
331      ImmutableListMultimap<K, V> kvMultimap = (ImmutableListMultimap<K, V>) multimap;
332      if (!kvMultimap.isPartialView()) {
333        return kvMultimap;
334      }
335    }
336
337    return fromMapEntries(multimap.asMap().entrySet(), null);
338  }
339
340  /**
341   * Returns an immutable multimap containing the specified entries. The returned multimap iterates
342   * over keys in the order they were first encountered in the input, and the values for each key
343   * are iterated in the order they were encountered.
344   *
345   * @throws NullPointerException if any key, value, or entry is null
346   * @since 19.0
347   */
348  public static <K, V> ImmutableListMultimap<K, V> copyOf(
349      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
350    return new Builder<K, V>().putAll(entries).build();
351  }
352
353  /** Creates an ImmutableListMultimap from an asMap.entrySet. */
354  static <K, V> ImmutableListMultimap<K, V> fromMapEntries(
355      Collection<? extends Map.Entry<? extends K, ? extends Collection<? extends V>>> mapEntries,
356      @CheckForNull Comparator<? super V> valueComparator) {
357    if (mapEntries.isEmpty()) {
358      return of();
359    }
360    ImmutableMap.Builder<K, ImmutableList<V>> builder =
361        new ImmutableMap.Builder<>(mapEntries.size());
362    int size = 0;
363
364    for (Entry<? extends K, ? extends Collection<? extends V>> entry : mapEntries) {
365      K key = entry.getKey();
366      Collection<? extends V> values = entry.getValue();
367      ImmutableList<V> list =
368          (valueComparator == null)
369              ? ImmutableList.copyOf(values)
370              : ImmutableList.sortedCopyOf(valueComparator, values);
371      if (!list.isEmpty()) {
372        builder.put(key, list);
373        size += list.size();
374      }
375    }
376
377    return new ImmutableListMultimap<>(builder.buildOrThrow(), size);
378  }
379
380  ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) {
381    super(map, size);
382  }
383
384  // views
385
386  /**
387   * Returns an immutable list of the values for the given key. If no mappings in the multimap have
388   * the provided key, an empty immutable list is returned. The values are in the same order as the
389   * parameters used to build this multimap.
390   */
391  @Override
392  public ImmutableList<V> get(K key) {
393    // This cast is safe as its type is known in constructor.
394    ImmutableList<V> list = (ImmutableList<V>) map.get(key);
395    return (list == null) ? ImmutableList.<V>of() : list;
396  }
397
398  @LazyInit @RetainedWith @CheckForNull private transient ImmutableListMultimap<V, K> inverse;
399
400  /**
401   * {@inheritDoc}
402   *
403   * <p>Because an inverse of a list multimap can contain multiple pairs with the same key and
404   * value, this method returns an {@code ImmutableListMultimap} rather than the {@code
405   * ImmutableMultimap} specified in the {@code ImmutableMultimap} class.
406   *
407   * @since 11.0
408   */
409  @Override
410  public ImmutableListMultimap<V, K> inverse() {
411    ImmutableListMultimap<V, K> result = inverse;
412    return (result == null) ? (inverse = invert()) : result;
413  }
414
415  private ImmutableListMultimap<V, K> invert() {
416    Builder<V, K> builder = builder();
417    for (Entry<K, V> entry : entries()) {
418      builder.put(entry.getValue(), entry.getKey());
419    }
420    ImmutableListMultimap<V, K> invertedMultimap = builder.build();
421    invertedMultimap.inverse = this;
422    return invertedMultimap;
423  }
424
425  /**
426   * Guaranteed to throw an exception and leave the multimap unmodified.
427   *
428   * @throws UnsupportedOperationException always
429   * @deprecated Unsupported operation.
430   */
431  @CanIgnoreReturnValue
432  @Deprecated
433  @Override
434  @DoNotCall("Always throws UnsupportedOperationException")
435  public final ImmutableList<V> removeAll(@CheckForNull Object key) {
436    throw new UnsupportedOperationException();
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  @DoNotCall("Always throws UnsupportedOperationException")
449  public final ImmutableList<V> replaceValues(K key, Iterable<? extends V> values) {
450    throw new UnsupportedOperationException();
451  }
452
453  /**
454   * @serialData number of distinct keys, and then for each distinct key: the key, the number of
455   *     values for that key, and the key's values
456   */
457  @GwtIncompatible // java.io.ObjectOutputStream
458  @J2ktIncompatible
459  private void writeObject(ObjectOutputStream stream) throws IOException {
460    stream.defaultWriteObject();
461    Serialization.writeMultimap(this, stream);
462  }
463
464  @GwtIncompatible // java.io.ObjectInputStream
465  @J2ktIncompatible
466  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
467    stream.defaultReadObject();
468    int keyCount = stream.readInt();
469    if (keyCount < 0) {
470      throw new InvalidObjectException("Invalid key count " + keyCount);
471    }
472    ImmutableMap.Builder<Object, ImmutableList<Object>> builder = ImmutableMap.builder();
473    int tmpSize = 0;
474
475    for (int i = 0; i < keyCount; i++) {
476      Object key = stream.readObject();
477      int valueCount = stream.readInt();
478      if (valueCount <= 0) {
479        throw new InvalidObjectException("Invalid value count " + valueCount);
480      }
481
482      ImmutableList.Builder<Object> valuesBuilder = ImmutableList.builder();
483      for (int j = 0; j < valueCount; j++) {
484        valuesBuilder.add(stream.readObject());
485      }
486      builder.put(key, valuesBuilder.build());
487      tmpSize += valueCount;
488    }
489
490    ImmutableMap<Object, ImmutableList<Object>> tmpMap;
491    try {
492      tmpMap = builder.buildOrThrow();
493    } catch (IllegalArgumentException e) {
494      throw (InvalidObjectException) new InvalidObjectException(e.getMessage()).initCause(e);
495    }
496
497    FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
498    FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
499  }
500
501  @GwtIncompatible // Not needed in emulated source
502  @J2ktIncompatible
503  private static final long serialVersionUID = 0;
504}