/*
 * Copyright (C) 2009 The Guava Authors
 *
 * 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 static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
import static com.google.common.collect.Maps.keyOrNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.WeakOuter;
import java.util.AbstractMap;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.NavigableMap;
import java.util.SortedMap;
import java.util.Spliterator;
import java.util.TreeMap;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collector;
import java.util.stream.Collectors;
import org.checkerframework.checker.nullness.qual.Nullable;

A NavigableMap whose contents will never change, with many other important properties detailed at ImmutableCollection. 
Warning: as with any sorted collection, you are strongly advised not to use a Comparator or Comparable type whose comparison behavior is inconsistent with
equals. That is, a.compareTo(b) or comparator.compare(a, b) should equal zero if and only if a.equals(b). If this advice is not followed, the resulting map will not correctly obey its specification. 
See the Guava User Guide article on  immutable collections.
Author:
Jared Levy, Louis Wasserman
Since:
2.0 (implements NavigableMap since 12.0)/**
 * A {@link NavigableMap} whose contents will never change, with many other important properties
 * detailed at {@link ImmutableCollection}.
 *
 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will
 * not correctly obey its specification.
 *
 * <p>See the Guava User Guide article on <a href=
 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
 *
 * @author Jared Levy
 * @author Louis Wasserman
 * @since 2.0 (implements {@code NavigableMap} since 12.0)
 */
@GwtCompatible(serializable = true, emulated = true)
public final class ImmutableSortedMap<K, V> extends ImmutableSortedMapFauxverideShim<K, V>
    implements NavigableMap<K, V> {
  
Returns a Collector that accumulates elements into an ImmutableSortedMap whose keys and values are the result of applying the provided mapping functions to the input elements. The generated map is sorted by the specified comparator. 
If the mapped keys contain duplicates (according to the specified comparator), an 
IllegalArgumentException is thrown when the collection operation is performed. (This differs from the Collector returned by Collectors.toMap(Function<? super Object,? extends Object>, Function<? super Object,? extends Object>), which throws an IllegalStateException.) 
Since:
21.0/**
   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
   * keys and values are the result of applying the provided mapping functions to the input
   * elements. The generated map is sorted by the specified comparator.
   *
   * <p>If the mapped keys contain duplicates (according to the specified comparator), an {@code
   * IllegalArgumentException} is thrown when the collection operation is performed. (This differs
   * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which
   * throws an {@code IllegalStateException}.)
   *
   * @since 21.0
   */
  @Beta
  public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
      Comparator<? super K> comparator,
      Function<? super T, ? extends K> keyFunction,
      Function<? super T, ? extends V> valueFunction) {
    return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction);
  }

  
Returns a Collector that accumulates elements into an ImmutableSortedMap whose keys and values are the result of applying the provided mapping functions to the input elements. 
If the mapped keys contain duplicates (according to the comparator), the the values are
merged using the specified merging function. Entries will appear in the encounter order of the
first occurrence of the key.
Since:
21.0/**
   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
   * keys and values are the result of applying the provided mapping functions to the input
   * elements.
   *
   * <p>If the mapped keys contain duplicates (according to the comparator), the the values are
   * merged using the specified merging function. Entries will appear in the encounter order of the
   * first occurrence of the key.
   *
   * @since 21.0
   */
  @Beta
  public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
      Comparator<? super K> comparator,
      Function<? super T, ? extends K> keyFunction,
      Function<? super T, ? extends V> valueFunction,
      BinaryOperator<V> mergeFunction) {
    checkNotNull(comparator);
    checkNotNull(keyFunction);
    checkNotNull(valueFunction);
    checkNotNull(mergeFunction);
    return Collectors.collectingAndThen(
        Collectors.toMap(
            keyFunction, valueFunction, mergeFunction, () -> new TreeMap<K, V>(comparator)),
        ImmutableSortedMap::copyOfSorted);
  }

  /*
   * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and
   * uses less memory than TreeMap; then say so in the class Javadoc.
   */
  private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural();

  private static final ImmutableSortedMap<Comparable, Object> NATURAL_EMPTY_MAP =
      new ImmutableSortedMap<>(
          ImmutableSortedSet.emptySet(Ordering.natural()), ImmutableList.<Object>of());

  static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) {
    if (Ordering.natural().equals(comparator)) {
      return of();
    } else {
      return new ImmutableSortedMap<>(
          ImmutableSortedSet.emptySet(comparator), ImmutableList.<V>of());
    }
  }

  
