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