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