Returns the empty sorted map. /** Returns the empty sorted map. */
  @SuppressWarnings("unchecked")
  // unsafe, comparator() returns a comparator on the specified type
  // TODO(kevinb): evaluate whether or not of().comparator() should return null
  public static <K, V> ImmutableSortedMap<K, V> of() {
    return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP;
  }

  
Returns an immutable map containing a single entry. /** Returns an immutable map containing a single entry. */
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1) {
    return of(Ordering.natural(), k1, v1);
  }

  
Returns an immutable map containing a single entry. /** Returns an immutable map containing a single entry. */
  private static <K, V> ImmutableSortedMap<K, V> of(Comparator<? super K> comparator, K k1, V v1) {
    return new ImmutableSortedMap<>(
        new RegularImmutableSortedSet<K>(ImmutableList.of(k1), checkNotNull(comparator)),
        ImmutableList.of(v1));
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
their keys.
Throws:
IllegalArgumentException – if the two keys are equal according to their natural ordering/**
   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
   * their keys.
   *
   * @throws IllegalArgumentException if the two keys are equal according to their natural ordering
   */
  @SuppressWarnings("unchecked")
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
      K k1, V v1, K k2, V v2) {
    return ofEntries(entryOf(k1, v1), entryOf(k2, v2));
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
their keys.
Throws:
IllegalArgumentException – if any two keys are equal according to their natural ordering/**
   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
   * their keys.
   *
   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
   */
  @SuppressWarnings("unchecked")
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
      K k1, V v1, K k2, V v2, K k3, V v3) {
    return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
their keys.
Throws:
IllegalArgumentException – if any two keys are equal according to their natural ordering/**
   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
   * their keys.
   *
   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
   */
  @SuppressWarnings("unchecked")
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
    return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
their keys.
Throws:
IllegalArgumentException – if any two keys are equal according to their natural ordering/**
   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
   * their keys.
   *
   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
   */
  @SuppressWarnings("unchecked")
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
    return ofEntries(
        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
  }

  private static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> ofEntries(
      Entry<K, V>... entries) {
    return fromEntries(Ordering.natural(), false, entries, entries.length);
  }

  
Returns an immutable map containing the same entries as map, sorted by the natural ordering of the keys. 
Despite the method name, this method attempts to avoid actually copying the data when it is
safe to do so. The exact circumstances under which a copy will or will not be performed are
undocumented and subject to change.
This method is not type-safe, as it may be called on a map with keys that are not mutually
comparable.
Throws:
ClassCastException – if the keys in map are not mutually comparable
NullPointerException – if any key or value in map is null
IllegalArgumentException – if any two keys are equal according to their natural ordering/**
   * Returns an immutable map containing the same entries as {@code map}, sorted by the natural
   * ordering of the keys.
   *
   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
   * safe to do so. The exact circumstances under which a copy will or will not be performed are
   * undocumented and subject to change.
   *
   * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually
   * comparable.
   *
   * @throws ClassCastException if the keys in {@code map} are not mutually comparable
   * @throws NullPointerException if any key or value in {@code map} is null
   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
   */
  public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
    // Hack around K not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
    return copyOfInternal(map, naturalOrder);
  }

  
