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    import static com.google.common.collect.Iterables.getOnlyElement;
021    
022    import com.google.common.annotations.GwtCompatible;
023    import com.google.common.collect.ImmutableSet.TransformedImmutableSet;
024    
025    import java.io.Serializable;
026    import java.util.ArrayList;
027    import java.util.Collections;
028    import java.util.HashMap;
029    import java.util.List;
030    import java.util.Map;
031    
032    import javax.annotation.Nullable;
033    
034    /**
035     * An immutable, hash-based {@link Map} with reliable user-specified iteration
036     * order. Does not permit null keys or values.
037     *
038     * <p>Unlike {@link Collections#unmodifiableMap}, which is a <i>view</i> of a
039     * separate map which can still change, an instance of {@code ImmutableMap}
040     * contains its own data and will <i>never</i> change. {@code ImmutableMap} is
041     * convenient for {@code public static final} maps ("constant maps") and also
042     * lets you easily make a "defensive copy" of a map provided to your class by a
043     * caller.
044     *
045     * <p><i>Performance notes:</i> unlike {@link HashMap}, {@code ImmutableMap} is
046     * not optimized for element types that have slow {@link Object#equals} or
047     * {@link Object#hashCode} implementations. You can get better performance by
048     * having your element type cache its own hash codes, and by making use of the
049     * cached values to short-circuit a slow {@code equals} algorithm.
050     *
051     * <p>See the Guava User Guide article on <a href=
052     * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
053     * immutable collections</a>.
054     *
055     * @author Jesse Wilson
056     * @author Kevin Bourrillion
057     * @since 2.0 (imported from Google Collections Library)
058     */
059    @GwtCompatible(serializable = true, emulated = true)
060    @SuppressWarnings("serial") // we're overriding default serialization
061    public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
062      /**
063       * Returns the empty map. This map behaves and performs comparably to
064       * {@link Collections#emptyMap}, and is preferable mainly for consistency
065       * and maintainability of your code.
066       */
067      // Casting to any type is safe because the set will never hold any elements.
068      @SuppressWarnings("unchecked")
069      public static <K, V> ImmutableMap<K, V> of() {
070        return (ImmutableMap<K, V>) EmptyImmutableMap.INSTANCE;
071      }
072    
073      /**
074       * Returns an immutable map containing a single entry. This map behaves and
075       * performs comparably to {@link Collections#singletonMap} but will not accept
076       * a null key or value. It is preferable mainly for consistency and
077       * maintainability of your code.
078       */
079      public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
080        return new SingletonImmutableMap<K, V>(
081            checkNotNull(k1), checkNotNull(v1));
082      }
083    
084      /**
085       * Returns an immutable map containing the given entries, in order.
086       *
087       * @throws IllegalArgumentException if duplicate keys are provided
088       */
089      public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
090        return new RegularImmutableMap<K, V>(entryOf(k1, v1), entryOf(k2, v2));
091      }
092    
093      /**
094       * Returns an immutable map containing the given entries, in order.
095       *
096       * @throws IllegalArgumentException if duplicate keys are provided
097       */
098      public static <K, V> ImmutableMap<K, V> of(
099          K k1, V v1, K k2, V v2, K k3, V v3) {
100        return new RegularImmutableMap<K, V>(
101            entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
102      }
103    
104      /**
105       * Returns an immutable map containing the given entries, in order.
106       *
107       * @throws IllegalArgumentException if duplicate keys are provided
108       */
109      public static <K, V> ImmutableMap<K, V> of(
110          K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
111        return new RegularImmutableMap<K, V>(
112            entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
113      }
114    
115      /**
116       * Returns an immutable map containing the given entries, in order.
117       *
118       * @throws IllegalArgumentException if duplicate keys are provided
119       */
120      public static <K, V> ImmutableMap<K, V> of(
121          K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
122        return new RegularImmutableMap<K, V>(entryOf(k1, v1),
123            entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
124      }
125    
126      // looking for of() with > 5 entries? Use the builder instead.
127    
128      /**
129       * Returns a new builder. The generated builder is equivalent to the builder
130       * created by the {@link Builder} constructor.
131       */
132      public static <K, V> Builder<K, V> builder() {
133        return new Builder<K, V>();
134      }
135    
136      /**
137       * Verifies that {@code key} and {@code value} are non-null, and returns a new
138       * immutable entry with those values.
139       *
140       * <p>A call to {@link Map.Entry#setValue} on the returned entry will always
141       * throw {@link UnsupportedOperationException}.
142       */
143      static <K, V> Entry<K, V> entryOf(K key, V value) {
144        return Maps.immutableEntry(
145            checkNotNull(key, "null key"),
146            checkNotNull(value, "null value"));
147      }
148    
149      /**
150       * A builder for creating immutable map instances, especially {@code public
151       * static final} maps ("constant maps"). Example: <pre>   {@code
152       *
153       *   static final ImmutableMap<String, Integer> WORD_TO_INT =
154       *       new ImmutableMap.Builder<String, Integer>()
155       *           .put("one", 1)
156       *           .put("two", 2)
157       *           .put("three", 3)
158       *           .build();}</pre>
159       *
160       * For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are
161       * even more convenient.
162       *
163       * <p>Builder instances can be reused - it is safe to call {@link #build}
164       * multiple times to build multiple maps in series. Each map is a superset of
165       * the maps created before it.
166       *
167       * @since 2.0 (imported from Google Collections Library)
168       */
169      public static class Builder<K, V> {
170        final ArrayList<Entry<K, V>> entries = Lists.newArrayList();
171    
172        /**
173         * Creates a new builder. The returned builder is equivalent to the builder
174         * generated by {@link ImmutableMap#builder}.
175         */
176        public Builder() {}
177    
178        /**
179         * Associates {@code key} with {@code value} in the built map. Duplicate
180         * keys are not allowed, and will cause {@link #build} to fail.
181         */
182        public Builder<K, V> put(K key, V value) {
183          entries.add(entryOf(key, value));
184          return this;
185        }
186    
187        /**
188         * Adds the given {@code entry} to the map, making it immutable if
189         * necessary. Duplicate keys are not allowed, and will cause {@link #build}
190         * to fail.
191         *
192         * @since 11.0
193         */
194        public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
195          K key = entry.getKey();
196          V value = entry.getValue();
197          if (entry instanceof ImmutableEntry<?, ?>) {
198            checkNotNull(key);
199            checkNotNull(value);
200            @SuppressWarnings("unchecked") // all supported methods are covariant
201            Entry<K, V> immutableEntry = (Entry<K, V>) entry;
202            entries.add(immutableEntry);
203          } else {
204            // Directly calling entryOf(entry.getKey(), entry.getValue()) can cause
205            // compilation error in Eclipse.
206            entries.add(entryOf(key, value));
207          }
208          return this;
209        }
210    
211        /**
212         * Associates all of the given map's keys and values in the built map.
213         * Duplicate keys are not allowed, and will cause {@link #build} to fail.
214         *
215         * @throws NullPointerException if any key or value in {@code map} is null
216         */
217        public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
218          entries.ensureCapacity(entries.size() + map.size());
219          for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
220            put(entry.getKey(), entry.getValue());
221          }
222          return this;
223        }
224    
225        /*
226         * TODO(kevinb): Should build() and the ImmutableBiMap & ImmutableSortedMap
227         * versions throw an IllegalStateException instead?
228         */
229    
230        /**
231         * Returns a newly-created immutable map.
232         *
233         * @throws IllegalArgumentException if duplicate keys were added
234         */
235        public ImmutableMap<K, V> build() {
236          return fromEntryList(entries);
237        }
238    
239        private static <K, V> ImmutableMap<K, V> fromEntryList(
240            List<Entry<K, V>> entries) {
241          int size = entries.size();
242          switch (size) {
243            case 0:
244              return of();
245            case 1:
246              return new SingletonImmutableMap<K, V>(getOnlyElement(entries));
247            default:
248              Entry<?, ?>[] entryArray
249                  = entries.toArray(new Entry<?, ?>[entries.size()]);
250              return new RegularImmutableMap<K, V>(entryArray);
251          }
252        }
253      }
254    
255      /**
256       * Returns an immutable map containing the same entries as {@code map}. If
257       * {@code map} somehow contains entries with duplicate keys (for example, if
258       * it is a {@code SortedMap} whose comparator is not <i>consistent with
259       * equals</i>), the results of this method are undefined.
260       *
261       * <p>Despite the method name, this method attempts to avoid actually copying
262       * the data when it is safe to do so. The exact circumstances under which a
263       * copy will or will not be performed are undocumented and subject to change.
264       *
265       * @throws NullPointerException if any key or value in {@code map} is null
266       */
267      public static <K, V> ImmutableMap<K, V> copyOf(
268          Map<? extends K, ? extends V> map) {
269        if ((map instanceof ImmutableMap) && !(map instanceof ImmutableSortedMap)) {
270          // TODO(user): Make ImmutableMap.copyOf(immutableBiMap) call copyOf()
271          // on the ImmutableMap delegate(), rather than the bimap itself
272    
273          @SuppressWarnings("unchecked") // safe since map is not writable
274          ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
275          if (!kvMap.isPartialView()) {
276            return kvMap;
277          }
278        }
279    
280        @SuppressWarnings("unchecked") // we won't write to this array
281        Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]);
282        switch (entries.length) {
283          case 0:
284            return of();
285          case 1:
286            return new SingletonImmutableMap<K, V>(entryOf(
287                entries[0].getKey(), entries[0].getValue()));
288          default:
289            for (int i = 0; i < entries.length; i++) {
290              K k = entries[i].getKey();
291              V v = entries[i].getValue();
292              entries[i] = entryOf(k, v);
293            }
294            return new RegularImmutableMap<K, V>(entries);
295        }
296      }
297    
298      ImmutableMap() {}
299    
300      /**
301       * Guaranteed to throw an exception and leave the map unmodified.
302       *
303       * @throws UnsupportedOperationException always
304       */
305      @Override
306      public final V put(K k, V v) {
307        throw new UnsupportedOperationException();
308      }
309    
310      /**
311       * Guaranteed to throw an exception and leave the map unmodified.
312       *
313       * @throws UnsupportedOperationException always
314       */
315      @Override
316      public final V remove(Object o) {
317        throw new UnsupportedOperationException();
318      }
319    
320      /**
321       * Guaranteed to throw an exception and leave the map unmodified.
322       *
323       * @throws UnsupportedOperationException always
324       */
325      @Override
326      public final void putAll(Map<? extends K, ? extends V> map) {
327        throw new UnsupportedOperationException();
328      }
329    
330      /**
331       * Guaranteed to throw an exception and leave the map unmodified.
332       *
333       * @throws UnsupportedOperationException always
334       */
335      @Override
336      public final void clear() {
337        throw new UnsupportedOperationException();
338      }
339    
340      @Override
341      public boolean isEmpty() {
342        return size() == 0;
343      }
344    
345      @Override
346      public boolean containsKey(@Nullable Object key) {
347        return get(key) != null;
348      }
349    
350      // Overriding to mark it Nullable
351      @Override
352      public abstract boolean containsValue(@Nullable Object value);
353    
354      // Overriding to mark it Nullable
355      @Override
356      public abstract V get(@Nullable Object key);
357    
358      private transient ImmutableSet<Entry<K, V>> entrySet;
359    
360      /**
361       * Returns an immutable set of the mappings in this map. The entries are in
362       * the same order as the parameters used to build this map.
363       */
364      @Override
365      public ImmutableSet<Entry<K, V>> entrySet() {
366        ImmutableSet<Entry<K, V>> result = entrySet;
367        return (result == null) ? entrySet = createEntrySet() : result;
368      }
369    
370      abstract ImmutableSet<Entry<K, V>> createEntrySet();
371    
372      abstract class EntrySet extends ImmutableSet<Entry<K, V>> {
373        @Override
374        public int size() {
375          return ImmutableMap.this.size();
376        }
377    
378        @Override
379        public boolean contains(@Nullable Object object) {
380          if (object instanceof Entry) {
381            Entry<?, ?> entry = (Entry<?, ?>) object;
382            V value = get(entry.getKey());
383            return value != null && value.equals(entry.getValue());
384          }
385          return false;
386        }
387    
388        @Override
389        boolean isPartialView() {
390          return ImmutableMap.this.isPartialView();
391        }
392    
393        @Override
394        Object writeReplace() {
395          return new EntrySetSerializedForm<K, V>(ImmutableMap.this);
396        }
397      }
398    
399      private static class EntrySetSerializedForm<K, V> implements Serializable {
400        final ImmutableMap<K, V> map;
401        EntrySetSerializedForm(ImmutableMap<K, V> map) {
402          this.map = map;
403        }
404        Object readResolve() {
405          return map.entrySet();
406        }
407        private static final long serialVersionUID = 0;
408      }
409    
410      private transient ImmutableSet<K> keySet;
411    
412      /**
413       * Returns an immutable set of the keys in this map. These keys are in
414       * the same order as the parameters used to build this map.
415       */
416      @Override
417      public ImmutableSet<K> keySet() {
418        ImmutableSet<K> result = keySet;
419        return (result == null) ? keySet = createKeySet() : result;
420      }
421    
422      ImmutableSet<K> createKeySet() {
423        return new KeySet();
424      }
425    
426      class KeySet extends TransformedImmutableSet<Entry<K, V>, K> {
427        KeySet() {
428          super(entrySet());
429        }
430    
431        KeySet(int hashCode) {
432          super(entrySet(), hashCode);
433        }
434    
435        @Override
436        K transform(Entry<K, V> entry) {
437          return entry.getKey();
438        }
439    
440        @Override
441        public boolean contains(@Nullable Object object) {
442          return containsKey(object);
443        }
444    
445        @Override
446        boolean isPartialView() {
447          return true;
448        }
449    
450        @Override
451        ImmutableList<K> createAsList() {
452          // TODO(user): rewrite to delegate contains() calls to the KeySet
453          return new TransformedImmutableList<Entry<K, V>, K>(entrySet().asList()) {
454            @Override
455            K transform(Entry<K, V> entry) {
456              return entry.getKey();
457            }
458          };
459        }
460    
461        @Override Object writeReplace() {
462          return new KeySetSerializedForm<K>(ImmutableMap.this);
463        }
464      }
465    
466      private static class KeySetSerializedForm<K> implements Serializable {
467        final ImmutableMap<K, ?> map;
468        KeySetSerializedForm(ImmutableMap<K, ?> map) {
469          this.map = map;
470        }
471        Object readResolve() {
472          return map.keySet();
473        }
474        private static final long serialVersionUID = 0;
475      }
476    
477      private transient ImmutableCollection<V> values;
478    
479      /**
480       * Returns an immutable collection of the values in this map. The values are
481       * in the same order as the parameters used to build this map.
482       */
483      @Override
484      public ImmutableCollection<V> values() {
485        ImmutableCollection<V> result = values;
486        return (result == null) ? values = createValues() : result;
487      }
488    
489      ImmutableCollection<V> createValues() {
490        return new Values();
491      }
492    
493      class Values extends ImmutableCollection<V> {
494        @Override
495        public int size() {
496          return ImmutableMap.this.size();
497        }
498    
499        @Override
500        public UnmodifiableIterator<V> iterator() {
501          return Maps.valueIterator(entrySet().iterator());
502        }
503    
504        @Override
505        public boolean contains(Object object) {
506          return containsValue(object);
507        }
508    
509        @Override
510        boolean isPartialView() {
511          return true;
512        }
513    
514        @Override
515        ImmutableList<V> createAsList() {
516          // TODO(user): rewrite to delegate contains() calls to the Values
517          return new TransformedImmutableList<Entry<K, V>, V>(entrySet().asList()) {
518            @Override
519            V transform(Entry<K, V> entry) {
520              return entry.getValue();
521            }
522          };
523        }
524    
525        @Override Object writeReplace() {
526          return new ValuesSerializedForm<V>(ImmutableMap.this);
527        }
528      }
529    
530      private static class ValuesSerializedForm<V> implements Serializable {
531        final ImmutableMap<?, V> map;
532        ValuesSerializedForm(ImmutableMap<?, V> map) {
533          this.map = map;
534        }
535        Object readResolve() {
536          return map.values();
537        }
538        private static final long serialVersionUID = 0;
539      }
540    
541      @Override public boolean equals(@Nullable Object object) {
542        if (object == this) {
543          return true;
544        }
545        if (object instanceof Map) {
546          Map<?, ?> that = (Map<?, ?>) object;
547          return this.entrySet().equals(that.entrySet());
548        }
549        return false;
550      }
551    
552      abstract boolean isPartialView();
553    
554      @Override public int hashCode() {
555        // not caching hash code since it could change if map values are mutable
556        // in a way that modifies their hash codes
557        return entrySet().hashCode();
558      }
559    
560      @Override public String toString() {
561        return Maps.toStringImpl(this);
562      }
563    
564      /**
565       * Serialized type for all ImmutableMap instances. It captures the logical
566       * contents and they are reconstructed using public factory methods. This
567       * ensures that the implementation types remain as implementation details.
568       */
569      static class SerializedForm implements Serializable {
570        private final Object[] keys;
571        private final Object[] values;
572        SerializedForm(ImmutableMap<?, ?> map) {
573          keys = new Object[map.size()];
574          values = new Object[map.size()];
575          int i = 0;
576          for (Entry<?, ?> entry : map.entrySet()) {
577            keys[i] = entry.getKey();
578            values[i] = entry.getValue();
579            i++;
580          }
581        }
582        Object readResolve() {
583          Builder<Object, Object> builder = new Builder<Object, Object>();
584          return createMap(builder);
585        }
586        Object createMap(Builder<Object, Object> builder) {
587          for (int i = 0; i < keys.length; i++) {
588            builder.put(keys[i], values[i]);
589          }
590          return builder.build();
591        }
592        private static final long serialVersionUID = 0;
593      }
594    
595      Object writeReplace() {
596        return new SerializedForm(this);
597      }
598    }