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