Returns an immutable map containing the same entries as map, with keys sorted by the provided comparator. 
Despite the method name, this method attempts to avoid actually copying the data when it is
safe to do so. The exact circumstances under which a copy will or will not be performed are
undocumented and subject to change.
Throws:
NullPointerException – if any key or value in map is null
IllegalArgumentException – if any two keys are equal according to the comparator/**
   * Returns an immutable map containing the same entries as {@code map}, with keys sorted by the
   * provided comparator.
   *
   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
   * safe to do so. The exact circumstances under which a copy will or will not be performed are
   * undocumented and subject to change.
   *
   * @throws NullPointerException if any key or value in {@code map} is null
   * @throws IllegalArgumentException if any two keys are equal according to the comparator
   */
  public static <K, V> ImmutableSortedMap<K, V> copyOf(
      Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
    return copyOfInternal(map, checkNotNull(comparator));
  }

  
Returns an immutable map containing the given entries, with keys sorted by the provided
comparator.
This method is not type-safe, as it may be called on a map with keys that are not mutually
comparable.
Throws:
NullPointerException – if any key or value in map is null
IllegalArgumentException – if any two keys are equal according to the comparator
Since:
19.0/**
   * Returns an immutable map containing the given entries, with keys sorted by the provided
   * comparator.
   *
   * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually
   * comparable.
   *
   * @throws NullPointerException if any key or value in {@code map} is null
   * @throws IllegalArgumentException if any two keys are equal according to the comparator
   * @since 19.0
   */
  @Beta
  public static <K, V> ImmutableSortedMap<K, V> copyOf(
      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
    // Hack around K not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
    return copyOf(entries, naturalOrder);
  }

  
Returns an immutable map containing the given entries, with keys sorted by the provided
comparator.
Throws:
NullPointerException – if any key or value in map is null
IllegalArgumentException – if any two keys are equal according to the comparator
Since:
19.0/**
   * Returns an immutable map containing the given entries, with keys sorted by the provided
   * comparator.
   *
   * @throws NullPointerException if any key or value in {@code map} is null
   * @throws IllegalArgumentException if any two keys are equal according to the comparator
   * @since 19.0
   */
  @Beta
  public static <K, V> ImmutableSortedMap<K, V> copyOf(
      Iterable<? extends Entry<? extends K, ? extends V>> entries,
      Comparator<? super K> comparator) {
    return fromEntries(checkNotNull(comparator), false, entries);
  }

  
Returns an immutable map containing the same entries as the provided sorted map, with the same
ordering.
Despite the method name, this method attempts to avoid actually copying the data when it is
safe to do so. The exact circumstances under which a copy will or will not be performed are
undocumented and subject to change.
Throws:
NullPointerException – if any key or value in map is null/**
   * Returns an immutable map containing the same entries as the provided sorted map, with the same
   * ordering.
   *
   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
   * safe to do so. The exact circumstances under which a copy will or will not be performed are
   * undocumented and subject to change.
   *
   * @throws NullPointerException if any key or value in {@code map} is null
   */
  @SuppressWarnings("unchecked")
  public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(SortedMap<K, ? extends V> map) {
    Comparator<? super K> comparator = map.comparator();
    if (comparator == null) {
      // If map has a null comparator, the keys should have a natural ordering,
      // even though K doesn't explicitly implement Comparable.
      comparator = (Comparator<? super K>) NATURAL_ORDER;
    }
    if (map instanceof ImmutableSortedMap) {
      // TODO(kevinb): Prove that this cast is safe, even though
      // Collections.unmodifiableSortedMap requires the same key type.
      @SuppressWarnings("unchecked")
      ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
      if (!kvMap.isPartialView()) {
        return kvMap;
      }
    }
    return fromEntries(comparator, true, map.entrySet());
  }

  private static <K, V> ImmutableSortedMap<K, V> copyOfInternal(
      Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
    boolean sameComparator = false;
    if (map instanceof SortedMap) {
      SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map;
      Comparator<?> comparator2 = sortedMap.comparator();
      sameComparator =
          (comparator2 == null) ? comparator == NATURAL_ORDER : comparator.equals(comparator2);
    }

    if (sameComparator && (map instanceof ImmutableSortedMap)) {
      // TODO(kevinb): Prove that this cast is safe, even though
      // Collections.unmodifiableSortedMap requires the same key type.
      @SuppressWarnings("unchecked")
      ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
      if (!kvMap.isPartialView()) {
        return kvMap;
      }
    }
    return fromEntries(comparator, sameComparator, map.entrySet());
  }

  
