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