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    
017    package com.google.common.collect;
018    
019    import com.google.common.annotations.Beta;
020    import com.google.common.annotations.GwtCompatible;
021    import com.google.common.annotations.GwtIncompatible;
022    
023    import java.io.IOException;
024    import java.io.InvalidObjectException;
025    import java.io.ObjectInputStream;
026    import java.io.ObjectOutputStream;
027    import java.util.Collection;
028    import java.util.Comparator;
029    import java.util.Map.Entry;
030    
031    import 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)
057    public 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    }