Accepts a collection of possibly-null entries. If sameComparator, then it is assumed that they do not need to be sorted or checked for dupes. /**
   * Accepts a collection of possibly-null entries. If {@code sameComparator}, then it is assumed
   * that they do not need to be sorted or checked for dupes.
   */
  private static <K, V> ImmutableSortedMap<K, V> fromEntries(
      Comparator<? super K> comparator,
      boolean sameComparator,
      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
    // "adding" type params to an array of a raw type should be safe as
    // long as no one can ever cast that same array instance back to a
    // raw type.
    @SuppressWarnings("unchecked")
    Entry<K, V>[] entryArray = (Entry[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
    return fromEntries(comparator, sameComparator, entryArray, entryArray.length);
  }

  private static <K, V> ImmutableSortedMap<K, V> fromEntries(
      final Comparator<? super K> comparator,
      boolean sameComparator,
      Entry<K, V>[] entryArray,
      int size) {
    switch (size) {
      case 0:
        return emptyMap(comparator);
      case 1:
        return ImmutableSortedMap.<K, V>of(
            comparator, entryArray[0].getKey(), entryArray[0].getValue());
      default:
        Object[] keys = new Object[size];
        Object[] values = new Object[size];
        if (sameComparator) {
          // Need to check for nulls, but don't need to sort or validate.
          for (int i = 0; i < size; i++) {
            Object key = entryArray[i].getKey();
            Object value = entryArray[i].getValue();
            checkEntryNotNull(key, value);
            keys[i] = key;
            values[i] = value;
          }
        } else {
          // Need to sort and check for nulls and dupes.
          // Inline the Comparator implementation rather than transforming with a Function
          // to save code size.
          Arrays.sort(
              entryArray,
              0,
              size,
              new Comparator<Entry<K, V>>() {
                @Override
                public int compare(Entry<K, V> e1, Entry<K, V> e2) {
                  return comparator.compare(e1.getKey(), e2.getKey());
                }
              });
          K prevKey = entryArray[0].getKey();
          keys[0] = prevKey;
          values[0] = entryArray[0].getValue();
          checkEntryNotNull(keys[0], values[0]);
          for (int i = 1; i < size; i++) {
            K key = entryArray[i].getKey();
            V value = entryArray[i].getValue();
            checkEntryNotNull(key, value);
            keys[i] = key;
            values[i] = value;
            checkNoConflict(
                comparator.compare(prevKey, key) != 0, "key", entryArray[i - 1], entryArray[i]);
            prevKey = key;
          }
        }
        return new ImmutableSortedMap<>(
            new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator),
            new RegularImmutableList<V>(values));
    }
  }

  
Returns a builder that creates immutable sorted maps whose keys are ordered by their natural ordering. The sorted maps use Ordering.natural() as the comparator. /**
   * Returns a builder that creates immutable sorted maps whose keys are ordered by their natural
   * ordering. The sorted maps use {@link Ordering#natural()} as the comparator.
   */
  public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() {
    return new Builder<>(Ordering.natural());
  }

  
Returns a builder that creates immutable sorted maps with an explicit comparator. If the comparator has a more general type than the map's keys, such as creating a 
SortedMap<Integer, String> with a Comparator<Number>, use the Builder constructor instead. 
Throws:
NullPointerException – if comparator is null/**
   * Returns a builder that creates immutable sorted maps with an explicit comparator. If the
   * comparator has a more general type than the map's keys, such as creating a {@code
   * SortedMap<Integer, String>} with a {@code Comparator<Number>}, use the {@link Builder}
   * constructor instead.
   *
   * @throws NullPointerException if {@code comparator} is null
   */
  public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) {
    return new Builder<>(comparator);
  }

  
