/*
 * 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.common.collect;

import com.google.common.base.Nullable;
import static com.google.common.base.Preconditions.checkNotNull;
import com.google.common.collect.ImmutableSet.ArrayImmutableSet;
import com.google.common.collect.ImmutableSet.TransformedImmutableSet;
import static com.google.common.collect.Iterables.getOnlyElement;

import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
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>(
        checkNotNull(k1), checkNotNull(v1));
  }

  /**
   * Returns an immutable map containing the given entries, in order.
   */
  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.
   */
  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.
   */
  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.
   */
  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.
   */
  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(checkNotNull(key), checkNotNull(value));
  }

  /**
   * A builder for creating immutable map instances, especially {@code public
   * static final} maps ("constant maps"). Code such as
   *
   * <pre>
   *   static final Map&lt;String, Integer&gt; ENGLISH_TO_INTEGER_MAP
   *       = createNumbersMap();
   *
   *   static Map&lt;String, Integer&gt; createNumbersMap() {
   *     Map&lt;String, Integer&gt; map = Maps.newHashMap();
   *     map.put("one", 1);
   *     map.put("two", 2);
   *     map.put("three", 3);
   *     return Collections.unmodifiableMap(map);
   *   }
   * </pre>
   * ... can be rewritten as ...
   * <pre>
   *   static final ImmutableMap&lt;String, Integer&gt; ENGLISH_TO_INTEGER_MAP
   *       = new ImmutableMap.Builder&lt;String, Integer&gt;()
   *           .put("one", 1)
   *           .put("two", 2)
   *           .put("three", 3)
   *           .build();
   * </pre>
   *
   * For <i>small</i> immutable maps, the {@link ImmutableMap#of()} methods are
   * even more convienient.
   *
   * <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 final class Builder<K, V> {
    final List<Entry<K, V>> entries = Lists.newArrayList();

    /**
     * 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;
    }

    /**
     * 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>(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.
   *
   * @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
            = 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);
    }
  }

  private 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();

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

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

    public int size() {
      return 0;
    }

    public boolean isEmpty() {
      return true;
    }

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

    @Override public boolean containsValue(@Nullable 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(Object object) {
      return object == this
          || (object instanceof Map<?, ?> && ((Map<?, ?>) object).isEmpty());
    }

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

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

  private static final class SingletonImmutableMap<K, V>
      extends ImmutableMap<K, V> {
    private final K key;
    private final V value;
    private Entry<K, V> entry;

    private SingletonImmutableMap(K key, V value) {
      this.key = key;
      this.value = value;
    }

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

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

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

    public int size() {
      return 1;
    }

    public boolean isEmpty() {
      return false;
    }

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

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

    private 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 ImmutableSet<K> keySet;

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

    private ImmutableCollection<V> values;

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

    private ImmutableCollection<V> createValues() {
      return new ImmutableCollection<V>() {
        @Override public boolean contains(@Nullable Object object) {
          return value.equals(object);
        }

        public boolean isEmpty() {
          return false;
        }

        public int size() {
          return 1;
        }

        public Iterator<V> iterator() {
          return Iterators.singletonIterator(value);
        }
      };
    }

    @Override public boolean equals(Object object) {
      if (object == this) {
        return true;
      }
      if (object instanceof Map<?, ?>) {
        Map<?, ?> map = (Map<?, ?>) object;
        return map.size() == 1 && map.entrySet().contains(entry());
      }
      return false;
    }

    @Override public int hashCode() {
      return key.hashCode() ^ value.hashCode();
    }

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

  private static final class RegularImmutableMap<K, V>
      extends ImmutableMap<K, V> {
    private final Entry<K, V>[] entries; // entries in insertion order
    private final Object[] table; // alternating keys and values
    private final int mask; // 'and' with an int then shift to get a table index
    private final int entrySetHashCode;
    private 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 entrySetHashCodeMutable = 0;
      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();
            int valueHashCode = value.hashCode();
            table[index] = key;
            table[index + 1] = value;
            entrySetHashCodeMutable += (keyHashCode ^ valueHashCode);
            keySetHashCodeMutable += keyHashCode;
            break;
          } else if (existing.equals(key)) {
            throw new IllegalArgumentException("duplicate key: " + key);
          }
        }
      }
      entrySetHashCode = entrySetHashCodeMutable;
      keySetHashCode = keySetHashCodeMutable;
    }

    @Override public V get(@Nullable 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(@Nullable Object key) {
      return get(key) != null;
    }

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

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

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

    private ImmutableSet<Entry<K, V>> createEntrySet() {
      return new ArrayImmutableSet<Entry<K, V>>(entries, entrySetHashCode) {
        @Override public boolean contains(@Nullable Object target) {
          if (target instanceof Entry<?, ?>) {
            Entry<?, ?> entry = (Entry<?, ?>) target;
            V mappedValue = get(entry.getKey());
            return mappedValue != null && mappedValue.equals(entry.getValue());
          }
          return false;
        }
      };
    }

    private ImmutableSet<K> keySet;

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

    private ImmutableSet<K> createKeySet() {
      return new TransformedImmutableSet<Map.Entry<K, V>, K>(
          entries, keySetHashCode) {
        @Override K transform(Entry<K, V> element) {
          return element.getKey();
        }

        @Override public boolean contains(@Nullable Object target) {
          return RegularImmutableMap.this.containsKey(target);
        }
      };
    }

    private ImmutableCollection<V> values;

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

    private ImmutableCollection<V> createValues() {
      return new ImmutableCollection<V>() {
        public int size() {
          return entries.length;
        }

        public boolean isEmpty() {
          return false;
        }

        public Iterator<V> iterator() {
          return new AbstractIterator<V>() {
            int index = 0;
            @Override protected V computeNext() {
              return (index < entries.length)
                  ? entries[index++].getValue()
                  : endOfData();
            }
          };
        }

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

    @Override public boolean equals(Object object) {
      if (object == this) {
        return true;
      }
      if (object instanceof ImmutableMap<?, ?>
          && object.hashCode() != hashCode()) {
        return false;
      }
      if (object instanceof Map<?, ?>) {
        Map<?, ?> map = (Map<?, ?>) object;
        return entrySet().equals(map.entrySet());
      }
      return false;
    }

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

    @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;
  }

  private void readObject(ObjectInputStream stream)
      throws InvalidObjectException {
    throw new InvalidObjectException("Use SerializedForm");
  }

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