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.Beta;
020import com.google.common.annotations.GwtCompatible;
021import com.google.common.annotations.GwtIncompatible;
022
023import java.io.IOException;
024import java.io.InvalidObjectException;
025import java.io.ObjectInputStream;
026import java.io.ObjectOutputStream;
027import java.util.Collection;
028import java.util.Comparator;
029import java.util.Map.Entry;
030
031import javax.annotation.Nullable;
032
033/**
034 * An immutable {@link ListMultimap} with reliable user-specified key and value
035 * iteration order. Does not permit null keys or values.
036 *
037 * <p>Unlike {@link Multimaps#unmodifiableListMultimap(ListMultimap)}, which is
038 * a <i>view</i> of a separate multimap which can still change, an instance of
039 * {@code ImmutableListMultimap} contains its own data and will <i>never</i>
040 * change. {@code ImmutableListMultimap} is convenient for
041 * {@code public static final} multimaps ("constant multimaps") and also lets
042 * you easily make a "defensive copy" of a multimap provided to your class by
043 * a caller.
044 *
045 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
046 * it has no public or protected constructors. Thus, instances of this class
047 * are guaranteed to be immutable.
048 *
049 * <p>See the Guava User Guide article on <a href=
050 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
051 * immutable collections</a>.
052 *
053 * @author Jared Levy
054 * @since 2.0 (imported from Google Collections Library)
055 */
056@GwtCompatible(serializable = true, emulated = true)
057public class ImmutableListMultimap<K, V>
058    extends ImmutableMultimap<K, V>
059    implements ListMultimap<K, V> {
060
061  /** Returns the empty multimap. */
062  // Casting is safe because the multimap will never hold any elements.
063  @SuppressWarnings("unchecked")
064  public static <K, V> ImmutableListMultimap<K, V> of() {
065    return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE;
066  }
067
068  /**
069   * Returns an immutable multimap containing a single entry.
070   */
071  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) {
072    ImmutableListMultimap.Builder<K, V> builder
073        = ImmutableListMultimap.builder();
074    builder.put(k1, v1);
075    return builder.build();
076  }
077
078  /**
079   * Returns an immutable multimap containing the given entries, in order.
080   */
081  public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) {
082    ImmutableListMultimap.Builder<K, V> builder
083        = ImmutableListMultimap.builder();
084    builder.put(k1, v1);
085    builder.put(k2, v2);
086    return builder.build();
087  }
088
089  /**
090   * Returns an immutable multimap containing the given entries, in order.
091   */
092  public static <K, V> ImmutableListMultimap<K, V> of(
093      K k1, V v1, K k2, V v2, K k3, V v3) {
094    ImmutableListMultimap.Builder<K, V> builder
095        = ImmutableListMultimap.builder();
096    builder.put(k1, v1);
097    builder.put(k2, v2);
098    builder.put(k3, v3);
099    return builder.build();
100  }
101
102  /**
103   * Returns an immutable multimap containing the given entries, in order.
104   */
105  public static <K, V> ImmutableListMultimap<K, V> of(
106      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
107    ImmutableListMultimap.Builder<K, V> builder
108        = ImmutableListMultimap.builder();
109    builder.put(k1, v1);
110    builder.put(k2, v2);
111    builder.put(k3, v3);
112    builder.put(k4, v4);
113    return builder.build();
114  }
115
116  /**
117   * Returns an immutable multimap containing the given entries, in order.
118   */
119  public static <K, V> ImmutableListMultimap<K, V> of(
120      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
121    ImmutableListMultimap.Builder<K, V> builder
122        = ImmutableListMultimap.builder();
123    builder.put(k1, v1);
124    builder.put(k2, v2);
125    builder.put(k3, v3);
126    builder.put(k4, v4);
127    builder.put(k5, v5);
128    return builder.build();
129  }
130
131  // looking for of() with > 5 entries? Use the builder instead.
132
133  /**
134   * Returns a new builder. The generated builder is equivalent to the builder
135   * created by the {@link Builder} constructor.
136   */
137  public static <K, V> Builder<K, V> builder() {
138    return new Builder<K, V>();
139  }
140
141  /**
142   * A builder for creating immutable {@code ListMultimap} instances, especially
143   * {@code public static final} multimaps ("constant multimaps"). Example:
144   * <pre>   {@code
145   *
146   *   static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
147   *       new ImmutableListMultimap.Builder<String, Integer>()
148   *           .put("one", 1)
149   *           .putAll("several", 1, 2, 3)
150   *           .putAll("many", 1, 2, 3, 4, 5)
151   *           .build();}</pre>
152   *
153   * Builder instances can be reused; it is safe to call {@link #build} multiple
154   * times to build multiple multimaps in series. Each multimap contains the
155   * key-value mappings in the previously created multimaps.
156   *
157   * @since 2.0 (imported from Google Collections Library)
158   */
159  public static final class Builder<K, V>
160      extends ImmutableMultimap.Builder<K, V> {
161    /**
162     * Creates a new builder. The returned builder is equivalent to the builder
163     * generated by {@link ImmutableListMultimap#builder}.
164     */
165    public Builder() {}
166
167    @Override public Builder<K, V> put(K key, V value) {
168      super.put(key, value);
169      return this;
170    }
171
172    /**
173     * {@inheritDoc}
174     *
175     * @since 11.0
176     */
177    @Override public Builder<K, V> put(
178        Entry<? extends K, ? extends V> entry) {
179      super.put(entry);
180      return this;
181    }
182
183    @Override public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
184      super.putAll(key, values);
185      return this;
186    }
187
188    @Override public Builder<K, V> putAll(K key, V... values) {
189      super.putAll(key, values);
190      return this;
191    }
192
193    @Override public Builder<K, V> putAll(
194        Multimap<? extends K, ? extends V> multimap) {
195      super.putAll(multimap);
196      return this;
197    }
198
199    /**
200     * {@inheritDoc}
201     *
202     * @since 8.0
203     */
204    @Beta @Override
205    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
206      super.orderKeysBy(keyComparator);
207      return this;
208    }
209
210    /**
211     * {@inheritDoc}
212     *
213     * @since 8.0
214     */
215    @Beta @Override
216    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
217      super.orderValuesBy(valueComparator);
218      return this;
219    }
220
221    /**
222     * Returns a newly-created immutable list multimap.
223     */
224    @Override public ImmutableListMultimap<K, V> build() {
225      return (ImmutableListMultimap<K, V>) super.build();
226    }
227  }
228
229  /**
230   * Returns an immutable multimap containing the same mappings as {@code
231   * multimap}. The generated multimap's key and value orderings correspond to
232   * the iteration ordering of the {@code multimap.asMap()} view.
233   *
234   * <p>Despite the method name, this method attempts to avoid actually copying
235   * the data when it is safe to do so. The exact circumstances under which a
236   * copy will or will not be performed are undocumented and subject to change.
237   *
238   * @throws NullPointerException if any key or value in {@code multimap} is
239   *         null
240   */
241  public static <K, V> ImmutableListMultimap<K, V> copyOf(
242      Multimap<? extends K, ? extends V> multimap) {
243    if (multimap.isEmpty()) {
244      return of();
245    }
246
247    // TODO(user): copy ImmutableSetMultimap by using asList() on the sets
248    if (multimap instanceof ImmutableListMultimap) {
249      @SuppressWarnings("unchecked") // safe since multimap is not writable
250      ImmutableListMultimap<K, V> kvMultimap
251          = (ImmutableListMultimap<K, V>) multimap;
252      if (!kvMultimap.isPartialView()) {
253        return kvMultimap;
254      }
255    }
256
257    ImmutableMap.Builder<K, ImmutableList<V>> builder = ImmutableMap.builder();
258    int size = 0;
259
260    for (Entry<? extends K, ? extends Collection<? extends V>> entry
261        : multimap.asMap().entrySet()) {
262      ImmutableList<V> list = ImmutableList.copyOf(entry.getValue());
263      if (!list.isEmpty()) {
264        builder.put(entry.getKey(), list);
265        size += list.size();
266      }
267    }
268
269    return new ImmutableListMultimap<K, V>(builder.build(), size);
270  }
271
272  ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) {
273    super(map, size);
274  }
275
276  // views
277
278  /**
279   * Returns an immutable list of the values for the given key.  If no mappings
280   * in the multimap have the provided key, an empty immutable list is
281   * returned. The values are in the same order as the parameters used to build
282   * this multimap.
283   */
284  @Override public ImmutableList<V> get(@Nullable K key) {
285    // This cast is safe as its type is known in constructor.
286    ImmutableList<V> list = (ImmutableList<V>) map.get(key);
287    return (list == null) ? ImmutableList.<V>of() : list;
288  }
289
290  private transient ImmutableListMultimap<V, K> inverse;
291
292  /**
293   * {@inheritDoc}
294   *
295   * <p>Because an inverse of a list multimap can contain multiple pairs with
296   * the same key and value, this method returns an {@code
297   * ImmutableListMultimap} rather than the {@code ImmutableMultimap} specified
298   * in the {@code ImmutableMultimap} class.
299   *
300   * @since 11
301   */
302  @Beta
303  public ImmutableListMultimap<V, K> inverse() {
304    ImmutableListMultimap<V, K> result = inverse;
305    return (result == null) ? (inverse = invert()) : result;
306  }
307
308  private ImmutableListMultimap<V, K> invert() {
309    Builder<V, K> builder = builder();
310    for (Entry<K, V> entry : entries()) {
311      builder.put(entry.getValue(), entry.getKey());
312    }
313    ImmutableListMultimap<V, K> invertedMultimap = builder.build();
314    invertedMultimap.inverse = this;
315    return invertedMultimap;
316  }
317
318  /**
319   * Guaranteed to throw an exception and leave the multimap unmodified.
320   *
321   * @throws UnsupportedOperationException always
322   */
323  @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   */
332  @Override public ImmutableList<V> replaceValues(
333      K key, Iterable<? extends V> values) {
334    throw new UnsupportedOperationException();
335  }
336
337  /**
338   * @serialData number of distinct keys, and then for each distinct key: the
339   *     key, the number of values for that key, and the key's values
340   */
341  @GwtIncompatible("java.io.ObjectOutputStream")
342  private void writeObject(ObjectOutputStream stream) throws IOException {
343    stream.defaultWriteObject();
344    Serialization.writeMultimap(this, stream);
345  }
346
347  @GwtIncompatible("java.io.ObjectInputStream")
348  private void readObject(ObjectInputStream stream)
349      throws IOException, ClassNotFoundException {
350    stream.defaultReadObject();
351    int keyCount = stream.readInt();
352    if (keyCount < 0) {
353      throw new InvalidObjectException("Invalid key count " + keyCount);
354    }
355    ImmutableMap.Builder<Object, ImmutableList<Object>> builder
356        = ImmutableMap.builder();
357    int tmpSize = 0;
358
359    for (int i = 0; i < keyCount; i++) {
360      Object key = stream.readObject();
361      int valueCount = stream.readInt();
362      if (valueCount <= 0) {
363        throw new InvalidObjectException("Invalid value count " + valueCount);
364      }
365
366      Object[] array = new Object[valueCount];
367      for (int j = 0; j < valueCount; j++) {
368        array[j] = stream.readObject();
369      }
370      builder.put(key, ImmutableList.copyOf(array));
371      tmpSize += valueCount;
372    }
373
374    ImmutableMap<Object, ImmutableList<Object>> tmpMap;
375    try {
376      tmpMap = builder.build();
377    } catch (IllegalArgumentException e) {
378      throw (InvalidObjectException)
379          new InvalidObjectException(e.getMessage()).initCause(e);
380    }
381
382    FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
383    FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
384  }
385
386  @GwtIncompatible("Not needed in emulated source")
387  private static final long serialVersionUID = 0;
388}