Returns a builder that creates immutable sorted maps whose keys are ordered by the reverse of
their natural ordering.
/**
   * Returns a builder that creates immutable sorted maps whose keys are ordered by the reverse of
   * their natural ordering.
   */
  public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() {
    return new Builder<>(Ordering.natural().reverse());
  }

  
A builder for creating immutable sorted map instances, especially public static final maps ("constant maps"). Example: 

static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
    new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
        .put(1, "one")
        .put(2, "two")
        .put(3, "three")
        .build();

For small immutable sorted maps, the ImmutableSortedMap.of() methods are even more convenient. 
Builder instances can be reused - it is safe to call build multiple times to build multiple maps in series. Each map is a superset of the maps created before it. 
Since:
2.0/**
   * A builder for creating immutable sorted map instances, especially {@code public static final}
   * maps ("constant maps"). Example:
   *
   * <pre>{@code
   * static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
   *     new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
   *         .put(1, "one")
   *         .put(2, "two")
   *         .put(3, "three")
   *         .build();
   * }</pre>
   *
   * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.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.
   *
   * @since 2.0
   */
  public static class Builder<K, V> extends ImmutableMap.Builder<K, V> {
    private final Comparator<? super K> comparator;

    
Creates a new builder. The returned builder is equivalent to the builder generated by ImmutableSortedMap.orderedBy. /**
     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
     * ImmutableSortedMap#orderedBy}.
     */
    @SuppressWarnings("unchecked")
    public Builder(Comparator<? super K> comparator) {
      this.comparator = checkNotNull(comparator);
    }

    
Associates key with value in the built map. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail. /**
     * Associates {@code key} with {@code value} in the built map. Duplicate keys, according to the
     * comparator (which might be the keys' natural order), are not allowed, and will cause {@link
     * #build} to fail.
     */
    @CanIgnoreReturnValue
    @Override
    public Builder<K, V> put(K key, V value) {
      super.put(key, value);
      return this;
    }

    
Adds the given entry to the map, making it immutable if necessary. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail. 
Since:
11.0/**
     * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys,
     * according to the comparator (which might be the keys' natural order), are not allowed, and
     * will cause {@link #build} to fail.
     *
     * @since 11.0
     */
    @CanIgnoreReturnValue
    @Override
    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
      super.put(entry);
      return this;
    }

    
Associates all of the given map's keys and values in the built map. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail. 
Throws:
NullPointerException – if any key or value in map is null/**
     * Associates all of the given map's keys and values in the built map. Duplicate keys, according
     * to the comparator (which might be the keys' natural order), are not allowed, and will cause
     * {@link #build} to fail.
     *
     * @throws NullPointerException if any key or value in {@code map} is null
     */
    @CanIgnoreReturnValue
    @Override
    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
      super.putAll(map);
      return this;
    }

    
Adds all the given entries to the built map. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail. 
Throws:
NullPointerException – if any key, value, or entry is null
Since:
19.0/**
     * Adds all the given entries to the built map. Duplicate keys, according to the comparator
     * (which might be the keys' natural order), are not allowed, and will cause {@link #build} to
     * fail.
     *
     * @throws NullPointerException if any key, value, or entry is null
     * @since 19.0
     */
    @CanIgnoreReturnValue
    @Beta
    @Override
    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
      super.putAll(entries);
      return this;
    }

    
