core/src/com/google/inject/internal/util/ImmutableMap.java - platform/external/guice - Git at Google

 /*
  * Copyright (C) 2008 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.google.inject.internal.util;

 import java.io.Serializable;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ConcurrentMap;

 /**
  * An immutable, hash-based {@link Map} with reliable user-specified iteration
  * order. Does not permit null keys or values.
  *
  * <p>Unlike {@link Collections#unmodifiableMap}, which is a <i>view</i> of a
  * separate map which can still change, an instance of {@code ImmutableMap}
  * contains its own data and will <i>never</i> change. {@code ImmutableMap} is
  * convenient for {@code public static final} maps ("constant maps") and also
  * lets you easily make a "defensive copy" of a map provided to your class by a
  * caller.
  *
  * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
  * it has no public or protected constructors. Thus, instances of this class are
  * guaranteed to be immutable.
  *
  * @see ImmutableList
  * @see ImmutableSet
  * @author Jesse Wilson
  * @author Kevin Bourrillion
  */
 @SuppressWarnings("serial") // we're overriding default serialization
 public abstract class ImmutableMap<K, V>
     implements ConcurrentMap<K, V>, Serializable {
   private static final ImmutableMap<?, ?> EMPTY_IMMUTABLE_MAP
       = new EmptyImmutableMap();

   // TODO: restore prebuilder API?  optimize, compare performance to HashMap

   /**
    * Returns the empty map. This map behaves and performs comparably to
    * {@link Collections#emptyMap}, and is preferable mainly for consistency
    * and maintainability of your code.
    */
   // Casting to any type is safe because the set will never hold any elements.
   @SuppressWarnings("unchecked")
   public static <K, V> ImmutableMap<K, V> of() {
     return (ImmutableMap<K, V>) EMPTY_IMMUTABLE_MAP;
   }

   /**
    * Returns an immutable map containing a single entry. This map behaves and
    * performs comparably to {@link Collections#singletonMap} but will not accept
    * a null key or value. It is preferable mainly for consistency and
    * maintainability of your code.
    */
   public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
     return new SingletonImmutableMap<K, V>(
         Preconditions.checkNotNull(k1), Preconditions.checkNotNull(v1));
   }

   /**
    * Returns an immutable map containing the given entries, in order.
    *
    * @throws IllegalArgumentException if duplicate keys are added
    */
   public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
     return new RegularImmutableMap<K, V>(entryOf(k1, v1), entryOf(k2, v2));
   }

   /**
    * Returns an immutable map containing the given entries, in order.
    *
    * @throws IllegalArgumentException if duplicate keys are added
    */
   public static <K, V> ImmutableMap<K, V> of(
       K k1, V v1, K k2, V v2, K k3, V v3) {
     return new RegularImmutableMap<K, V>(
         entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
   }

   /**
    * Returns an immutable map containing the given entries, in order.
    *
    * @throws IllegalArgumentException if duplicate keys are added
    */
   public static <K, V> ImmutableMap<K, V> of(
       K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
     return new RegularImmutableMap<K, V>(
         entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
   }

   /**
    * Returns an immutable map containing the given entries, in order.
    *
    * @throws IllegalArgumentException if duplicate keys are added
    */
   public static <K, V> ImmutableMap<K, V> of(
       K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
     return new RegularImmutableMap<K, V>(entryOf(k1, v1),
         entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
   }

   // looking for of() with > 5 entries? Use the builder instead.

   /**
    * Returns a new builder. The generated builder is equivalent to the builder
    * created by the {@link Builder} constructor.
    */
   public static <K, V> Builder<K, V> builder() {
     return new Builder<K, V>();
   }

   /**
    * Verifies that {@code key} and {@code value} are non-null, and returns a new
    * entry with those values.
    */
   private static <K, V> Entry<K, V> entryOf(K key, V value) {
     return Maps.immutableEntry(Preconditions.checkNotNull(key), Preconditions.checkNotNull(value));
   }

   /**
    * A builder for creating immutable map instances, especially {@code public
    * static final} maps ("constant maps"). Example: <pre>   {@code
    *
    *   static final ImmutableMap<String, Integer> WORD_TO_INT =
    *       new ImmutableMap.Builder<String, Integer>()
    *           .put("one", 1)
    *           .put("two", 2)
    *           .put("three", 3)
    *           .build();}</pre>
    *
    * For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are
    * even more convenient.
    *
    * <p>Builder instances can be reused - it is safe to call {@link #build}
    * multiple times to build multiple maps in series. Each map is a superset of
    * the maps created before it.
    */
   public static class Builder<K, V> {
     final List<Entry<K, V>> entries = Lists.newArrayList();

     /**
      * Creates a new builder. The returned builder is equivalent to the builder
      * generated by {@link ImmutableMap#builder}.
      */
     public Builder() {}

     /**
      * Associates {@code key} with {@code value} in the built map. Duplicate
      * keys are not allowed, and will cause {@link #build} to fail.
      */
     public Builder<K, V> put(K key, V value) {
       entries.add(entryOf(key, value));
       return this;
     }

     /**
      * Associates all of {@code map's} keys and values in the built map.
      * Duplicate keys are not allowed, and will cause {@link #build} to fail.
      *
      * @throws NullPointerException if any key or value in {@code map} is null
      */
     public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
       for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
         put(entry.getKey(), entry.getValue());
       }
       return this;
     }

     // TODO: Should build() and the ImmutableBiMap version throw an
     // IllegalStateException instead?

     /**
      * Returns a newly-created immutable map.
      *
      * @throws IllegalArgumentException if duplicate keys were added
      */
     public ImmutableMap<K, V> build() {
       return fromEntryList(entries);
     }

     private static <K, V> ImmutableMap<K, V> fromEntryList(
         List<Entry<K, V>> entries) {
       int size = entries.size();
       switch (size) {
         case 0:
           return of();
         case 1:
           return new SingletonImmutableMap<K, V>(Iterables.getOnlyElement(entries));
         default:
           Entry<?, ?>[] entryArray
               = entries.toArray(new Entry<?, ?>[entries.size()]);
           return new RegularImmutableMap<K, V>(entryArray);
       }
     }
   }

   /**
    * Returns an immutable map containing the same entries as {@code map}. If
    * {@code map} somehow contains entries with duplicate keys (for example, if
    * it is a {@code SortedMap} whose comparator is not <i>consistent with
    * equals</i>), the results of this method are undefined.
    *
    * <p><b>Note:</b> Despite what the method name suggests, if {@code map} is an
    * {@code ImmutableMap}, no copy will actually be performed, and the given map
    * itself will be returned.
    *
    * @throws NullPointerException if any key or value in {@code map} is null
    */
   public static <K, V> ImmutableMap<K, V> copyOf(
       Map<? extends K, ? extends V> map) {
     if (map instanceof ImmutableMap) {
       @SuppressWarnings("unchecked") // safe since map is not writable
       ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
       return kvMap;
     }

     int size = map.size();
     switch (size) {
       case 0:
         return of();
       case 1:
         Map.Entry<? extends K, ? extends V> loneEntry
             = Iterables.getOnlyElement(map.entrySet());
         /*
          * Must cast next line to (K) and (V) to avoid returning an
          * ImmutableMap<? extends K, ? extends V>, which is incompatible
          * with the return type ImmutableMap<K, V>.  (Eclipse will complain
          * mightily about this line if there's no cast.)
          */
         return of((K) loneEntry.getKey(), (V) loneEntry.getValue());
       default:
         Entry<?, ?>[] array = new Entry<?, ?>[size];
         int i = 0;
         for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
           /*
            * See comment above re: <? extends K, ? extends V> to <K, V>.
            */
           array[i++] = entryOf((K) entry.getKey(), (V) entry.getValue());
         }
         return new RegularImmutableMap<K, V>(array);
     }
   }

   ImmutableMap() {}

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final V put(K k, V v) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final V remove(Object o) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final V putIfAbsent(K key, V value) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final boolean remove(Object key, Object value) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final boolean replace(K key, V oldValue, V newValue) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final V replace(K key, V value) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final void putAll(Map<? extends K, ? extends V> map) {
     throw new UnsupportedOperationException();
   }

   /**
    * Guaranteed to throw an exception and leave the map unmodified.
    *
    * @throws UnsupportedOperationException always
    */
   public final void clear() {
     throw new UnsupportedOperationException();
   }

   // Overriding to mark it Nullable
   public abstract boolean containsKey(@Nullable Object key);

   // Overriding to mark it Nullable
   public abstract boolean containsValue(@Nullable Object value);

   // Overriding to mark it Nullable
   public abstract V get(@Nullable Object key);

   /**
    * Returns an immutable set of the mappings in this map. The entries are in
    * the same order as the parameters used to build this map.
    */
   public abstract ImmutableSet<Entry<K, V>> entrySet();

   /**
    * Returns an immutable set of the keys in this map. These keys are in
    * the same order as the parameters used to build this map.
    */
   public abstract ImmutableSet<K> keySet();

   /**
    * Returns an immutable collection of the values in this map. The values are
    * in the same order as the parameters used to build this map.
    */
   public abstract ImmutableCollection<V> values();

   @Override public boolean equals(@Nullable Object object) {
     if (object == this) {
       return true;
     }
     if (object instanceof Map) {
       Map<?, ?> that = (Map<?, ?>) object;
       return this.entrySet().equals(that.entrySet());
     }
     return false;
   }

   @Override public int hashCode() {
     // not caching hash code since it could change if map values are mutable
     // in a way that modifies their hash codes
     return entrySet().hashCode();
   }

   @Override public String toString() {
     StringBuilder result = new StringBuilder(size() * 16).append('{');
     Iterator<Entry<K, V>> entries = entrySet().iterator();
     result.append(entries.next());
     while (entries.hasNext()) {
       result.append(", ").append(entries.next());
     }
     return result.append('}').toString();
   }

   private static final class EmptyImmutableMap
       extends ImmutableMap<Object, Object> {

     @Override public Object get(Object key) {
       return null;
     }

     public int size() {
       return 0;
     }

     public boolean isEmpty() {
       return true;
     }

     @Override public boolean containsKey(Object key) {
       return false;
     }

     @Override public boolean containsValue(Object value) {
       return false;
     }

     @Override public ImmutableSet<Entry<Object, Object>> entrySet() {
       return ImmutableSet.of();
     }

     @Override public ImmutableSet<Object> keySet() {
       return ImmutableSet.of();
     }

     @Override public ImmutableCollection<Object> values() {
       return ImmutableCollection.EMPTY_IMMUTABLE_COLLECTION;
     }

     @Override public boolean equals(@Nullable Object object) {
       if (object instanceof Map) {
         Map<?, ?> that = (Map<?, ?>) object;
         return that.isEmpty();
       }
       return false;
     }

     @Override public int hashCode() {
       return 0;
     }

     @Override public String toString() {
       return "{}";
     }
   }

   private static final class SingletonImmutableMap<K, V>
       extends ImmutableMap<K, V> {
     private transient final K singleKey;
     private transient final V singleValue;
     private transient Entry<K, V> entry;

     private SingletonImmutableMap(K singleKey, V singleValue) {
       this.singleKey = singleKey;
       this.singleValue = singleValue;
     }

     private SingletonImmutableMap(Entry<K, V> entry) {
       this.entry = entry;
       this.singleKey = entry.getKey();
       this.singleValue = entry.getValue();
     }

     private Entry<K, V> entry() {
       Entry<K, V> e = entry;
       return (e == null)
           ? (entry = Maps.immutableEntry(singleKey, singleValue)) : e;
     }

     @Override public V get(Object key) {
       return singleKey.equals(key) ? singleValue : null;
     }

     public int size() {
       return 1;
     }

     public boolean isEmpty() {
       return false;
     }

     @Override public boolean containsKey(Object key) {
       return singleKey.equals(key);
     }

     @Override public boolean containsValue(Object value) {
       return singleValue.equals(value);
     }

     private transient ImmutableSet<Entry<K, V>> entrySet;

     @Override public ImmutableSet<Entry<K, V>> entrySet() {
       ImmutableSet<Entry<K, V>> es = entrySet;
       return (es == null) ? (entrySet = ImmutableSet.of(entry())) : es;
     }

     private transient ImmutableSet<K> keySet;

     @Override public ImmutableSet<K> keySet() {
       ImmutableSet<K> ks = keySet;
       return (ks == null) ? (keySet = ImmutableSet.of(singleKey)) : ks;
     }

     private transient ImmutableCollection<V> values;

     @Override public ImmutableCollection<V> values() {
       ImmutableCollection<V> v = values;
       return (v == null) ? (values = new Values<V>(singleValue)) : v;
     }

     private static class Values<V> extends ImmutableCollection<V> {
       final V singleValue;

       Values(V singleValue) {
         this.singleValue = singleValue;
       }

       @Override public boolean contains(Object object) {
         return singleValue.equals(object);
       }

       @Override public boolean isEmpty() {
         return false;
       }

       public int size() {
         return 1;
       }

       @Override public UnmodifiableIterator<V> iterator() {
         return Iterators.singletonIterator(singleValue);
       }
     }

     @Override public boolean equals(@Nullable Object object) {
       if (object == this) {
         return true;
       }
       if (object instanceof Map) {
         Map<?, ?> that = (Map<?, ?>) object;
         if (that.size() != 1) {
           return false;
         }
         Map.Entry<?, ?> entry = that.entrySet().iterator().next();
         return singleKey.equals(entry.getKey())
             && singleValue.equals(entry.getValue());
       }
       return false;
     }

     @Override public int hashCode() {
       return singleKey.hashCode() ^ singleValue.hashCode();
     }

     @Override public String toString() {
       return new StringBuilder()
           .append('{')
           .append(singleKey.toString())
           .append('=')
           .append(singleValue.toString())
           .append('}')
           .toString();
     }
   }

   private static final class RegularImmutableMap<K, V>
       extends ImmutableMap<K, V> {
     private transient final Entry<K, V>[] entries; // entries in insertion order
     private transient final Object[] table; // alternating keys and values
     // 'and' with an int then shift to get a table index
     private transient final int mask;
     private transient final int keySetHashCode;

     private RegularImmutableMap(Entry<?, ?>... entries) {
       // each of our 6 callers carefully put only Entry<K, V>s into the array!
       @SuppressWarnings("unchecked")
       Entry<K, V>[] tmp = (Entry<K, V>[]) entries;
       this.entries = tmp;

       int tableSize = Hashing.chooseTableSize(entries.length);
       table = new Object[tableSize * 2];
       mask = tableSize - 1;

       int keySetHashCodeMutable = 0;
       for (Entry<K, V> entry : this.entries) {
         K key = entry.getKey();
         int keyHashCode = key.hashCode();
         for (int i = Hashing.smear(keyHashCode); true; i++) {
           int index = (i & mask) * 2;
           Object existing = table[index];
           if (existing == null) {
             V value = entry.getValue();
             table[index] = key;
             table[index + 1] = value;
             keySetHashCodeMutable += keyHashCode;
             break;
           } else if (existing.equals(key)) {
             throw new IllegalArgumentException("duplicate key: " + key);
           }
         }
       }
       keySetHashCode = keySetHashCodeMutable;
     }

     @Override public V get(Object key) {
       if (key == null) {
         return null;
       }
       for (int i = Hashing.smear(key.hashCode()); true; i++) {
         int index = (i & mask) * 2;
         Object candidate = table[index];
         if (candidate == null) {
           return null;
         }
         if (candidate.equals(key)) {
           // we're careful to store only V's at odd indices
           @SuppressWarnings("unchecked")
           V value = (V) table[index + 1];
           return value;
         }
       }
     }

     public int size() {
       return entries.length;
     }

     public boolean isEmpty() {
       return false;
     }

     @Override public boolean containsKey(Object key) {
       return get(key) != null;
     }

     @Override public boolean containsValue(Object value) {
       if (value == null) {
         return false;
       }
       for (Entry<K, V> entry : entries) {
         if (entry.getValue().equals(value)) {
           return true;
         }
       }
       return false;
     }

     // TODO: Serialization of the map views should serialize the map, and
     // deserialization should call entrySet(), keySet(), or values() on the
     // deserialized map. The views are serializable since the Immutable* classes
     // are.

     private transient ImmutableSet<Entry<K, V>> entrySet;

     @Override public ImmutableSet<Entry<K, V>> entrySet() {
       ImmutableSet<Entry<K, V>> es = entrySet;
       return (es == null) ? (entrySet = new EntrySet<K, V>(this)) : es;
     }

     private static class EntrySet<K, V> extends ImmutableSet.ArrayImmutableSet<Entry<K, V>> {
       final RegularImmutableMap<K, V> map;

       EntrySet(RegularImmutableMap<K, V> map) {
         super(map.entries);
         this.map = map;
       }

       @Override public boolean contains(Object target) {
         if (target instanceof Entry) {
           Entry<?, ?> entry = (Entry<?, ?>) target;
           V mappedValue = map.get(entry.getKey());
           return mappedValue != null && mappedValue.equals(entry.getValue());
         }
         return false;
       }
     }

     private transient ImmutableSet<K> keySet;

     @Override public ImmutableSet<K> keySet() {
       ImmutableSet<K> ks = keySet;
       return (ks == null) ? (keySet = new KeySet<K, V>(this)) : ks;
     }

     private static class KeySet<K, V>
         extends ImmutableSet.TransformedImmutableSet<Entry<K, V>, K> {
       final RegularImmutableMap<K, V> map;

       KeySet(RegularImmutableMap<K, V> map) {
         super(map.entries, map.keySetHashCode);
         this.map = map;
       }

       @Override K transform(Entry<K, V> element) {
         return element.getKey();
       }

       @Override public boolean contains(Object target) {
         return map.containsKey(target);
       }
     }

     private transient ImmutableCollection<V> values;

     @Override public ImmutableCollection<V> values() {
       ImmutableCollection<V> v = values;
       return (v == null) ? (values = new Values<V>(this)) : v;
     }

     private static class Values<V> extends ImmutableCollection<V>  {
       final RegularImmutableMap<?, V> map;

       Values(RegularImmutableMap<?, V> map) {
         this.map = map;
       }

       public int size() {
         return map.entries.length;
       }

       @Override public boolean isEmpty() {
         return false;
       }

       @Override public UnmodifiableIterator<V> iterator() {
         Iterator<V> iterator = new AbstractIterator<V>() {
           int index = 0;
           @Override protected V computeNext() {
             return (index < map.entries.length)
                 ? map.entries[index++].getValue()
                 : endOfData();
           }
         };
         // Though the AbstractIterator is unmodifiable, it isn't an
         // UnmodifiableIterator.
         return Iterators.unmodifiableIterator(iterator);
       }

       @Override public boolean contains(Object target) {
         return map.containsValue(target);
       }
     }

     @Override public String toString() {
       StringBuilder result = new StringBuilder(size() * 16)
           .append('{')
           .append(entries[0]);
       for (int e = 1; e < entries.length; e++) {
         result.append(", ").append(entries[e].toString());
       }
       return result.append('}').toString();
     }
   }

   /*
    * Serialized type for all ImmutableMap instances. It captures the logical
    * contents and they are reconstructed using public factory methods. This
    * ensures that the implementation types remain as implementation details.
    */
   private static class SerializedForm implements Serializable {
     final Object[] keys;
     final Object[] values;
     SerializedForm(ImmutableMap<?, ?> map) {
       keys = new Object[map.size()];
       values = new Object[map.size()];
       int i = 0;
       for (Entry<?, ?> entry : map.entrySet()) {
         keys[i] = entry.getKey();
         values[i] = entry.getValue();
         i++;
       }
     }
     Object readResolve() {
       Builder<Object, Object> builder = new Builder<Object, Object>();
       for (int i = 0; i < keys.length; i++) {
         builder.put(keys[i], values[i]);
       }
       return builder.build();
     }
     private static final long serialVersionUID = 0;
   }

   Object writeReplace() {
     return new SerializedForm(this);
   }
 }
	/*
	* Copyright (C) 2008 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.google.inject.internal.util;

	import java.io.Serializable;
	import java.util.Collections;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.concurrent.ConcurrentMap;

	/**
	* An immutable, hash-based {@link Map} with reliable user-specified iteration
	* order. Does not permit null keys or values.
	*
	* <p>Unlike {@link Collections#unmodifiableMap}, which is a <i>view</i> of a
	* separate map which can still change, an instance of {@code ImmutableMap}
	* contains its own data and will <i>never</i> change. {@code ImmutableMap} is
	* convenient for {@code public static final} maps ("constant maps") and also
	* lets you easily make a "defensive copy" of a map provided to your class by a
	* caller.
	*
	* <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
	* it has no public or protected constructors. Thus, instances of this class are
	* guaranteed to be immutable.
	*
	* @see ImmutableList
	* @see ImmutableSet
	* @author Jesse Wilson
	* @author Kevin Bourrillion
	*/
	@SuppressWarnings("serial") // we're overriding default serialization
	public abstract class ImmutableMap<K, V>
	implements ConcurrentMap<K, V>, Serializable {
	private static final ImmutableMap<?, ?> EMPTY_IMMUTABLE_MAP
	= new EmptyImmutableMap();

	// TODO: restore prebuilder API? optimize, compare performance to HashMap

	/**
	* Returns the empty map. This map behaves and performs comparably to
	* {@link Collections#emptyMap}, and is preferable mainly for consistency
	* and maintainability of your code.
	*/
	// Casting to any type is safe because the set will never hold any elements.
	@SuppressWarnings("unchecked")
	public static <K, V> ImmutableMap<K, V> of() {
	return (ImmutableMap<K, V>) EMPTY_IMMUTABLE_MAP;
	}

	/**
	* Returns an immutable map containing a single entry. This map behaves and
	* performs comparably to {@link Collections#singletonMap} but will not accept
	* a null key or value. It is preferable mainly for consistency and
	* maintainability of your code.
	*/
	public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
	return new SingletonImmutableMap<K, V>(
	Preconditions.checkNotNull(k1), Preconditions.checkNotNull(v1));
	}

	/**
	* Returns an immutable map containing the given entries, in order.
	*
	* @throws IllegalArgumentException if duplicate keys are added
	*/
	public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
	return new RegularImmutableMap<K, V>(entryOf(k1, v1), entryOf(k2, v2));
	}

	/**
	* Returns an immutable map containing the given entries, in order.
	*
	* @throws IllegalArgumentException if duplicate keys are added
	*/
	public static <K, V> ImmutableMap<K, V> of(
	K k1, V v1, K k2, V v2, K k3, V v3) {
	return new RegularImmutableMap<K, V>(
	entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
	}

	/**
	* Returns an immutable map containing the given entries, in order.
	*
	* @throws IllegalArgumentException if duplicate keys are added
	*/
	public static <K, V> ImmutableMap<K, V> of(
	K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
	return new RegularImmutableMap<K, V>(
	entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
	}

	/**
	* Returns an immutable map containing the given entries, in order.
	*
	* @throws IllegalArgumentException if duplicate keys are added
	*/
	public static <K, V> ImmutableMap<K, V> of(
	K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
	return new RegularImmutableMap<K, V>(entryOf(k1, v1),
	entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
	}

	// looking for of() with > 5 entries? Use the builder instead.

	/**
	* Returns a new builder. The generated builder is equivalent to the builder
	* created by the {@link Builder} constructor.
	*/
	public static <K, V> Builder<K, V> builder() {
	return new Builder<K, V>();
	}

	/**
	* Verifies that {@code key} and {@code value} are non-null, and returns a new
	* entry with those values.
	*/
	private static <K, V> Entry<K, V> entryOf(K key, V value) {
	return Maps.immutableEntry(Preconditions.checkNotNull(key), Preconditions.checkNotNull(value));
	}

	/**
	* A builder for creating immutable map instances, especially {@code public
	* static final} maps ("constant maps"). Example: <pre> {@code
	*
	* static final ImmutableMap<String, Integer> WORD_TO_INT =
	* new ImmutableMap.Builder<String, Integer>()
	* .put("one", 1)
	* .put("two", 2)
	* .put("three", 3)
	* .build();}</pre>
	*
	* For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are
	* even more convenient.
	*
	* <p>Builder instances can be reused - it is safe to call {@link #build}
	* multiple times to build multiple maps in series. Each map is a superset of
	* the maps created before it.
	*/
	public static class Builder<K, V> {
	final List<Entry<K, V>> entries = Lists.newArrayList();

	/**
	* Creates a new builder. The returned builder is equivalent to the builder
	* generated by {@link ImmutableMap#builder}.
	*/
	public Builder() {}

	/**
	* Associates {@code key} with {@code value} in the built map. Duplicate
	* keys are not allowed, and will cause {@link #build} to fail.
	*/
	public Builder<K, V> put(K key, V value) {
	entries.add(entryOf(key, value));
	return this;
	}

	/**
	* Associates all of {@code map's} keys and values in the built map.
	* Duplicate keys are not allowed, and will cause {@link #build} to fail.
	*
	* @throws NullPointerException if any key or value in {@code map} is null
	*/
	public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
	for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
	put(entry.getKey(), entry.getValue());
	}
	return this;
	}

	// TODO: Should build() and the ImmutableBiMap version throw an
	// IllegalStateException instead?

	/**
	* Returns a newly-created immutable map.
	*
	* @throws IllegalArgumentException if duplicate keys were added
	*/
	public ImmutableMap<K, V> build() {
	return fromEntryList(entries);
	}

	private static <K, V> ImmutableMap<K, V> fromEntryList(
	List<Entry<K, V>> entries) {
	int size = entries.size();
	switch (size) {
	case 0:
	return of();
	case 1:
	return new SingletonImmutableMap<K, V>(Iterables.getOnlyElement(entries));
	default:
	Entry<?, ?>[] entryArray
	= entries.toArray(new Entry<?, ?>[entries.size()]);
	return new RegularImmutableMap<K, V>(entryArray);
	}
	}
	}

	/**
	* Returns an immutable map containing the same entries as {@code map}. If
	* {@code map} somehow contains entries with duplicate keys (for example, if
	* it is a {@code SortedMap} whose comparator is not <i>consistent with
	* equals</i>), the results of this method are undefined.
	*
	* <p><b>Note:</b> Despite what the method name suggests, if {@code map} is an
	* {@code ImmutableMap}, no copy will actually be performed, and the given map
	* itself will be returned.
	*
	* @throws NullPointerException if any key or value in {@code map} is null
	*/
	public static <K, V> ImmutableMap<K, V> copyOf(
	Map<? extends K, ? extends V> map) {
	if (map instanceof ImmutableMap) {
	@SuppressWarnings("unchecked") // safe since map is not writable
	ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
	return kvMap;
	}

	int size = map.size();
	switch (size) {
	case 0:
	return of();
	case 1:
	Map.Entry<? extends K, ? extends V> loneEntry
	= Iterables.getOnlyElement(map.entrySet());
	/*
	* Must cast next line to (K) and (V) to avoid returning an
	* ImmutableMap<? extends K, ? extends V>, which is incompatible
	* with the return type ImmutableMap<K, V>. (Eclipse will complain
	* mightily about this line if there's no cast.)
	*/
	return of((K) loneEntry.getKey(), (V) loneEntry.getValue());
	default:
	Entry<?, ?>[] array = new Entry<?, ?>[size];
	int i = 0;
	for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
	/*
	* See comment above re: <? extends K, ? extends V> to <K, V>.
	*/
	array[i++] = entryOf((K) entry.getKey(), (V) entry.getValue());
	}
	return new RegularImmutableMap<K, V>(array);
	}
	}

	ImmutableMap() {}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final V put(K k, V v) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final V remove(Object o) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final V putIfAbsent(K key, V value) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final boolean remove(Object key, Object value) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final boolean replace(K key, V oldValue, V newValue) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final V replace(K key, V value) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final void putAll(Map<? extends K, ? extends V> map) {
	throw new UnsupportedOperationException();
	}

	/**
	* Guaranteed to throw an exception and leave the map unmodified.
	*
	* @throws UnsupportedOperationException always
	*/
	public final void clear() {
	throw new UnsupportedOperationException();
	}

	// Overriding to mark it Nullable
	public abstract boolean containsKey(@Nullable Object key);

	// Overriding to mark it Nullable
	public abstract boolean containsValue(@Nullable Object value);

	// Overriding to mark it Nullable
	public abstract V get(@Nullable Object key);

	/**
	* Returns an immutable set of the mappings in this map. The entries are in
	* the same order as the parameters used to build this map.
	*/
	public abstract ImmutableSet<Entry<K, V>> entrySet();

	/**
	* Returns an immutable set of the keys in this map. These keys are in
	* the same order as the parameters used to build this map.
	*/
	public abstract ImmutableSet<K> keySet();

	/**
	* Returns an immutable collection of the values in this map. The values are
	* in the same order as the parameters used to build this map.
	*/
	public abstract ImmutableCollection<V> values();

	@Override public boolean equals(@Nullable Object object) {
	if (object == this) {
	return true;
	}
	if (object instanceof Map) {
	Map<?, ?> that = (Map<?, ?>) object;
	return this.entrySet().equals(that.entrySet());
	}
	return false;
	}

	@Override public int hashCode() {
	// not caching hash code since it could change if map values are mutable
	// in a way that modifies their hash codes
	return entrySet().hashCode();
	}

	@Override public String toString() {
	StringBuilder result = new StringBuilder(size() * 16).append('{');
	Iterator<Entry<K, V>> entries = entrySet().iterator();
	result.append(entries.next());
	while (entries.hasNext()) {
	result.append(", ").append(entries.next());
	}
	return result.append('}').toString();
	}

	private static final class EmptyImmutableMap
	extends ImmutableMap<Object, Object> {

	@Override public Object get(Object key) {
	return null;
	}

	public int size() {
	return 0;
	}

	public boolean isEmpty() {
	return true;
	}

	@Override public boolean containsKey(Object key) {
	return false;
	}

	@Override public boolean containsValue(Object value) {
	return false;
	}

	@Override public ImmutableSet<Entry<Object, Object>> entrySet() {
	return ImmutableSet.of();
	}

	@Override public ImmutableSet<Object> keySet() {
	return ImmutableSet.of();
	}

	@Override public ImmutableCollection<Object> values() {
	return ImmutableCollection.EMPTY_IMMUTABLE_COLLECTION;
	}

	@Override public boolean equals(@Nullable Object object) {
	if (object instanceof Map) {
	Map<?, ?> that = (Map<?, ?>) object;
	return that.isEmpty();
	}
	return false;
	}

	@Override public int hashCode() {
	return 0;
	}

	@Override public String toString() {
	return "{}";
	}
	}

	private static final class SingletonImmutableMap<K, V>
	extends ImmutableMap<K, V> {
	private transient final K singleKey;
	private transient final V singleValue;
	private transient Entry<K, V> entry;

	private SingletonImmutableMap(K singleKey, V singleValue) {
	this.singleKey = singleKey;
	this.singleValue = singleValue;
	}

	private SingletonImmutableMap(Entry<K, V> entry) {
	this.entry = entry;
	this.singleKey = entry.getKey();
	this.singleValue = entry.getValue();
	}

	private Entry<K, V> entry() {
	Entry<K, V> e = entry;
	return (e == null)
	? (entry = Maps.immutableEntry(singleKey, singleValue)) : e;
	}

	@Override public V get(Object key) {
	return singleKey.equals(key) ? singleValue : null;
	}

	public int size() {
	return 1;
	}

	public boolean isEmpty() {
	return false;
	}

	@Override public boolean containsKey(Object key) {
	return singleKey.equals(key);
	}

	@Override public boolean containsValue(Object value) {
	return singleValue.equals(value);
	}

	private transient ImmutableSet<Entry<K, V>> entrySet;

	@Override public ImmutableSet<Entry<K, V>> entrySet() {
	ImmutableSet<Entry<K, V>> es = entrySet;
	return (es == null) ? (entrySet = ImmutableSet.of(entry())) : es;
	}

	private transient ImmutableSet<K> keySet;

	@Override public ImmutableSet<K> keySet() {
	ImmutableSet<K> ks = keySet;
	return (ks == null) ? (keySet = ImmutableSet.of(singleKey)) : ks;
	}

	private transient ImmutableCollection<V> values;

	@Override public ImmutableCollection<V> values() {
	ImmutableCollection<V> v = values;
	return (v == null) ? (values = new Values<V>(singleValue)) : v;
	}

	private static class Values<V> extends ImmutableCollection<V> {
	final V singleValue;

	Values(V singleValue) {
	this.singleValue = singleValue;
	}

	@Override public boolean contains(Object object) {
	return singleValue.equals(object);
	}

	@Override public boolean isEmpty() {
	return false;
	}

	public int size() {
	return 1;
	}

	@Override public UnmodifiableIterator<V> iterator() {
	return Iterators.singletonIterator(singleValue);
	}
	}

	@Override public boolean equals(@Nullable Object object) {
	if (object == this) {
	return true;
	}
	if (object instanceof Map) {
	Map<?, ?> that = (Map<?, ?>) object;
	if (that.size() != 1) {
	return false;
	}
	Map.Entry<?, ?> entry = that.entrySet().iterator().next();
	return singleKey.equals(entry.getKey())
	&& singleValue.equals(entry.getValue());
	}
	return false;
	}

	@Override public int hashCode() {
	return singleKey.hashCode() ^ singleValue.hashCode();
	}

	@Override public String toString() {
	return new StringBuilder()
	.append('{')
	.append(singleKey.toString())
	.append('=')
	.append(singleValue.toString())
	.append('}')
	.toString();
	}
	}

	private static final class RegularImmutableMap<K, V>
	extends ImmutableMap<K, V> {
	private transient final Entry<K, V>[] entries; // entries in insertion order
	private transient final Object[] table; // alternating keys and values
	// 'and' with an int then shift to get a table index
	private transient final int mask;
	private transient final int keySetHashCode;

	private RegularImmutableMap(Entry<?, ?>... entries) {
	// each of our 6 callers carefully put only Entry<K, V>s into the array!
	@SuppressWarnings("unchecked")
	Entry<K, V>[] tmp = (Entry<K, V>[]) entries;
	this.entries = tmp;

	int tableSize = Hashing.chooseTableSize(entries.length);
	table = new Object[tableSize * 2];
	mask = tableSize - 1;

	int keySetHashCodeMutable = 0;
	for (Entry<K, V> entry : this.entries) {
	K key = entry.getKey();
	int keyHashCode = key.hashCode();
	for (int i = Hashing.smear(keyHashCode); true; i++) {
	int index = (i & mask) * 2;
	Object existing = table[index];
	if (existing == null) {
	V value = entry.getValue();
	table[index] = key;
	table[index + 1] = value;
	keySetHashCodeMutable += keyHashCode;
	break;
	} else if (existing.equals(key)) {
	throw new IllegalArgumentException("duplicate key: " + key);
	}
	}
	}
	keySetHashCode = keySetHashCodeMutable;
	}

	@Override public V get(Object key) {
	if (key == null) {
	return null;
	}
	for (int i = Hashing.smear(key.hashCode()); true; i++) {
	int index = (i & mask) * 2;
	Object candidate = table[index];
	if (candidate == null) {
	return null;
	}
	if (candidate.equals(key)) {
	// we're careful to store only V's at odd indices
	@SuppressWarnings("unchecked")
	V value = (V) table[index + 1];
	return value;
	}
	}
	}

	public int size() {
	return entries.length;
	}

	public boolean isEmpty() {
	return false;
	}

	@Override public boolean containsKey(Object key) {
	return get(key) != null;
	}

	@Override public boolean containsValue(Object value) {
	if (value == null) {
	return false;
	}
	for (Entry<K, V> entry : entries) {
	if (entry.getValue().equals(value)) {
	return true;
	}
	}
	return false;
	}

	// TODO: Serialization of the map views should serialize the map, and
	// deserialization should call entrySet(), keySet(), or values() on the
	// deserialized map. The views are serializable since the Immutable* classes
	// are.

	private transient ImmutableSet<Entry<K, V>> entrySet;

	@Override public ImmutableSet<Entry<K, V>> entrySet() {
	ImmutableSet<Entry<K, V>> es = entrySet;
	return (es == null) ? (entrySet = new EntrySet<K, V>(this)) : es;
	}

	private static class EntrySet<K, V> extends ImmutableSet.ArrayImmutableSet<Entry<K, V>> {
	final RegularImmutableMap<K, V> map;

	EntrySet(RegularImmutableMap<K, V> map) {
	super(map.entries);
	this.map = map;
	}

	@Override public boolean contains(Object target) {
	if (target instanceof Entry) {
	Entry<?, ?> entry = (Entry<?, ?>) target;
	V mappedValue = map.get(entry.getKey());
	return mappedValue != null && mappedValue.equals(entry.getValue());
	}
	return false;
	}
	}

	private transient ImmutableSet<K> keySet;

	@Override public ImmutableSet<K> keySet() {
	ImmutableSet<K> ks = keySet;
	return (ks == null) ? (keySet = new KeySet<K, V>(this)) : ks;
	}

	private static class KeySet<K, V>
	extends ImmutableSet.TransformedImmutableSet<Entry<K, V>, K> {
	final RegularImmutableMap<K, V> map;

	KeySet(RegularImmutableMap<K, V> map) {
	super(map.entries, map.keySetHashCode);
	this.map = map;
	}

	@Override K transform(Entry<K, V> element) {
	return element.getKey();
	}

	@Override public boolean contains(Object target) {
	return map.containsKey(target);
	}
	}

	private transient ImmutableCollection<V> values;

	@Override public ImmutableCollection<V> values() {
	ImmutableCollection<V> v = values;
	return (v == null) ? (values = new Values<V>(this)) : v;
	}

	private static class Values<V> extends ImmutableCollection<V> {
	final RegularImmutableMap<?, V> map;

	Values(RegularImmutableMap<?, V> map) {
	this.map = map;
	}

	public int size() {
	return map.entries.length;
	}

	@Override public boolean isEmpty() {
	return false;
	}

	@Override public UnmodifiableIterator<V> iterator() {
	Iterator<V> iterator = new AbstractIterator<V>() {
	int index = 0;
	@Override protected V computeNext() {
	return (index < map.entries.length)
	? map.entries[index++].getValue()
	: endOfData();
	}
	};
	// Though the AbstractIterator is unmodifiable, it isn't an
	// UnmodifiableIterator.
	return Iterators.unmodifiableIterator(iterator);
	}

	@Override public boolean contains(Object target) {
	return map.containsValue(target);
	}
	}

	@Override public String toString() {
	StringBuilder result = new StringBuilder(size() * 16)
	.append('{')
	.append(entries[0]);
	for (int e = 1; e < entries.length; e++) {
	result.append(", ").append(entries[e].toString());
	}
	return result.append('}').toString();
	}
	}

	/*
	* Serialized type for all ImmutableMap instances. It captures the logical
	* contents and they are reconstructed using public factory methods. This
	* ensures that the implementation types remain as implementation details.
	*/
	private static class SerializedForm implements Serializable {
	final Object[] keys;
	final Object[] values;
	SerializedForm(ImmutableMap<?, ?> map) {
	keys = new Object[map.size()];
	values = new Object[map.size()];
	int i = 0;
	for (Entry<?, ?> entry : map.entrySet()) {
	keys[i] = entry.getKey();
	values[i] = entry.getValue();
	i++;
	}
	}
	Object readResolve() {
	Builder<Object, Object> builder = new Builder<Object, Object>();
	for (int i = 0; i < keys.length; i++) {
	builder.put(keys[i], values[i]);
	}
	return builder.build();
	}
	private static final long serialVersionUID = 0;
	}

	Object writeReplace() {
	return new SerializedForm(this);
	}
	}