    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
    025    import java.io.Serializable;
    026    import java.util.Arrays;
    027    import java.util.Collection;
    028    import java.util.Collections;
    029    import java.util.Comparator;
    030    import java.util.Iterator;
    031    import java.util.LinkedHashMap;
    032    import java.util.List;
    033    import java.util.Map;
    034    import java.util.TreeMap;
    035
    036    import 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.0 (imported from Google Collections Library)
    055     */
    056    @GwtCompatible(emulated = true)
    057    public 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.0 (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.0
    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.0
    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        static final Serialization.FieldSetter<ImmutableMultimap>
    294            MAP_FIELD_SETTER = Serialization.getFieldSetter(
    295            ImmutableMultimap.class, "map");
    296        static final Serialization.FieldSetter<ImmutableMultimap>
    297            SIZE_FIELD_SETTER = Serialization.getFieldSetter(
    298            ImmutableMultimap.class, "size");
    299      }
    300
    301      ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map,
    302          int size) {
    303        this.map = map;
    304        this.size = size;
    305      }
    306
    307      // mutators (not supported)
    308
    309      /**
    310       * Guaranteed to throw an exception and leave the multimap unmodified.
    311       *
    312       * @throws UnsupportedOperationException always
    313       */
    314      @Override
    315      public ImmutableCollection<V> removeAll(Object key) {
    316        throw new UnsupportedOperationException();
    317      }
    318
    319      /**
    320       * Guaranteed to throw an exception and leave the multimap unmodified.
    321       *
    322       * @throws UnsupportedOperationException always
    323       */
    324      @Override
    325      public ImmutableCollection<V> replaceValues(K key,
    326          Iterable<? extends V> values) {
    327        throw new UnsupportedOperationException();
    328      }
    329
    330      /**
    331       * Guaranteed to throw an exception and leave the multimap unmodified.
    332       *
    333       * @throws UnsupportedOperationException always
    334       */
    335      @Override
    336      public void clear() {
    337        throw new UnsupportedOperationException();
    338      }
    339
    340      /**
    341       * Returns an immutable collection of the values for the given key.  If no
    342       * mappings in the multimap have the provided key, an empty immutable
    343       * collection is returned. The values are in the same order as the parameters
    344       * used to build this multimap.
    345       */
    346      @Override
    347      public abstract ImmutableCollection<V> get(K key);
    348
    349      /**
    350       * Guaranteed to throw an exception and leave the multimap unmodified.
    351       *
    352       * @throws UnsupportedOperationException always
    353       */
    354      @Override
    355      public boolean put(K key, V value) {
    356        throw new UnsupportedOperationException();
    357      }
    358
    359      /**
    360       * Guaranteed to throw an exception and leave the multimap unmodified.
    361       *
    362       * @throws UnsupportedOperationException always
    363       */
    364      @Override
    365      public boolean putAll(K key, Iterable<? extends V> values) {
    366        throw new UnsupportedOperationException();
    367      }
    368
    369      /**
    370       * Guaranteed to throw an exception and leave the multimap unmodified.
    371       *
    372       * @throws UnsupportedOperationException always
    373       */
    374      @Override
    375      public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
    376        throw new UnsupportedOperationException();
    377      }
    378
    379      /**
    380       * Guaranteed to throw an exception and leave the multimap unmodified.
    381       *
    382       * @throws UnsupportedOperationException always
    383       */
    384      @Override
    385      public boolean remove(Object key, Object value) {
    386        throw new UnsupportedOperationException();
    387      }
    388
    389      boolean isPartialView(){
    390        return map.isPartialView();
    391      }
    392
    393      // accessors
    394
    395      @Override
    396      public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
    397        Collection<V> values = map.get(key);
    398        return values != null && values.contains(value);
    399      }
    400
    401      @Override
    402      public boolean containsKey(@Nullable Object key) {
    403        return map.containsKey(key);
    404      }
    405
    406      @Override
    407      public boolean containsValue(@Nullable Object value) {
    408        for (Collection<V> valueCollection : map.values()) {
    409          if (valueCollection.contains(value)) {
    410            return true;
    411          }
    412        }
    413        return false;
    414      }
    415
    416      @Override
    417      public boolean isEmpty() {
    418        return size == 0;
    419      }
    420
    421      @Override
    422      public int size() {
    423        return size;
    424      }
    425
    426      @Override public boolean equals(@Nullable Object object) {
    427        if (object instanceof Multimap) {
    428          Multimap<?, ?> that = (Multimap<?, ?>) object;
    429          return this.map.equals(that.asMap());
    430        }
    431        return false;
    432      }
    433
    434      @Override public int hashCode() {
    435        return map.hashCode();
    436      }
    437
    438      @Override public String toString() {
    439        return map.toString();
    440      }
    441
    442      // views
    443
    444      /**
    445       * Returns an immutable set of the distinct keys in this multimap. These keys
    446       * are ordered according to when they first appeared during the construction
    447       * of this multimap.
    448       */
    449      @Override
    450      public ImmutableSet<K> keySet() {
    451        return map.keySet();
    452      }
    453
    454      /**
    455       * Returns an immutable map that associates each key with its corresponding
    456       * values in the multimap.
    457       */
    458      @Override
    459      @SuppressWarnings("unchecked") // a widening cast
    460      public ImmutableMap<K, Collection<V>> asMap() {
    461        return (ImmutableMap) map;
    462      }
    463
    464      private transient ImmutableCollection<Map.Entry<K, V>> entries;
    465
    466      /**
    467       * Returns an immutable collection of all key-value pairs in the multimap. Its
    468       * iterator traverses the values for the first key, the values for the second
    469       * key, and so on.
    470       */
    471      @Override
    472      public ImmutableCollection<Map.Entry<K, V>> entries() {
    473        ImmutableCollection<Map.Entry<K, V>> result = entries;
    474        return (result == null)
    475            ? (entries = new EntryCollection<K, V>(this)) : result;
    476      }
    477
    478      private static class EntryCollection<K, V>
    479          extends ImmutableCollection<Map.Entry<K, V>> {
    480        final ImmutableMultimap<K, V> multimap;
    481
    482        EntryCollection(ImmutableMultimap<K, V> multimap) {
    483          this.multimap = multimap;
    484        }
    485
    486        @Override public UnmodifiableIterator<Map.Entry<K, V>> iterator() {
    487          final Iterator<? extends Map.Entry<K, ? extends ImmutableCollection<V>>>
    488              mapIterator = this.multimap.map.entrySet().iterator();
    489
    490          return new UnmodifiableIterator<Map.Entry<K, V>>() {
    491            K key;
    492            Iterator<V> valueIterator;
    493
    494            @Override
    495            public boolean hasNext() {
    496              return (key != null && valueIterator.hasNext())
    497                  || mapIterator.hasNext();
    498            }
    499
    500            @Override
    501            public Map.Entry<K, V> next() {
    502              if (key == null || !valueIterator.hasNext()) {
    503                Map.Entry<K, ? extends ImmutableCollection<V>> entry
    504                    = mapIterator.next();
    505                key = entry.getKey();
    506                valueIterator = entry.getValue().iterator();
    507              }
    508              return Maps.immutableEntry(key, valueIterator.next());
    509            }
    510          };
    511        }
    512
    513        @Override boolean isPartialView() {
    514          return multimap.isPartialView();
    515        }
    516
    517        @Override
    518        public int size() {
    519          return multimap.size();
    520        }
    521
    522        @Override public boolean contains(Object object) {
    523          if (object instanceof Map.Entry) {
    524            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
    525            return multimap.containsEntry(entry.getKey(), entry.getValue());
    526          }
    527          return false;
    528        }
    529
    530        private static final long serialVersionUID = 0;
    531      }
    532
    533      private transient ImmutableMultiset<K> keys;
    534
    535      /**
    536       * Returns a collection, which may contain duplicates, of all keys. The number
    537       * of times a key appears in the returned multiset equals the number of
    538       * mappings the key has in the multimap. Duplicate keys appear consecutively
    539       * in the multiset's iteration order.
    540       */
    541      @Override
    542      public ImmutableMultiset<K> keys() {
    543        ImmutableMultiset<K> result = keys;
    544        return (result == null) ? (keys = createKeys()) : result;
    545      }
    546
    547      private ImmutableMultiset<K> createKeys() {
    548        ImmutableMultiset.Builder<K> builder = ImmutableMultiset.builder();
    549        for (Map.Entry<K, ? extends ImmutableCollection<V>> entry
    550            : map.entrySet()) {
    551          builder.addCopies(entry.getKey(), entry.getValue().size());
    552        }
    553        return builder.build();
    554      }
    555
    556      private transient ImmutableCollection<V> values;
    557
    558      /**
    559       * Returns an immutable collection of the values in this multimap. Its
    560       * iterator traverses the values for the first key, the values for the second
    561       * key, and so on.
    562       */
    563      @Override
    564      public ImmutableCollection<V> values() {
    565        ImmutableCollection<V> result = values;
    566        return (result == null) ? (values = new Values<V>(this)) : result;
    567      }
    568
    569      private static class Values<V> extends ImmutableCollection<V> {
    570        final ImmutableMultimap<?, V> multimap;
    571
    572        Values(ImmutableMultimap<?, V> multimap) {
    573          this.multimap = multimap;
    574        }
    575
    576        @Override public UnmodifiableIterator<V> iterator() {
    577          final Iterator<? extends Map.Entry<?, V>> entryIterator
    578              = multimap.entries().iterator();
    579          return new UnmodifiableIterator<V>() {
    580            @Override
    581            public boolean hasNext() {
    582              return entryIterator.hasNext();
    583            }
    584            @Override
    585            public V next() {
    586              return entryIterator.next().getValue();
    587            }
    588          };
    589        }
    590
    591        @Override
    592        public int size() {
    593          return multimap.size();
    594        }
    595
    596        @Override boolean isPartialView() {
    597          return true;
    598        }
    599
    600        private static final long serialVersionUID = 0;
    601      }
    602
    603      private static final long serialVersionUID = 0;
    604    }