Throws an UnsupportedOperationException. 
Since:
19.0
Deprecated:
Unsupported by ImmutableSortedMap.Builder./**
     * Throws an {@code UnsupportedOperationException}.
     *
     * @since 19.0
     * @deprecated Unsupported by ImmutableSortedMap.Builder.
     */
    @CanIgnoreReturnValue
    @Beta
    @Override
    @Deprecated
    public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
      throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder");
    }

    @Override
    Builder<K, V> combine(ImmutableMap.Builder<K, V> other) {
      super.combine(other);
      return this;
    }

    
Returns a newly-created immutable sorted map.
Throws:
IllegalArgumentException – if any two keys are equal according to the comparator (which
    might be the keys' natural order)/**
     * Returns a newly-created immutable sorted map.
     *
     * @throws IllegalArgumentException if any two keys are equal according to the comparator (which
     *     might be the keys' natural order)
     */
    @Override
    public ImmutableSortedMap<K, V> build() {
      switch (size) {
        case 0:
          return emptyMap(comparator);
        case 1:
          return of(comparator, entries[0].getKey(), entries[0].getValue());
        default:
          return fromEntries(comparator, false, entries, size);
      }
    }
  }

  private final transient RegularImmutableSortedSet<K> keySet;
  private final transient ImmutableList<V> valueList;
  private transient ImmutableSortedMap<K, V> descendingMap;

  ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) {
    this(keySet, valueList, null);
  }

  ImmutableSortedMap(
      RegularImmutableSortedSet<K> keySet,
      ImmutableList<V> valueList,
      ImmutableSortedMap<K, V> descendingMap) {
    this.keySet = keySet;
    this.valueList = valueList;
    this.descendingMap = descendingMap;
  }

  @Override
  public int size() {
    return valueList.size();
  }

  @Override
  public void forEach(BiConsumer<? super K, ? super V> action) {
    checkNotNull(action);
    ImmutableList<K> keyList = keySet.asList();
    for (int i = 0; i < size(); i++) {
      action.accept(keyList.get(i), valueList.get(i));
    }
  }

  @Override
  public V get(@Nullable Object key) {
    int index = keySet.indexOf(key);
    return (index == -1) ? null : valueList.get(index);
  }

  @Override
  boolean isPartialView() {
    return keySet.isPartialView() || valueList.isPartialView();
  }

  
Returns an immutable set of the mappings in this map, sorted by the key ordering. /** Returns an immutable set of the mappings in this map, sorted by the key ordering. */
  @Override
  public ImmutableSet<Entry<K, V>> entrySet() {
    return super.entrySet();
  }

  @Override
  ImmutableSet<Entry<K, V>> createEntrySet() {
    @WeakOuter
    class EntrySet extends ImmutableMapEntrySet<K, V> {
      @Override
      public UnmodifiableIterator<Entry<K, V>> iterator() {
        return asList().iterator();
      }

      @Override
      public Spliterator<Entry<K, V>> spliterator() {
        return asList().spliterator();
      }

      @Override
      public void forEach(Consumer<? super Entry<K, V>> action) {
        asList().forEach(action);
      }

      @Override
      ImmutableList<Entry<K, V>> createAsList() {
        return new ImmutableAsList<Entry<K, V>>() {
          @Override
          public Entry<K, V> get(int index) {
            return new AbstractMap.SimpleImmutableEntry<>(
                keySet.asList().get(index), valueList.get(index));
          }

          @Override
          public Spliterator<Entry<K, V>> spliterator() {
            return CollectSpliterators.indexed(
                size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get);
          }

          @Override
          ImmutableCollection<Entry<K, V>> delegateCollection() {
            return EntrySet.this;
          }
        };
      }

      @Override
      ImmutableMap<K, V> map() {
        return ImmutableSortedMap.this;
      }
    }
    return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet();
  }

  
Returns an immutable sorted set of the keys in this map. /** Returns an immutable sorted set of the keys in this map. */
  @Override
  public ImmutableSortedSet<K> keySet() {
    return keySet;
  }

  @Override
  ImmutableSet<K> createKeySet() {
    throw new AssertionError("should never be called");
  }

  
