001    /*
002     * Copyright (C) 2009 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 static com.google.common.base.Preconditions.checkNotNull;
020    
021    import com.google.common.annotations.Beta;
022    import com.google.common.annotations.GwtCompatible;
023    import com.google.common.annotations.GwtIncompatible;
024    
025    import java.io.IOException;
026    import java.io.InvalidObjectException;
027    import java.io.ObjectInputStream;
028    import java.io.ObjectOutputStream;
029    import java.util.Arrays;
030    import java.util.Collection;
031    import java.util.Comparator;
032    import java.util.LinkedHashMap;
033    import java.util.Map;
034    import java.util.TreeMap;
035    
036    import javax.annotation.Nullable;
037    
038    /**
039     * An immutable {@link SetMultimap} with reliable user-specified key and value
040     * iteration order. Does not permit null keys or values.
041     *
042     * <p>Unlike {@link Multimaps#unmodifiableSetMultimap(SetMultimap)}, which is
043     * a <i>view</i> of a separate multimap which can still change, an instance of
044     * {@code ImmutableSetMultimap} contains its own data and will <i>never</i>
045     * change. {@code ImmutableSetMultimap} is convenient for
046     * {@code public static final} multimaps ("constant multimaps") and also lets
047     * you easily make a "defensive copy" of a multimap provided to your class by
048     * a caller.
049     *
050     * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
051     * it has no public or protected constructors. Thus, instances of this class
052     * are guaranteed to be immutable.
053     *
054     * @author Mike Ward
055     * @since 2 (imported from Google Collections Library)
056     */
057    @GwtCompatible(serializable = true, emulated = true)
058    public class ImmutableSetMultimap<K, V>
059        extends ImmutableMultimap<K, V>
060        implements SetMultimap<K, V> {
061    
062      /** Returns the empty multimap. */
063      // Casting is safe because the multimap will never hold any elements.
064      @SuppressWarnings("unchecked")
065      public static <K, V> ImmutableSetMultimap<K, V> of() {
066        return (ImmutableSetMultimap<K, V>) EmptyImmutableSetMultimap.INSTANCE;
067      }
068    
069      /**
070       * Returns an immutable multimap containing a single entry.
071       */
072      public static <K, V> ImmutableSetMultimap<K, V> of(K k1, V v1) {
073        ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.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       * Repeated occurrences of an entry (according to {@link Object#equals}) after
081       * the first are ignored.
082       */
083      public static <K, V> ImmutableSetMultimap<K, V> of(K k1, V v1, K k2, V v2) {
084        ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
085        builder.put(k1, v1);
086        builder.put(k2, v2);
087        return builder.build();
088      }
089    
090      /**
091       * Returns an immutable multimap containing the given entries, in order.
092       * Repeated occurrences of an entry (according to {@link Object#equals}) after
093       * the first are ignored.
094       */
095      public static <K, V> ImmutableSetMultimap<K, V> of(
096          K k1, V v1, K k2, V v2, K k3, V v3) {
097        ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
098        builder.put(k1, v1);
099        builder.put(k2, v2);
100        builder.put(k3, v3);
101        return builder.build();
102      }
103    
104      /**
105       * Returns an immutable multimap containing the given entries, in order.
106       * Repeated occurrences of an entry (according to {@link Object#equals}) after
107       * the first are ignored.
108       */
109      public static <K, V> ImmutableSetMultimap<K, V> of(
110          K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
111        ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
112        builder.put(k1, v1);
113        builder.put(k2, v2);
114        builder.put(k3, v3);
115        builder.put(k4, v4);
116        return builder.build();
117      }
118    
119      /**
120       * Returns an immutable multimap containing the given entries, in order.
121       * Repeated occurrences of an entry (according to {@link Object#equals}) after
122       * the first are ignored.
123       */
124      public static <K, V> ImmutableSetMultimap<K, V> of(
125          K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
126        ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
127        builder.put(k1, v1);
128        builder.put(k2, v2);
129        builder.put(k3, v3);
130        builder.put(k4, v4);
131        builder.put(k5, v5);
132        return builder.build();
133      }
134    
135      // looking for of() with > 5 entries? Use the builder instead.
136    
137      /**
138       * Returns a new {@link Builder}.
139       */
140      public static <K, V> Builder<K, V> builder() {
141        return new Builder<K, V>();
142      }
143    
144      /**
145       * Multimap for {@link ImmutableSetMultimap.Builder} that maintains key
146       * and value orderings and performs better than {@link LinkedHashMultimap}.
147       */
148      private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> {
149        BuilderMultimap() {
150          super(new LinkedHashMap<K, Collection<V>>());
151        }
152        @Override Collection<V> createCollection() {
153          return Sets.newLinkedHashSet();
154        }
155        private static final long serialVersionUID = 0;
156      }
157    
158      /**
159       * Multimap for {@link ImmutableSetMultimap.Builder} that sorts keys and
160       * maintains value orderings.
161       */
162      private static class SortedKeyBuilderMultimap<K, V> 
163          extends AbstractMultimap<K, V> {
164        SortedKeyBuilderMultimap(
165            Comparator<? super K> keyComparator, Multimap<K, V> multimap) {
166          super(new TreeMap<K, Collection<V>>(keyComparator));
167          putAll(multimap);
168        }
169        @Override Collection<V> createCollection() {
170          return Sets.newLinkedHashSet();
171        }
172        private static final long serialVersionUID = 0;
173      }
174      
175      /**
176       * A builder for creating immutable {@code SetMultimap} instances, especially
177       * {@code public static final} multimaps ("constant multimaps"). Example:
178       * <pre>   {@code
179       *
180       *   static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
181       *       new ImmutableSetMultimap.Builder<String, Integer>()
182       *           .put("one", 1)
183       *           .putAll("several", 1, 2, 3)
184       *           .putAll("many", 1, 2, 3, 4, 5)
185       *           .build();}</pre>
186       *
187       * Builder instances can be reused; it is safe to call {@link #build} multiple
188       * times to build multiple multimaps in series. Each multimap contains the
189       * key-value mappings in the previously created multimaps.
190       *
191       * @since 2 (imported from Google Collections Library)
192       */
193      public static final class Builder<K, V>
194          extends ImmutableMultimap.Builder<K, V> {
195        /**
196         * Creates a new builder. The returned builder is equivalent to the builder
197         * generated by {@link ImmutableSetMultimap#builder}.
198         */
199        public Builder() {
200          builderMultimap = new BuilderMultimap<K, V>();      
201        }
202    
203        /**
204         * Adds a key-value mapping to the built multimap if it is not already
205         * present.
206         */
207        @Override public Builder<K, V> put(K key, V value) {
208          builderMultimap.put(checkNotNull(key), checkNotNull(value));
209          return this;
210        }
211    
212        @Override public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
213          Collection<V> collection = builderMultimap.get(checkNotNull(key));
214          for (V value : values) {
215            collection.add(checkNotNull(value));
216          }
217          return this;
218        }
219    
220        @Override public Builder<K, V> putAll(K key, V... values) {
221          return putAll(key, Arrays.asList(values));
222        }
223    
224        @Override public Builder<K, V> putAll(
225            Multimap<? extends K, ? extends V> multimap) {
226          for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry
227              : multimap.asMap().entrySet()) {
228            putAll(entry.getKey(), entry.getValue());
229          }
230          return this;
231        }
232    
233        /**
234         * {@inheritDoc}
235         *
236         * @since 8
237         */
238        @Beta @Override
239        public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
240          builderMultimap = new SortedKeyBuilderMultimap<K, V>(
241              checkNotNull(keyComparator), builderMultimap);
242          return this;
243        }
244    
245        /**
246         * Specifies the ordering of the generated multimap's values for each key.
247         * 
248         * <p>If this method is called, the sets returned by the {@code get()} 
249         * method of the generated multimap and its {@link Multimap#asMap()} view
250         * are {@link ImmutableSortedSet} instances. However, serialization does not
251         * preserve that property, though it does maintain the key and value
252         * ordering.
253         * 
254         * @since 8
255         */
256        // TODO: Make serialization behavior consistent.
257        @Beta @Override
258        public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
259          super.orderValuesBy(valueComparator);
260          return this;
261        }
262    
263        /**
264         * Returns a newly-created immutable set multimap.
265         */
266        @Override public ImmutableSetMultimap<K, V> build() {
267          return copyOf(builderMultimap, valueComparator);
268        }
269      }
270    
271      /**
272       * Returns an immutable set multimap containing the same mappings as
273       * {@code multimap}. The generated multimap's key and value orderings
274       * correspond to the iteration ordering of the {@code multimap.asMap()} view.
275       * Repeated occurrences of an entry in the multimap after the first are
276       * ignored.
277       *
278       * <p>Despite the method name, this method attempts to avoid actually copying
279       * the data when it is safe to do so. The exact circumstances under which a
280       * copy will or will not be performed are undocumented and subject to change.
281       *
282       * @throws NullPointerException if any key or value in {@code multimap} is
283       *     null
284       */
285      public static <K, V> ImmutableSetMultimap<K, V> copyOf(
286          Multimap<? extends K, ? extends V> multimap) {
287        return copyOf(multimap, null);
288      }
289      
290      private static <K, V> ImmutableSetMultimap<K, V> copyOf(
291          Multimap<? extends K, ? extends V> multimap,
292          Comparator<? super V> valueComparator) {
293        checkNotNull(multimap); // eager for GWT
294        if (multimap.isEmpty() && valueComparator == null) {
295          return of();
296        }
297    
298        if (multimap instanceof ImmutableSetMultimap) {
299          @SuppressWarnings("unchecked") // safe since multimap is not writable
300          ImmutableSetMultimap<K, V> kvMultimap
301              = (ImmutableSetMultimap<K, V>) multimap;
302          if (!kvMultimap.isPartialView()) {
303            return kvMultimap;
304          }
305        }
306    
307        ImmutableMap.Builder<K, ImmutableSet<V>> builder = ImmutableMap.builder();
308        int size = 0;
309    
310        for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry
311            : multimap.asMap().entrySet()) {
312          K key = entry.getKey();
313          Collection<? extends V> values = entry.getValue();
314          ImmutableSet<V> set = (valueComparator == null)
315              ? ImmutableSet.copyOf(values) 
316              : ImmutableSortedSet.copyOf(valueComparator, values);
317          if (!set.isEmpty()) {
318            builder.put(key, set);
319            size += set.size();
320          }
321        }
322    
323        return new ImmutableSetMultimap<K, V>(
324            builder.build(), size, valueComparator);
325      }
326    
327      // Returned by get() when values are sorted and a missing key is provided.
328      private final transient ImmutableSortedSet<V> emptySet;
329    
330      ImmutableSetMultimap(ImmutableMap<K, ImmutableSet<V>> map, int size, 
331          @Nullable Comparator<? super V> valueComparator) {
332        super(map, size);
333        this.emptySet = (valueComparator == null) 
334            ? null : ImmutableSortedSet.<V>emptySet(valueComparator);
335      }
336    
337      // views
338    
339      /**
340       * Returns an immutable set of the values for the given key.  If no mappings
341       * in the multimap have the provided key, an empty immutable set is returned.
342       * The values are in the same order as the parameters used to build this
343       * multimap.
344       */
345      @Override public ImmutableSet<V> get(@Nullable K key) {
346         // This cast is safe as its type is known in constructor.
347        ImmutableSet<V> set = (ImmutableSet<V>) map.get(key);
348        if (set != null) {
349          return set;
350        } else if (emptySet != null) {
351          return emptySet;
352        } else {
353          return ImmutableSet.<V>of();
354        }
355      }
356    
357      /**
358       * Guaranteed to throw an exception and leave the multimap unmodified.
359       *
360       * @throws UnsupportedOperationException always
361       */
362      @Override public ImmutableSet<V> removeAll(Object key) {
363        throw new UnsupportedOperationException();
364      }
365    
366      /**
367       * Guaranteed to throw an exception and leave the multimap unmodified.
368       *
369       * @throws UnsupportedOperationException always
370       */
371      @Override public ImmutableSet<V> replaceValues(
372          K key, Iterable<? extends V> values) {
373        throw new UnsupportedOperationException();
374      }
375    
376      private transient ImmutableSet<Map.Entry<K, V>> entries;
377    
378      /**
379       * Returns an immutable collection of all key-value pairs in the multimap.
380       * Its iterator traverses the values for the first key, the values for the
381       * second key, and so on.
382       */
383      // TODO(kevinb): Fix this so that two copies of the entries are not created.
384      @Override public ImmutableSet<Map.Entry<K, V>> entries() {
385        ImmutableSet<Map.Entry<K, V>> result = entries;
386        return (result == null)
387            ? (entries = ImmutableSet.copyOf(super.entries()))
388            : result;
389      }
390    
391      /**
392       * @serialData number of distinct keys, and then for each distinct key: the
393       *     key, the number of values for that key, and the key's values
394       */
395      @GwtIncompatible("java.io.ObjectOutputStream")
396      private void writeObject(ObjectOutputStream stream) throws IOException {
397        stream.defaultWriteObject();
398        Serialization.writeMultimap(this, stream);
399      }
400    
401      @GwtIncompatible("java.io.ObjectInputStream")
402      private void readObject(ObjectInputStream stream)
403          throws IOException, ClassNotFoundException {
404        stream.defaultReadObject();
405        int keyCount = stream.readInt();
406        if (keyCount < 0) {
407          throw new InvalidObjectException("Invalid key count " + keyCount);
408        }
409        ImmutableMap.Builder<Object, ImmutableSet<Object>> builder
410            = ImmutableMap.builder();
411        int tmpSize = 0;
412    
413        for (int i = 0; i < keyCount; i++) {
414          Object key = stream.readObject();
415          int valueCount = stream.readInt();
416          if (valueCount <= 0) {
417            throw new InvalidObjectException("Invalid value count " + valueCount);
418          }
419    
420          Object[] array = new Object[valueCount];
421          for (int j = 0; j < valueCount; j++) {
422            array[j] = stream.readObject();
423          }
424          ImmutableSet<Object> valueSet = ImmutableSet.copyOf(array);
425          if (valueSet.size() != array.length) {
426            throw new InvalidObjectException(
427                "Duplicate key-value pairs exist for key " + key);
428          }
429          builder.put(key, valueSet);
430          tmpSize += valueCount;
431        }
432    
433        ImmutableMap<Object, ImmutableSet<Object>> tmpMap;
434        try {
435          tmpMap = builder.build();
436        } catch (IllegalArgumentException e) {
437          throw (InvalidObjectException)
438              new InvalidObjectException(e.getMessage()).initCause(e);
439        }
440    
441        FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
442        FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
443      }
444    
445      @GwtIncompatible("not needed in emulated source.")
446      private static final long serialVersionUID = 0;
447    }