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
17package com.google.common.collect;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.annotations.GwtIncompatible;
21
22import java.io.IOException;
23import java.io.InvalidObjectException;
24import java.io.ObjectInputStream;
25import java.io.ObjectOutputStream;
26import java.util.Collection;
27import java.util.Comparator;
28import java.util.Map.Entry;
29
30import javax.annotation.Nullable;
31
32/**
33 * An immutable {@link ListMultimap} with reliable user-specified key and value
34 * iteration order. Does not permit null keys or values.
35 *
36 * <p>Unlike {@link Multimaps#unmodifiableListMultimap(ListMultimap)}, which is
37 * a <i>view</i> of a separate multimap which can still change, an instance of
38 * {@code ImmutableListMultimap} contains its own data and will <i>never</i>
39 * change. {@code ImmutableListMultimap} is convenient for
40 * {@code public static final} multimaps ("constant multimaps") and also lets
41 * you easily make a "defensive copy" of a multimap provided to your class by
42 * a caller.
43 *
44 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
45 * it has no public or protected constructors. Thus, instances of this class
46 * are guaranteed to be immutable.
47 *
48 * <p>See the Guava User Guide article on <a href=
49 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
50 * immutable collections</a>.
51 *
52 * @author Jared Levy
53 * @since 2.0 (imported from Google Collections Library)
54 */
55@GwtCompatible(serializable = true, emulated = true)
56public class ImmutableListMultimap<K, V>
57    extends ImmutableMultimap<K, V>
58    implements ListMultimap<K, V> {
59
60  /** Returns the empty multimap. */
61  // Casting is safe because the multimap will never hold any elements.
62  @SuppressWarnings("unchecked")
63  public static <K, V> ImmutableListMultimap<K, V> of() {
64    return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE;
65  }
66
67  /**
68   * Returns an immutable multimap containing a single entry.
69   */
70  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) {
71    ImmutableListMultimap.Builder<K, V> builder
72        = ImmutableListMultimap.builder();
73    builder.put(k1, v1);
74    return builder.build();
75  }
76
77  /**
78   * Returns an immutable multimap containing the given entries, in order.
79   */
80  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) {
81    ImmutableListMultimap.Builder<K, V> builder
82        = ImmutableListMultimap.builder();
83    builder.put(k1, v1);
84    builder.put(k2, v2);
85    return builder.build();
86  }
87
88  /**
89   * Returns an immutable multimap containing the given entries, in order.
90   */
91  public static <K, V> ImmutableListMultimap<K, V> of(
92      K k1, V v1, K k2, V v2, K k3, V v3) {
93    ImmutableListMultimap.Builder<K, V> builder
94        = ImmutableListMultimap.builder();
95    builder.put(k1, v1);
96    builder.put(k2, v2);
97    builder.put(k3, v3);
98    return builder.build();
99  }
100
101  /**
102   * Returns an immutable multimap containing the given entries, in order.
103   */
104  public static <K, V> ImmutableListMultimap<K, V> of(
105      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
106    ImmutableListMultimap.Builder<K, V> builder
107        = ImmutableListMultimap.builder();
108    builder.put(k1, v1);
109    builder.put(k2, v2);
110    builder.put(k3, v3);
111    builder.put(k4, v4);
112    return builder.build();
113  }
114
115  /**
116   * Returns an immutable multimap containing the given entries, in order.
117   */
118  public static <K, V> ImmutableListMultimap<K, V> of(
119      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
120    ImmutableListMultimap.Builder<K, V> builder
121        = ImmutableListMultimap.builder();
122    builder.put(k1, v1);
123    builder.put(k2, v2);
124    builder.put(k3, v3);
125    builder.put(k4, v4);
126    builder.put(k5, v5);
127    return builder.build();
128  }
129
130  // looking for of() with > 5 entries? Use the builder instead.
131
132  /**
133   * Returns a new builder. The generated builder is equivalent to the builder
134   * created by the {@link Builder} constructor.
135   */
136  public static <K, V> Builder<K, V> builder() {
137    return new Builder<K, V>();
138  }
139
140  /**
141   * A builder for creating immutable {@code ListMultimap} instances, especially
142   * {@code public static final} multimaps ("constant multimaps"). Example:
143   * <pre>   {@code
144   *
145   *   static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
146   *       new ImmutableListMultimap.Builder<String, Integer>()
147   *           .put("one", 1)
148   *           .putAll("several", 1, 2, 3)
149   *           .putAll("many", 1, 2, 3, 4, 5)
150   *           .build();}</pre>
151   *
152   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
153   * times to build multiple multimaps in series. Each multimap contains the
154   * key-value mappings in the previously created multimaps.
155   *
156   * @since 2.0 (imported from Google Collections Library)
157   */
158  public static final class Builder<K, V>
159      extends ImmutableMultimap.Builder<K, V> {
160    /**
161     * Creates a new builder. The returned builder is equivalent to the builder
162     * generated by {@link ImmutableListMultimap#builder}.
163     */
164    public Builder() {}
165
166    @Override public Builder<K, V> put(K key, V value) {
167      super.put(key, value);
168      return this;
169    }
170
171    /**
172     * {@inheritDoc}
173     *
174     * @since 11.0
175     */
176    @Override public Builder<K, V> put(
177        Entry<? extends K, ? extends V> entry) {
178      super.put(entry);
179      return this;
180    }
181
182    @Override public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
183      super.putAll(key, values);
184      return this;
185    }
186
187    @Override public Builder<K, V> putAll(K key, V... values) {
188      super.putAll(key, values);
189      return this;
190    }
191
192    @Override public Builder<K, V> putAll(
193        Multimap<? extends K, ? extends V> multimap) {
194      super.putAll(multimap);
195      return this;
196    }
197
198    /**
199     * {@inheritDoc}
200     *
201     * @since 8.0
202     */
203    @Override
204    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
205      super.orderKeysBy(keyComparator);
206      return this;
207    }
208
209    /**
210     * {@inheritDoc}
211     *
212     * @since 8.0
213     */
214    @Override
215    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
216      super.orderValuesBy(valueComparator);
217      return this;
218    }
219
220    /**
221     * Returns a newly-created immutable list multimap.
222     */
223    @Override public ImmutableListMultimap<K, V> build() {
224      return (ImmutableListMultimap<K, V>) super.build();
225    }
226  }
227
228  /**
229   * Returns an immutable multimap containing the same mappings as {@code
230   * multimap}. The generated multimap's key and value orderings correspond to
231   * the iteration ordering of the {@code multimap.asMap()} view.
232   *
233   * <p>Despite the method name, this method attempts to avoid actually copying
234   * the data when it is safe to do so. The exact circumstances under which a
235   * copy will or will not be performed are undocumented and subject to change.
236   *
237   * @throws NullPointerException if any key or value in {@code multimap} is
238   *         null
239   */
240  public static <K, V> ImmutableListMultimap<K, V> copyOf(
241      Multimap<? extends K, ? extends V> multimap) {
242    if (multimap.isEmpty()) {
243      return of();
244    }
245
246    // TODO(user): copy ImmutableSetMultimap by using asList() on the sets
247    if (multimap instanceof ImmutableListMultimap) {
248      @SuppressWarnings("unchecked") // safe since multimap is not writable
249      ImmutableListMultimap<K, V> kvMultimap
250          = (ImmutableListMultimap<K, V>) multimap;
251      if (!kvMultimap.isPartialView()) {
252        return kvMultimap;
253      }
254    }
255
256    ImmutableMap.Builder<K, ImmutableList<V>> builder = ImmutableMap.builder();
257    int size = 0;
258
259    for (Entry<? extends K, ? extends Collection<? extends V>> entry
260        : multimap.asMap().entrySet()) {
261      ImmutableList<V> list = ImmutableList.copyOf(entry.getValue());
262      if (!list.isEmpty()) {
263        builder.put(entry.getKey(), list);
264        size += list.size();
265      }
266    }
267
268    return new ImmutableListMultimap<K, V>(builder.build(), size);
269  }
270
271  ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) {
272    super(map, size);
273  }
274
275  // views
276
277  /**
278   * Returns an immutable list of the values for the given key.  If no mappings
279   * in the multimap have the provided key, an empty immutable list is
280   * returned. The values are in the same order as the parameters used to build
281   * this multimap.
282   */
283  @Override public ImmutableList<V> get(@Nullable K key) {
284    // This cast is safe as its type is known in constructor.
285    ImmutableList<V> list = (ImmutableList<V>) map.get(key);
286    return (list == null) ? ImmutableList.<V>of() : list;
287  }
288
289  private transient ImmutableListMultimap<V, K> inverse;
290
291  /**
292   * {@inheritDoc}
293   *
294   * <p>Because an inverse of a list multimap can contain multiple pairs with
295   * the same key and value, this method returns an {@code
296   * ImmutableListMultimap} rather than the {@code ImmutableMultimap} specified
297   * in the {@code ImmutableMultimap} class.
298   *
299   * @since 11.0
300   */
301  @Override
302  public ImmutableListMultimap<V, K> inverse() {
303    ImmutableListMultimap<V, K> result = inverse;
304    return (result == null) ? (inverse = invert()) : result;
305  }
306
307  private ImmutableListMultimap<V, K> invert() {
308    Builder<V, K> builder = builder();
309    for (Entry<K, V> entry : entries()) {
310      builder.put(entry.getValue(), entry.getKey());
311    }
312    ImmutableListMultimap<V, K> invertedMultimap = builder.build();
313    invertedMultimap.inverse = this;
314    return invertedMultimap;
315  }
316
317  /**
318   * Guaranteed to throw an exception and leave the multimap unmodified.
319   *
320   * @throws UnsupportedOperationException always
321   * @deprecated Unsupported operation.
322   */
323  @Deprecated @Override public ImmutableList<V> removeAll(Object key) {
324    throw new UnsupportedOperationException();
325  }
326
327  /**
328   * Guaranteed to throw an exception and leave the multimap unmodified.
329   *
330   * @throws UnsupportedOperationException always
331   * @deprecated Unsupported operation.
332   */
333  @Deprecated @Override public ImmutableList<V> replaceValues(
334      K key, Iterable<? extends V> values) {
335    throw new UnsupportedOperationException();
336  }
337
338  /**
339   * @serialData number of distinct keys, and then for each distinct key: the
340   *     key, the number of values for that key, and the key's values
341   */
342  @GwtIncompatible("java.io.ObjectOutputStream")
343  private void writeObject(ObjectOutputStream stream) throws IOException {
344    stream.defaultWriteObject();
345    Serialization.writeMultimap(this, stream);
346  }
347
348  @GwtIncompatible("java.io.ObjectInputStream")
349  private void readObject(ObjectInputStream stream)
350      throws IOException, ClassNotFoundException {
351    stream.defaultReadObject();
352    int keyCount = stream.readInt();
353    if (keyCount < 0) {
354      throw new InvalidObjectException("Invalid key count " + keyCount);
355    }
356    ImmutableMap.Builder<Object, ImmutableList<Object>> builder
357        = ImmutableMap.builder();
358    int tmpSize = 0;
359
360    for (int i = 0; i < keyCount; i++) {
361      Object key = stream.readObject();
362      int valueCount = stream.readInt();
363      if (valueCount <= 0) {
364        throw new InvalidObjectException("Invalid value count " + valueCount);
365      }
366
367      Object[] array = new Object[valueCount];
368      for (int j = 0; j < valueCount; j++) {
369        array[j] = stream.readObject();
370      }
371      builder.put(key, ImmutableList.copyOf(array));
372      tmpSize += valueCount;
373    }
374
375    ImmutableMap<Object, ImmutableList<Object>> tmpMap;
376    try {
377      tmpMap = builder.build();
378    } catch (IllegalArgumentException e) {
379      throw (InvalidObjectException)
380          new InvalidObjectException(e.getMessage()).initCause(e);
381    }
382
383    FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
384    FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
385  }
386
387  @GwtIncompatible("Not needed in emulated source")
388  private static final long serialVersionUID = 0;
389}
390