Returns an immutable collection of the values in this map, sorted by the ordering of the
corresponding keys.
/**
   * Returns an immutable collection of the values in this map, sorted by the ordering of the
   * corresponding keys.
   */
  @Override
  public ImmutableCollection<V> values() {
    return valueList;
  }

  @Override
  ImmutableCollection<V> createValues() {
    throw new AssertionError("should never be called");
  }

  
Returns the comparator that orders the keys, which is Ordering.natural() when the natural ordering of the keys is used. Note that its behavior is not consistent with TreeMap.comparator(), which returns null to indicate natural ordering. /**
   * Returns the comparator that orders the keys, which is {@link Ordering#natural()} when the
   * natural ordering of the keys is used. Note that its behavior is not consistent with {@link
   * TreeMap#comparator()}, which returns {@code null} to indicate natural ordering.
   */
  @Override
  public Comparator<? super K> comparator() {
    return keySet().comparator();
  }

  @Override
  public K firstKey() {
    return keySet().first();
  }

  @Override
  public K lastKey() {
    return keySet().last();
  }

  private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) {
    if (fromIndex == 0 && toIndex == size()) {
      return this;
    } else if (fromIndex == toIndex) {
      return emptyMap(comparator());
    } else {
      return new ImmutableSortedMap<>(
          keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex));
    }
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are less than toKey. 
The SortedMap.headMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a toKey greater than an earlier 
toKey. However, this method doesn't throw an exception in that situation, but instead keeps the original toKey. /**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less
   * than {@code toKey}.
   *
   * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an
   * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code
   * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps
   * the original {@code toKey}.
   */
  @Override
  public ImmutableSortedMap<K, V> headMap(K toKey) {
    return headMap(toKey, false);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are less than (or equal to, if inclusive) toKey. 
The SortedMap.headMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a toKey greater than an earlier 
toKey. However, this method doesn't throw an exception in that situation, but instead keeps the original toKey. 
Since:
12.0/**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less
   * than (or equal to, if {@code inclusive}) {@code toKey}.
   *
   * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an
   * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code
   * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps
   * the original {@code toKey}.
   *
   * @since 12.0
   */
  @Override
  public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) {
    return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive));
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys ranges from fromKey, inclusive, to toKey, exclusive. 
The SortedMap.subMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey. Similarly, this method keeps the original toKey, instead of throwing an exception, if passed a toKey greater than an earlier toKey. /**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
   * from {@code fromKey}, inclusive, to {@code toKey}, exclusive.
   *
   * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link
   * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}.
   * However, this method doesn't throw an exception in that situation, but instead keeps the
   * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of
   * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}.
   */
  @Override
  public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
    return subMap(fromKey, true, toKey, false);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys ranges from fromKey to toKey, inclusive or exclusive as indicated by the boolean flags. 
