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 static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
021
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.annotations.GwtIncompatible;
024
025import java.io.Serializable;
026import java.util.Arrays;
027import java.util.Collection;
028import java.util.Collections;
029import java.util.Comparator;
030import java.util.Iterator;
031import java.util.LinkedHashMap;
032import java.util.List;
033import java.util.Map;
034import java.util.Map.Entry;
035import java.util.Set;
036
037import javax.annotation.Nullable;
038
039/**
040 * An immutable {@link Multimap}. Does not permit null keys or values.
041 *
042 * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is
043 * a <i>view</i> of a separate multimap which can still change, an instance of
044 * {@code ImmutableMultimap} contains its own data and will <i>never</i>
045 * change. {@code ImmutableMultimap} 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 * <p>In addition to methods defined by {@link Multimap}, an {@link #inverse}
055 * method is also supported.
056 *
057 * <p>See the Guava User Guide article on <a href=
058 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
059 * immutable collections</a>.
060 *
061 * @author Jared Levy
062 * @since 2.0 (imported from Google Collections Library)
063 */
064@GwtCompatible(emulated = true)
065public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V>
066    implements Serializable {
067
068  /** Returns an empty multimap. */
069  public static <K, V> ImmutableMultimap<K, V> of() {
070    return ImmutableListMultimap.of();
071  }
072
073  /**
074   * Returns an immutable multimap containing a single entry.
075   */
076  public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) {
077    return ImmutableListMultimap.of(k1, v1);
078  }
079
080  /**
081   * Returns an immutable multimap containing the given entries, in order.
082   */
083  public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) {
084    return ImmutableListMultimap.of(k1, v1, k2, v2);
085  }
086
087  /**
088   * Returns an immutable multimap containing the given entries, in order.
089   */
090  public static <K, V> ImmutableMultimap<K, V> of(
091      K k1, V v1, K k2, V v2, K k3, V v3) {
092    return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3);
093  }
094
095  /**
096   * Returns an immutable multimap containing the given entries, in order.
097   */
098  public static <K, V> ImmutableMultimap<K, V> of(
099      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
100    return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4);
101  }
102
103  /**
104   * Returns an immutable multimap containing the given entries, in order.
105   */
106  public static <K, V> ImmutableMultimap<K, V> of(
107      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
108    return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
109  }
110
111  // looking for of() with > 5 entries? Use the builder instead.
112
113  /**
114   * Returns a new builder. The generated builder is equivalent to the builder
115   * created by the {@link Builder} constructor.
116   */
117  public static <K, V> Builder<K, V> builder() {
118    return new Builder<K, V>();
119  }
120
121  /**
122   * Multimap for {@link ImmutableMultimap.Builder} that maintains key and
123   * value orderings, allows duplicate values, and performs better than
124   * {@link LinkedListMultimap}.
125   */
126  private static class BuilderMultimap<K, V> extends AbstractMapBasedMultimap<K, V> {
127    BuilderMultimap() {
128      super(new LinkedHashMap<K, Collection<V>>());
129    }
130    @Override Collection<V> createCollection() {
131      return Lists.newArrayList();
132    }
133    private static final long serialVersionUID = 0;
134  }
135
136  /**
137   * A builder for creating immutable multimap instances, especially
138   * {@code public static final} multimaps ("constant multimaps"). Example:
139   * <pre>   {@code
140   *
141   *   static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
142   *       new ImmutableMultimap.Builder<String, Integer>()
143   *           .put("one", 1)
144   *           .putAll("several", 1, 2, 3)
145   *           .putAll("many", 1, 2, 3, 4, 5)
146   *           .build();}</pre>
147   *
148   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
149   * times to build multiple multimaps in series. Each multimap contains the
150   * key-value mappings in the previously created multimaps.
151   *
152   * @since 2.0 (imported from Google Collections Library)
153   */
154  public static class Builder<K, V> {
155    Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>();
156    Comparator<? super K> keyComparator;
157    Comparator<? super V> valueComparator;
158
159    /**
160     * Creates a new builder. The returned builder is equivalent to the builder
161     * generated by {@link ImmutableMultimap#builder}.
162     */
163    public Builder() {}
164
165    /**
166     * Adds a key-value mapping to the built multimap.
167     */
168    public Builder<K, V> put(K key, V value) {
169      checkEntryNotNull(key, value);
170      builderMultimap.put(key, value);
171      return this;
172    }
173
174    /**
175     * Adds an entry to the built multimap.
176     *
177     * @since 11.0
178     */
179    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
180      return put(entry.getKey(), entry.getValue());
181    }
182
183    /**
184     * Stores a collection of values with the same key in the built multimap.
185     *
186     * @throws NullPointerException if {@code key}, {@code values}, or any
187     *     element in {@code values} is null. The builder is left in an invalid
188     *     state.
189     */
190    public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
191      if (key == null) {
192        throw new NullPointerException(
193            "null key in entry: null=" + Iterables.toString(values));
194      }
195      Collection<V> valueList = builderMultimap.get(key);
196      for (V value : values) {
197        checkEntryNotNull(key, value);
198        valueList.add(value);
199      }
200      return this;
201    }
202
203    /**
204     * Stores an array of values with the same key in the built multimap.
205     *
206     * @throws NullPointerException if the key or any value is null. The builder
207     *     is left in an invalid state.
208     */
209    public Builder<K, V> putAll(K key, V... values) {
210      return putAll(key, Arrays.asList(values));
211    }
212
213    /**
214     * Stores another multimap's entries in the built multimap. The generated
215     * multimap's key and value orderings correspond to the iteration ordering
216     * of the {@code multimap.asMap()} view, with new keys and values following
217     * any existing keys and values.
218     *
219     * @throws NullPointerException if any key or value in {@code multimap} is
220     *     null. The builder is left in an invalid state.
221     */
222    public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
223      for (Entry<? extends K, ? extends Collection<? extends V>> entry
224          : multimap.asMap().entrySet()) {
225        putAll(entry.getKey(), entry.getValue());
226      }
227      return this;
228    }
229
230    /**
231     * Specifies the ordering of the generated multimap's keys.
232     *
233     * @since 8.0
234     */
235    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
236      this.keyComparator = checkNotNull(keyComparator);
237      return this;
238    }
239
240    /**
241     * Specifies the ordering of the generated multimap's values for each key.
242     *
243     * @since 8.0
244     */
245    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
246      this.valueComparator = checkNotNull(valueComparator);
247      return this;
248    }
249
250    /**
251     * Returns a newly-created immutable multimap.
252     */
253    public ImmutableMultimap<K, V> build() {
254      if (valueComparator != null) {
255        for (Collection<V> values : builderMultimap.asMap().values()) {
256          List<V> list = (List <V>) values;
257          Collections.sort(list, valueComparator);
258        }
259      }
260      if (keyComparator != null) {
261        Multimap<K, V> sortedCopy = new BuilderMultimap<K, V>();
262        List<Map.Entry<K, Collection<V>>> entries = Lists.newArrayList(
263            builderMultimap.asMap().entrySet());
264        Collections.sort(
265            entries,
266            Ordering.from(keyComparator).<K>onKeys());
267        for (Map.Entry<K, Collection<V>> entry : entries) {
268          sortedCopy.putAll(entry.getKey(), entry.getValue());
269        }
270        builderMultimap = sortedCopy;
271      }
272      return copyOf(builderMultimap);
273    }
274  }
275
276  /**
277   * Returns an immutable multimap containing the same mappings as {@code
278   * multimap}. The generated multimap's key and value orderings correspond to
279   * the iteration ordering of the {@code multimap.asMap()} view.
280   *
281   * <p>Despite the method name, this method attempts to avoid actually copying
282   * the data when it is safe to do so. The exact circumstances under which a
283   * copy will or will not be performed are undocumented and subject to change.
284   *
285   * @throws NullPointerException if any key or value in {@code multimap} is
286   *         null
287   */
288  public static <K, V> ImmutableMultimap<K, V> copyOf(
289      Multimap<? extends K, ? extends V> multimap) {
290    if (multimap instanceof ImmutableMultimap) {
291      @SuppressWarnings("unchecked") // safe since multimap is not writable
292      ImmutableMultimap<K, V> kvMultimap
293          = (ImmutableMultimap<K, V>) multimap;
294      if (!kvMultimap.isPartialView()) {
295        return kvMultimap;
296      }
297    }
298    return ImmutableListMultimap.copyOf(multimap);
299  }
300
301  final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map;
302  final transient int size;
303
304  // These constants allow the deserialization code to set final fields. This
305  // holder class makes sure they are not initialized unless an instance is
306  // deserialized.
307  @GwtIncompatible("java serialization is not supported")
308  static class FieldSettersHolder {
309    static final Serialization.FieldSetter<ImmutableMultimap>
310        MAP_FIELD_SETTER = Serialization.getFieldSetter(
311        ImmutableMultimap.class, "map");
312    static final Serialization.FieldSetter<ImmutableMultimap>
313        SIZE_FIELD_SETTER = Serialization.getFieldSetter(
314        ImmutableMultimap.class, "size");
315    static final Serialization.FieldSetter<ImmutableSetMultimap>
316        EMPTY_SET_FIELD_SETTER = Serialization.getFieldSetter(
317        ImmutableSetMultimap.class, "emptySet");
318  }
319
320  ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map,
321      int size) {
322    this.map = map;
323    this.size = size;
324  }
325
326  // mutators (not supported)
327
328  /**
329   * Guaranteed to throw an exception and leave the multimap unmodified.
330   *
331   * @throws UnsupportedOperationException always
332   * @deprecated Unsupported operation.
333   */
334  @Deprecated
335  @Override
336  public ImmutableCollection<V> removeAll(Object key) {
337    throw new UnsupportedOperationException();
338  }
339
340  /**
341   * Guaranteed to throw an exception and leave the multimap unmodified.
342   *
343   * @throws UnsupportedOperationException always
344   * @deprecated Unsupported operation.
345   */
346  @Deprecated
347  @Override
348  public ImmutableCollection<V> replaceValues(K key,
349      Iterable<? extends V> values) {
350    throw new UnsupportedOperationException();
351  }
352
353  /**
354   * Guaranteed to throw an exception and leave the multimap unmodified.
355   *
356   * @throws UnsupportedOperationException always
357   * @deprecated Unsupported operation.
358   */
359  @Deprecated
360  @Override
361  public void clear() {
362    throw new UnsupportedOperationException();
363  }
364
365  /**
366   * Returns an immutable collection of the values for the given key.  If no
367   * mappings in the multimap have the provided key, an empty immutable
368   * collection is returned. The values are in the same order as the parameters
369   * used to build this multimap.
370   */
371  @Override
372  public abstract ImmutableCollection<V> get(K key);
373
374  /**
375   * Returns an immutable multimap which is the inverse of this one. For every
376   * key-value mapping in the original, the result will have a mapping with
377   * key and value reversed.
378   *
379   * @since 11.0
380   */
381  public abstract ImmutableMultimap<V, K> inverse();
382
383  /**
384   * Guaranteed to throw an exception and leave the multimap unmodified.
385   *
386   * @throws UnsupportedOperationException always
387   * @deprecated Unsupported operation.
388   */
389  @Deprecated
390  @Override
391  public boolean put(K key, V value) {
392    throw new UnsupportedOperationException();
393  }
394
395  /**
396   * Guaranteed to throw an exception and leave the multimap unmodified.
397   *
398   * @throws UnsupportedOperationException always
399   * @deprecated Unsupported operation.
400   */
401  @Deprecated
402  @Override
403  public boolean putAll(K key, Iterable<? extends V> values) {
404    throw new UnsupportedOperationException();
405  }
406
407  /**
408   * Guaranteed to throw an exception and leave the multimap unmodified.
409   *
410   * @throws UnsupportedOperationException always
411   * @deprecated Unsupported operation.
412   */
413  @Deprecated
414  @Override
415  public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
416    throw new UnsupportedOperationException();
417  }
418
419  /**
420   * Guaranteed to throw an exception and leave the multimap unmodified.
421   *
422   * @throws UnsupportedOperationException always
423   * @deprecated Unsupported operation.
424   */
425  @Deprecated
426  @Override
427  public boolean remove(Object key, Object value) {
428    throw new UnsupportedOperationException();
429  }
430  
431  /**
432   * Returns {@code true} if this immutable multimap's implementation contains references to
433   * user-created objects that aren't accessible via this multimap's methods. This is generally
434   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
435   * memory leaks.
436   */
437  boolean isPartialView() {
438    return map.isPartialView();
439  }
440
441  // accessors
442
443  @Override
444  public boolean containsKey(@Nullable Object key) {
445    return map.containsKey(key);
446  }
447
448  @Override
449  public boolean containsValue(@Nullable Object value) {
450    return value != null && super.containsValue(value);
451  }
452  
453  @Override
454  public int size() {
455    return size;
456  }
457
458  // views
459
460  /**
461   * Returns an immutable set of the distinct keys in this multimap. These keys
462   * are ordered according to when they first appeared during the construction
463   * of this multimap.
464   */
465  @Override
466  public ImmutableSet<K> keySet() {
467    return map.keySet();
468  }
469
470  /**
471   * Returns an immutable map that associates each key with its corresponding
472   * values in the multimap.
473   */
474  @Override
475  @SuppressWarnings("unchecked") // a widening cast
476  public ImmutableMap<K, Collection<V>> asMap() {
477    return (ImmutableMap) map;
478  }
479  
480  @Override
481  Map<K, Collection<V>> createAsMap() {
482    throw new AssertionError("should never be called");
483  }
484
485  /**
486   * Returns an immutable collection of all key-value pairs in the multimap. Its
487   * iterator traverses the values for the first key, the values for the second
488   * key, and so on.
489   */
490  @Override
491  public ImmutableCollection<Entry<K, V>> entries() {
492    return (ImmutableCollection<Entry<K, V>>) super.entries();
493  }
494  
495  @Override
496  ImmutableCollection<Entry<K, V>> createEntries() {
497    return new EntryCollection<K, V>(this);
498  }
499
500  private static class EntryCollection<K, V>
501      extends ImmutableCollection<Entry<K, V>> {
502    final ImmutableMultimap<K, V> multimap;
503
504    EntryCollection(ImmutableMultimap<K, V> multimap) {
505      this.multimap = multimap;
506    }
507
508    @Override public UnmodifiableIterator<Entry<K, V>> iterator() {
509      return multimap.entryIterator();
510    }
511
512    @Override boolean isPartialView() {
513      return multimap.isPartialView();
514    }
515
516    @Override
517    public int size() {
518      return multimap.size();
519    }
520
521    @Override public boolean contains(Object object) {
522      if (object instanceof Entry) {
523        Entry<?, ?> entry = (Entry<?, ?>) object;
524        return multimap.containsEntry(entry.getKey(), entry.getValue());
525      }
526      return false;
527    }
528
529    private static final long serialVersionUID = 0;
530  }
531  
532  private abstract class Itr<T> extends UnmodifiableIterator<T> {
533    final Iterator<Entry<K, Collection<V>>> mapIterator = asMap().entrySet().iterator();
534    K key = null;
535    Iterator<V> valueIterator = Iterators.emptyIterator();
536    
537    abstract T output(K key, V value);
538
539    @Override
540    public boolean hasNext() {
541      return mapIterator.hasNext() || valueIterator.hasNext();
542    }
543
544    @Override
545    public T next() {
546      if (!valueIterator.hasNext()) {
547        Entry<K, Collection<V>> mapEntry = mapIterator.next();
548        key = mapEntry.getKey();
549        valueIterator = mapEntry.getValue().iterator();
550      }
551      return output(key, valueIterator.next());
552    }
553  }
554  
555  @Override
556  UnmodifiableIterator<Entry<K, V>> entryIterator() {
557    return new Itr<Entry<K, V>>() {
558      @Override
559      Entry<K, V> output(K key, V value) {
560        return Maps.immutableEntry(key, value);
561      }
562    };
563  }
564
565  /**
566   * Returns a collection, which may contain duplicates, of all keys. The number
567   * of times a key appears in the returned multiset equals the number of
568   * mappings the key has in the multimap. Duplicate keys appear consecutively
569   * in the multiset's iteration order.
570   */
571  @Override
572  public ImmutableMultiset<K> keys() {
573    return (ImmutableMultiset<K>) super.keys();
574  }
575
576  @Override
577  ImmutableMultiset<K> createKeys() {
578    return new Keys();
579  }
580
581  @SuppressWarnings("serial") // Uses writeReplace, not default serialization
582  class Keys extends ImmutableMultiset<K> {
583    @Override
584    public boolean contains(@Nullable Object object) {
585      return containsKey(object);
586    }
587
588    @Override
589    public int count(@Nullable Object element) {
590      Collection<V> values = map.get(element);
591      return (values == null) ? 0 : values.size();
592    }
593
594    @Override
595    public Set<K> elementSet() {
596      return keySet();
597    }
598
599    @Override
600    public int size() {
601      return ImmutableMultimap.this.size();
602    }
603    
604    @Override
605    Multiset.Entry<K> getEntry(int index) {
606      Map.Entry<K, ? extends Collection<V>> entry = map.entrySet().asList().get(index);
607      return Multisets.immutableEntry(entry.getKey(), entry.getValue().size());
608    }
609
610    @Override
611    boolean isPartialView() {
612      return true;
613    }
614  }
615
616  /**
617   * Returns an immutable collection of the values in this multimap. Its
618   * iterator traverses the values for the first key, the values for the second
619   * key, and so on.
620   */
621  @Override
622  public ImmutableCollection<V> values() {
623    return (ImmutableCollection<V>) super.values();
624  }
625  
626  @Override
627  ImmutableCollection<V> createValues() {
628    return new Values<K, V>(this);
629  }
630
631  @Override
632  UnmodifiableIterator<V> valueIterator() {
633    return new Itr<V>() {
634      @Override
635      V output(K key, V value) {
636        return value;
637      }
638    };
639  }
640
641  private static final class Values<K, V> extends ImmutableCollection<V> {
642    private transient final ImmutableMultimap<K, V> multimap;
643    
644    Values(ImmutableMultimap<K, V> multimap) {
645      this.multimap = multimap;
646    }
647
648    @Override
649    public boolean contains(@Nullable Object object) {
650      return multimap.containsValue(object);
651    }
652    
653    @Override public UnmodifiableIterator<V> iterator() {
654      return multimap.valueIterator();
655    }
656
657    @GwtIncompatible("not present in emulated superclass")
658    @Override
659    int copyIntoArray(Object[] dst, int offset) {
660      for (ImmutableCollection<V> valueCollection : multimap.map.values()) {
661        offset = valueCollection.copyIntoArray(dst, offset);
662      }
663      return offset;
664    }
665
666    @Override
667    public int size() {
668      return multimap.size();
669    }
670
671    @Override boolean isPartialView() {
672      return true;
673    }
674
675    private static final long serialVersionUID = 0;
676  }
677
678  private static final long serialVersionUID = 0;
679}