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    
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.Serializable;
027    import java.util.Arrays;
028    import java.util.Collection;
029    import java.util.Collections;
030    import java.util.Comparator;
031    import java.util.Iterator;
032    import java.util.LinkedHashMap;
033    import java.util.List;
034    import java.util.Map;
035    import java.util.Map.Entry;
036    import java.util.Set;
037    
038    import 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)
066    public 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    }