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