The SortedMap.subMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey. Similarly, this method keeps the original toKey, instead of throwing an exception, if passed a toKey greater than an earlier toKey. 
Since:
12.0/**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
   * from {@code fromKey} to {@code toKey}, inclusive or exclusive as indicated by the boolean
   * flags.
   *
   * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link
   * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}.
   * However, this method doesn't throw an exception in that situation, but instead keeps the
   * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of
   * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}.
   *
   * @since 12.0
   */
  @Override
  public ImmutableSortedMap<K, V> subMap(
      K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
    checkNotNull(fromKey);
    checkNotNull(toKey);
    checkArgument(
        comparator().compare(fromKey, toKey) <= 0,
        "expected fromKey <= toKey but %s > %s",
        fromKey,
        toKey);
    return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are greater than or equals to fromKey. 
The SortedMap.tailMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier 
fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey. /**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are
   * greater than or equals to {@code fromKey}.
   *
   * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an
   * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code
   * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps
   * the original {@code fromKey}.
   */
  @Override
  public ImmutableSortedMap<K, V> tailMap(K fromKey) {
    return tailMap(fromKey, true);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are greater than (or equal to, if inclusive) fromKey. 
The SortedMap.tailMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier 
fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey. 
Since:
12.0/**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are
   * greater than (or equal to, if {@code inclusive}) {@code fromKey}.
   *
   * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an
   * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code
   * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps
   * the original {@code fromKey}.
   *
   * @since 12.0
   */
  @Override
  public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) {
    return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size());
  }

  @Override
  public Entry<K, V> lowerEntry(K key) {
    return headMap(key, false).lastEntry();
  }

  @Override
  public K lowerKey(K key) {
    return keyOrNull(lowerEntry(key));
  }

  @Override
  public Entry<K, V> floorEntry(K key) {
    return headMap(key, true).lastEntry();
  }

  @Override
  public K floorKey(K key) {
    return keyOrNull(floorEntry(key));
  }

  @Override
  public Entry<K, V> ceilingEntry(K key) {
    return tailMap(key, true).firstEntry();
  }

  @Override
  public K ceilingKey(K key) {
    return keyOrNull(ceilingEntry(key));
  }

  @Override
  public Entry<K, V> higherEntry(K key) {
    return tailMap(key, false).firstEntry();
  }

  @Override
  public K higherKey(K key) {
    return keyOrNull(higherEntry(key));
  }

  @Override
  public Entry<K, V> firstEntry() {
    return isEmpty() ? null : entrySet().asList().get(0);
  }

  @Override
  public Entry<K, V> lastEntry() {
    return isEmpty() ? null : entrySet().asList().get(size() - 1);
  }

  
Guaranteed to throw an exception and leave the map unmodified.
Throws:
UnsupportedOperationException – always
Deprecated:
Unsupported operation./**
   * Guaranteed to throw an exception and leave the map unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @CanIgnoreReturnValue
  @Deprecated
  @Override
  public final Entry<K, V> pollFirstEntry() {
    throw new UnsupportedOperationException();
  }

  
Guaranteed to throw an exception and leave the map unmodified.
Throws:
UnsupportedOperationException – always
Deprecated:
Unsupported operation./**
   * Guaranteed to throw an exception and leave the map unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @CanIgnoreReturnValue
  @Deprecated
  @Override
  public final Entry<K, V> pollLastEntry() {
    throw new UnsupportedOperationException();
  }

  @Override
  public ImmutableSortedMap<K, V> descendingMap() {
    // TODO(kevinb): the descendingMap is never actually cached at all. Either it should be or the
    // code below simplified.
    ImmutableSortedMap<K, V> result = descendingMap;
    if (result == null) {
      if (isEmpty()) {
        return result = emptyMap(Ordering.from(comparator()).reverse());
      } else {
        return result =
            new ImmutableSortedMap<>(
                (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this);
      }
    }
    return result;
  }

  @Override
  public ImmutableSortedSet<K> navigableKeySet() {
    return keySet;
  }

  @Override
  public ImmutableSortedSet<K> descendingKeySet() {
    return keySet.descendingSet();
  }

  
Serialized type for all ImmutableSortedMap instances. It captures the logical contents and they
are reconstructed using public factory methods. This ensures that the implementation types
remain as implementation details.
/**
   * Serialized type for all ImmutableSortedMap 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 extends ImmutableMap.SerializedForm {
    private final Comparator<Object> comparator;

    @SuppressWarnings("unchecked")
    SerializedForm(ImmutableSortedMap<?, ?> sortedMap) {
      super(sortedMap);
      comparator = (Comparator<Object>) sortedMap.comparator();
    }

    @Override
    Object readResolve() {
      Builder<Object, Object> builder = new Builder<>(comparator);
      return createMap(builder);
    }

    private static final long serialVersionUID = 0;
  }

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

  // This class is never actually serialized directly, but we have to make the
  // warning go away (and suppressing would suppress for all nested classes too)
  private static final long serialVersionUID = 0;
}