content: /*
   * Copyright (C) 2014 The Android Open Source Project
   * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  package java.util;
  
  import java.io.Serializable;
  import java.util.function.BiConsumer;
  import java.util.function.BiFunction;
  import java.util.function.Consumer;
  
  /**
   * A Red-Black tree based {@link NavigableMap} implementation.
   * The map is sorted according to the {@linkplain Comparable natural
   * ordering} of its keys, or by a {@link Comparator} provided at map
   * creation time, depending on which constructor is used.
   *
   * <p>This implementation provides guaranteed log(n) time cost for the
   * {@code containsKey}, {@code get}, {@code put} and {@code remove}
   * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
   * Rivest's <em>Introduction to Algorithms</em>.
   *
   * <p>Note that the ordering maintained by a tree map, like any sorted map, and
   * whether or not an explicit comparator is provided, must be <em>consistent
   * with {@code equals}</em> if this sorted map is to correctly implement the
   * {@code Map} interface.  (See {@code Comparable} or {@code Comparator} for a
   * precise definition of <em>consistent with equals</em>.)  This is so because
   * the {@code Map} interface is defined in terms of the {@code equals}
   * operation, but a sorted map performs all key comparisons using its {@code
   * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
   * this method are, from the standpoint of the sorted map, equal.  The behavior
   * of a sorted map <em>is</em> well-defined even if its ordering is
   * inconsistent with {@code equals}; it just fails to obey the general contract
   * of the {@code Map} interface.
   *
   * <p><strong>Note that this implementation is not synchronized.</strong>
   * If multiple threads access a map concurrently, and at least one of the
   * threads modifies the map structurally, it <em>must</em> be synchronized
   * externally.  (A structural modification is any operation that adds or
   * deletes one or more mappings; merely changing the value associated
   * with an existing key is not a structural modification.)  This is
   * typically accomplished by synchronizing on some object that naturally
   * encapsulates the map.
   * If no such object exists, the map should be "wrapped" using the
   * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
   * method.  This is best done at creation time, to prevent accidental
   * unsynchronized access to the map: <pre>
   *   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
   *
   * <p>The iterators returned by the {@code iterator} method of the collections
   * returned by all of this class's "collection view methods" are
   * <em>fail-fast</em>: if the map is structurally modified at any time after
   * the iterator is created, in any way except through the iterator's own
   * {@code remove} method, the iterator will throw a {@link
   * ConcurrentModificationException}.  Thus, in the face of concurrent
   * modification, the iterator fails quickly and cleanly, rather than risking
   * arbitrary, non-deterministic behavior at an undetermined time in the future.
   *
   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
   * as it is, generally speaking, impossible to make any hard guarantees in the
   * presence of unsynchronized concurrent modification.  Fail-fast iterators
   * throw {@code ConcurrentModificationException} on a best-effort basis.
   * Therefore, it would be wrong to write a program that depended on this
   * exception for its correctness:   <em>the fail-fast behavior of iterators
   * should be used only to detect bugs.</em>
   *
   * <p>All {@code Map.Entry} pairs returned by methods in this class
   * and its views represent snapshots of mappings at the time they were
   * produced. They do <strong>not</strong> support the {@code Entry.setValue}
   * method. (Note however that it is possible to change mappings in the
   * associated map using {@code put}.)
   *
   * <p>This class is a member of the
   * <a href="{@docRoot}/../technotes/guides/collections/index.html">
   * Java Collections Framework</a>.
   *
   * @param <K> the type of keys maintained by this map
   * @param <V> the type of mapped values
   *
   * @author  Josh Bloch and Doug Lea
   * @see Map
   * @see HashMap
   * @see Hashtable
   * @see Comparable
   * @see Comparator
   * @see Collection
   * @since 1.2
   */
  
  public class TreeMap<K,V>
      extends AbstractMap<K,V>
      implements NavigableMap<K,V>, Cloneable, Serializable
  {
      /**
       * The comparator used to maintain order in this tree map, or
       * null if it uses the natural ordering of its keys.
       *
       * @serial
       */
      private final Comparator<? super K> comparator;
  
      private transient TreeMapEntry<K,V> root;
  
      /**
       * The number of entries in the tree
       */
      private transient int size = 0;
  
      /**
       * The number of structural modifications to the tree.
       */
      private transient int modCount = 0;
  
      /**
       * Constructs a new, empty tree map, using the natural ordering of its
       * keys.  All keys inserted into the map must implement the {@link
       * Comparable} interface.  Furthermore, all such keys must be
       * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
       * a {@code ClassCastException} for any keys {@code k1} and
       * {@code k2} in the map.  If the user attempts to put a key into the
       * map that violates this constraint (for example, the user attempts to
       * put a string key into a map whose keys are integers), the
       * {@code put(Object key, Object value)} call will throw a
       * {@code ClassCastException}.
       */
      public TreeMap() {
          comparator = null;
      }
  
      /**
       * Constructs a new, empty tree map, ordered according to the given
       * comparator.  All keys inserted into the map must be <em>mutually
       * comparable</em> by the given comparator: {@code comparator.compare(k1,
       * k2)} must not throw a {@code ClassCastException} for any keys
       * {@code k1} and {@code k2} in the map.  If the user attempts to put
       * a key into the map that violates this constraint, the {@code put(Object
       * key, Object value)} call will throw a
       * {@code ClassCastException}.
       *
       * @param comparator the comparator that will be used to order this map.
       *        If {@code null}, the {@linkplain Comparable natural
       *        ordering} of the keys will be used.
       */
      public TreeMap(Comparator<? super K> comparator) {
          this.comparator = comparator;
      }
  
      /**
       * Constructs a new tree map containing the same mappings as the given
       * map, ordered according to the <em>natural ordering</em> of its keys.
       * All keys inserted into the new map must implement the {@link
       * Comparable} interface.  Furthermore, all such keys must be
       * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
       * a {@code ClassCastException} for any keys {@code k1} and
       * {@code k2} in the map.  This method runs in n*log(n) time.
       *
       * @param  m the map whose mappings are to be placed in this map
       * @throws ClassCastException if the keys in m are not {@link Comparable},
       *         or are not mutually comparable
       * @throws NullPointerException if the specified map is null
       */
      public TreeMap(Map<? extends K, ? extends V> m) {
          comparator = null;
          putAll(m);
      }
  
      /**
       * Constructs a new tree map containing the same mappings and
       * using the same ordering as the specified sorted map.  This
       * method runs in linear time.
       *
       * @param  m the sorted map whose mappings are to be placed in this map,
       *         and whose comparator is to be used to sort this map
       * @throws NullPointerException if the specified map is null
       */
      public TreeMap(SortedMap<K, ? extends V> m) {
          comparator = m.comparator();
          try {
              buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
          } catch (java.io.IOException cannotHappen) {
          } catch (ClassNotFoundException cannotHappen) {
          }
      }
  
  
      // Query Operations
  
      /**
       * Returns the number of key-value mappings in this map.
       *
       * @return the number of key-value mappings in this map
       */
      public int size() {
          return size;
      }
  
      /**
       * Returns {@code true} if this map contains a mapping for the specified
       * key.
       *
       * @param key key whose presence in this map is to be tested
       * @return {@code true} if this map contains a mapping for the
       *         specified key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       */
      public boolean containsKey(Object key) {
          return getEntry(key) != null;
      }
  
      /**
       * Returns {@code true} if this map maps one or more keys to the
       * specified value.  More formally, returns {@code true} if and only if
       * this map contains at least one mapping to a value {@code v} such
       * that {@code (value==null ? v==null : value.equals(v))}.  This
       * operation will probably require time linear in the map size for
       * most implementations.
       *
       * @param value value whose presence in this map is to be tested
       * @return {@code true} if a mapping to {@code value} exists;
       *         {@code false} otherwise
       * @since 1.2
       */
      public boolean containsValue(Object value) {
          for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e))
              if (valEquals(value, e.value))
                  return true;
          return false;
      }
  
      /**
       * Returns the value to which the specified key is mapped,
       * or {@code null} if this map contains no mapping for the key.
       *
       * <p>More formally, if this map contains a mapping from a key
       * {@code k} to a value {@code v} such that {@code key} compares
       * equal to {@code k} according to the map's ordering, then this
       * method returns {@code v}; otherwise it returns {@code null}.
       * (There can be at most one such mapping.)
       *
       * <p>A return value of {@code null} does not <em>necessarily</em>
       * indicate that the map contains no mapping for the key; it's also
       * possible that the map explicitly maps the key to {@code null}.
       * The {@link #containsKey containsKey} operation may be used to
       * distinguish these two cases.
       *
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       */
      public V get(Object key) {
          TreeMapEntry<K,V> p = getEntry(key);
          return (p==null ? null : p.value);
      }
  
      public Comparator<? super K> comparator() {
          return comparator;
      }
  
      /**
       * @throws NoSuchElementException {@inheritDoc}
       */
      public K firstKey() {
          return key(getFirstEntry());
      }
  
      /**
       * @throws NoSuchElementException {@inheritDoc}
       */
      public K lastKey() {
          return key(getLastEntry());
      }
  
      /**
       * Copies all of the mappings from the specified map to this map.
       * These mappings replace any mappings that this map had for any
       * of the keys currently in the specified map.
       *
       * @param  map mappings to be stored in this map
       * @throws ClassCastException if the class of a key or value in
       *         the specified map prevents it from being stored in this map
       * @throws NullPointerException if the specified map is null or
       *         the specified map contains a null key and this map does not
       *         permit null keys
       */
      public void putAll(Map<? extends K, ? extends V> map) {
          int mapSize = map.size();
          if (size==0 && mapSize!=0 && map instanceof SortedMap) {
              Comparator<?> c = ((SortedMap<?,?>)map).comparator();
              if (c == comparator || (c != null && c.equals(comparator))) {
                  ++modCount;
                  try {
                      buildFromSorted(mapSize, map.entrySet().iterator(),
                                      null, null);
                  } catch (java.io.IOException cannotHappen) {
                  } catch (ClassNotFoundException cannotHappen) {
                  }
                  return;
              }
          }
          super.putAll(map);
      }
  
      /**
       * Returns this map's entry for the given key, or {@code null} if the map
       * does not contain an entry for the key.
       *
       * @return this map's entry for the given key, or {@code null} if the map
       *         does not contain an entry for the key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       */
      final TreeMapEntry<K,V> getEntry(Object key) {
          // Offload comparator-based version for sake of performance
          if (comparator != null)
              return getEntryUsingComparator(key);
          if (key == null)
              throw new NullPointerException();
          @SuppressWarnings("unchecked")
              Comparable<? super K> k = (Comparable<? super K>) key;
          TreeMapEntry<K,V> p = root;
          while (p != null) {
              int cmp = k.compareTo(p.key);
              if (cmp < 0)
                  p = p.left;
              else if (cmp > 0)
                  p = p.right;
              else
                  return p;
          }
          return null;
      }
  
      /**
       * Version of getEntry using comparator. Split off from getEntry
       * for performance. (This is not worth doing for most methods,
       * that are less dependent on comparator performance, but is
       * worthwhile here.)
       */
      final TreeMapEntry<K,V> getEntryUsingComparator(Object key) {
          @SuppressWarnings("unchecked")
              K k = (K) key;
          Comparator<? super K> cpr = comparator;
          if (cpr != null) {
              TreeMapEntry<K,V> p = root;
              while (p != null) {
                  int cmp = cpr.compare(k, p.key);
                  if (cmp < 0)
                      p = p.left;
                  else if (cmp > 0)
                      p = p.right;
                  else
                      return p;
              }
          }
          return null;
      }
  
      /**
       * Gets the entry corresponding to the specified key; if no such entry
       * exists, returns the entry for the least key greater than the specified
       * key; if no such entry exists (i.e., the greatest key in the Tree is less
       * than the specified key), returns {@code null}.
       */
      final TreeMapEntry<K,V> getCeilingEntry(K key) {
          TreeMapEntry<K,V> p = root;
          while (p != null) {
              int cmp = compare(key, p.key);
              if (cmp < 0) {
                  if (p.left != null)
                      p = p.left;
                  else
                      return p;
              } else if (cmp > 0) {
                  if (p.right != null) {
                      p = p.right;
                  } else {
                      TreeMapEntry<K,V> parent = p.parent;
                      TreeMapEntry<K,V> ch = p;
                      while (parent != null && ch == parent.right) {
                          ch = parent;
                          parent = parent.parent;
                      }
                      return parent;
                  }
              } else
                  return p;
          }
          return null;
      }
  
      /**
       * Gets the entry corresponding to the specified key; if no such entry
       * exists, returns the entry for the greatest key less than the specified
       * key; if no such entry exists, returns {@code null}.
       */
      final TreeMapEntry<K,V> getFloorEntry(K key) {
          TreeMapEntry<K,V> p = root;
          while (p != null) {
              int cmp = compare(key, p.key);
              if (cmp > 0) {
                  if (p.right != null)
                      p = p.right;
                  else
                      return p;
              } else if (cmp < 0) {
                  if (p.left != null) {
                      p = p.left;
                  } else {
                      TreeMapEntry<K,V> parent = p.parent;
                      TreeMapEntry<K,V> ch = p;
                      while (parent != null && ch == parent.left) {
                          ch = parent;
                          parent = parent.parent;
                      }
                      return parent;
                  }
              } else
                  return p;
  
          }
          return null;
      }
  
      /**
       * Gets the entry for the least key greater than the specified
       * key; if no such entry exists, returns the entry for the least
       * key greater than the specified key; if no such entry exists
       * returns {@code null}.
       */
      final TreeMapEntry<K,V> getHigherEntry(K key) {
          TreeMapEntry<K,V> p = root;
          while (p != null) {
              int cmp = compare(key, p.key);
              if (cmp < 0) {
                  if (p.left != null)
                      p = p.left;
                  else
                      return p;
              } else {
                  if (p.right != null) {
                      p = p.right;
                  } else {
                      TreeMapEntry<K,V> parent = p.parent;
                      TreeMapEntry<K,V> ch = p;
                      while (parent != null && ch == parent.right) {
                          ch = parent;
                          parent = parent.parent;
                      }
                      return parent;
                  }
              }
          }
          return null;
      }
  
      /**
       * Returns the entry for the greatest key less than the specified key; if
       * no such entry exists (i.e., the least key in the Tree is greater than
       * the specified key), returns {@code null}.
       */
      final TreeMapEntry<K,V> getLowerEntry(K key) {
          TreeMapEntry<K,V> p = root;
          while (p != null) {
              int cmp = compare(key, p.key);
              if (cmp > 0) {
                  if (p.right != null)
                      p = p.right;
                  else
                      return p;
              } else {
                  if (p.left != null) {
                      p = p.left;
                  } else {
                      TreeMapEntry<K,V> parent = p.parent;
                      TreeMapEntry<K,V> ch = p;
                      while (parent != null && ch == parent.left) {
                          ch = parent;
                          parent = parent.parent;
                      }
                      return parent;
                  }
              }
          }
          return null;
      }
  
      /**
       * Associates the specified value with the specified key in this map.
       * If the map previously contained a mapping for the key, the old
       * value is replaced.
       *
       * @param key key with which the specified value is to be associated
       * @param value value to be associated with the specified key
       *
       * @return the previous value associated with {@code key}, or
       *         {@code null} if there was no mapping for {@code key}.
       *         (A {@code null} return can also indicate that the map
       *         previously associated {@code null} with {@code key}.)
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       */
      public V put(K key, V value) {
          TreeMapEntry<K,V> t = root;
          if (t == null) {
              compare(key, key); // type (and possibly null) check
  
              root = new TreeMapEntry<>(key, value, null);
              size = 1;
              modCount++;
              return null;
          }
          int cmp;
          TreeMapEntry<K,V> parent;
          // split comparator and comparable paths
          Comparator<? super K> cpr = comparator;
          if (cpr != null) {
              do {
                  parent = t;
                  cmp = cpr.compare(key, t.key);
                  if (cmp < 0)
                      t = t.left;
                  else if (cmp > 0)
                      t = t.right;
                  else
                      return t.setValue(value);
              } while (t != null);
          }
          else {
              if (key == null)
                  throw new NullPointerException();
              @SuppressWarnings("unchecked")
                  Comparable<? super K> k = (Comparable<? super K>) key;
              do {
                  parent = t;
                  cmp = k.compareTo(t.key);
                  if (cmp < 0)
                      t = t.left;
                  else if (cmp > 0)
                      t = t.right;
                  else
                      return t.setValue(value);
              } while (t != null);
          }
          TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
          if (cmp < 0)
              parent.left = e;
          else
              parent.right = e;
          fixAfterInsertion(e);
          size++;
          modCount++;
          return null;
      }
  
      /**
       * Removes the mapping for this key from this TreeMap if present.
       *
       * @param  key key for which mapping should be removed
       * @return the previous value associated with {@code key}, or
       *         {@code null} if there was no mapping for {@code key}.
       *         (A {@code null} return can also indicate that the map
       *         previously associated {@code null} with {@code key}.)
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       */
      public V remove(Object key) {
          TreeMapEntry<K,V> p = getEntry(key);
          if (p == null)
              return null;
  
          V oldValue = p.value;
          deleteEntry(p);
          return oldValue;
      }
  
      /**
       * Removes all of the mappings from this map.
       * The map will be empty after this call returns.
       */
      public void clear() {
          modCount++;
          size = 0;
          root = null;
      }
  
      /**
       * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
       * values themselves are not cloned.)
       *
       * @return a shallow copy of this map
       */
      public Object clone() {
          TreeMap<?,?> clone;
          try {
              clone = (TreeMap<?,?>) super.clone();
          } catch (CloneNotSupportedException e) {
              throw new InternalError(e);
          }
  
          // Put clone into "virgin" state (except for comparator)
          clone.root = null;
          clone.size = 0;
          clone.modCount = 0;
          clone.entrySet = null;
          clone.navigableKeySet = null;
          clone.descendingMap = null;
  
          // Initialize clone with our mappings
          try {
              clone.buildFromSorted(size, entrySet().iterator(), null, null);
          } catch (java.io.IOException cannotHappen) {
          } catch (ClassNotFoundException cannotHappen) {
          }
  
          return clone;
      }
  
      // NavigableMap API methods
  
      /**
       * @since 1.6
       */
      public Entry<K,V> firstEntry() {
          return exportEntry(getFirstEntry());
      }
  
      /**
       * @since 1.6
       */
      public Entry<K,V> lastEntry() {
          return exportEntry(getLastEntry());
      }
  
      /**
       * @since 1.6
       */
      public Entry<K,V> pollFirstEntry() {
          TreeMapEntry<K,V> p = getFirstEntry();
          Entry<K,V> result = exportEntry(p);
          if (p != null)
              deleteEntry(p);
          return result;
      }
  
      /**
       * @since 1.6
       */
      public Entry<K,V> pollLastEntry() {
          TreeMapEntry<K,V> p = getLastEntry();
          Entry<K,V> result = exportEntry(p);
          if (p != null)
              deleteEntry(p);
          return result;
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public Entry<K,V> lowerEntry(K key) {
          return exportEntry(getLowerEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public K lowerKey(K key) {
          return keyOrNull(getLowerEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public Entry<K,V> floorEntry(K key) {
          return exportEntry(getFloorEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public K floorKey(K key) {
          return keyOrNull(getFloorEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public Entry<K,V> ceilingEntry(K key) {
          return exportEntry(getCeilingEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public K ceilingKey(K key) {
          return keyOrNull(getCeilingEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public Entry<K,V> higherEntry(K key) {
          return exportEntry(getHigherEntry(key));
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @since 1.6
       */
      public K higherKey(K key) {
          return keyOrNull(getHigherEntry(key));
      }
  
      // Views
  
      /**
       * Fields initialized to contain an instance of the entry set view
       * the first time this view is requested.  Views are stateless, so
       * there's no reason to create more than one.
       */
      private transient EntrySet entrySet;
      private transient KeySet<K> navigableKeySet;
      private transient NavigableMap<K,V> descendingMap;
  
      /**
       * Returns a {@link Set} view of the keys contained in this map.
       *
       * <p>The set's iterator returns the keys in ascending order.
       * The set's spliterator is
       * <em><a href="Spliterator.html#binding">late-binding</a></em>,
       * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED}
       * and {@link Spliterator#ORDERED} with an encounter order that is ascending
       * key order.  The spliterator's comparator (see
       * {@link Spliterator#getComparator()}) is {@code null} if
       * the tree map's comparator (see {@link #comparator()}) is {@code null}.
       * Otherwise, the spliterator's comparator is the same as or imposes the
       * same total ordering as the tree map's comparator.
       *
       * <p>The set is backed by the map, so changes to the map are
       * reflected in the set, and vice-versa.  If the map is modified
       * while an iteration over the set is in progress (except through
       * the iterator's own {@code remove} operation), the results of
       * the iteration are undefined.  The set supports element removal,
       * which removes the corresponding mapping from the map, via the
       * {@code Iterator.remove}, {@code Set.remove},
       * {@code removeAll}, {@code retainAll}, and {@code clear}
       * operations.  It does not support the {@code add} or {@code addAll}
       * operations.
       */
      public Set<K> keySet() {
          return navigableKeySet();
      }
  
      /**
       * @since 1.6
       */
      public NavigableSet<K> navigableKeySet() {
          KeySet<K> nks = navigableKeySet;
          return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
      }
  
      /**
       * @since 1.6
       */
      public NavigableSet<K> descendingKeySet() {
          return descendingMap().navigableKeySet();
      }
  
      /**
       * Returns a {@link Collection} view of the values contained in this map.
       *
       * <p>The collection's iterator returns the values in ascending order
       * of the corresponding keys. The collection's spliterator is
       * <em><a href="Spliterator.html#binding">late-binding</a></em>,
       * <em>fail-fast</em>, and additionally reports {@link Spliterator#ORDERED}
       * with an encounter order that is ascending order of the corresponding
       * keys.
       *
       * <p>The collection is backed by the map, so changes to the map are
       * reflected in the collection, and vice-versa.  If the map is
       * modified while an iteration over the collection is in progress
       * (except through the iterator's own {@code remove} operation),
       * the results of the iteration are undefined.  The collection
       * supports element removal, which removes the corresponding
       * mapping from the map, via the {@code Iterator.remove},
       * {@code Collection.remove}, {@code removeAll},
       * {@code retainAll} and {@code clear} operations.  It does not
       * support the {@code add} or {@code addAll} operations.
       */
      public Collection<V> values() {
          Collection<V> vs = values;
          if (vs == null) {
              vs = new Values();
              values = vs;
          }
          return vs;
      }
  
      /**
       * Returns a {@link Set} view of the mappings contained in this map.
       *
       * <p>The set's iterator returns the entries in ascending key order. The
       * sets's spliterator is
       * <em><a href="Spliterator.html#binding">late-binding</a></em>,
       * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED} and
       * {@link Spliterator#ORDERED} with an encounter order that is ascending key
       * order.
       *
       * <p>The set is backed by the map, so changes to the map are
       * reflected in the set, and vice-versa.  If the map is modified
       * while an iteration over the set is in progress (except through
       * the iterator's own {@code remove} operation, or through the
       * {@code setValue} operation on a map entry returned by the
       * iterator) the results of the iteration are undefined.  The set
       * supports element removal, which removes the corresponding
       * mapping from the map, via the {@code Iterator.remove},
       * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
       * {@code clear} operations.  It does not support the
       * {@code add} or {@code addAll} operations.
       */
      public Set<Entry<K,V>> entrySet() {
          EntrySet es = entrySet;
          return (es != null) ? es : (entrySet = new EntrySet());
      }
  
      /**
       * @since 1.6
       */
      public NavigableMap<K, V> descendingMap() {
          NavigableMap<K, V> km = descendingMap;
          return (km != null) ? km :
              (descendingMap = new DescendingSubMap<>(this,
                                                      true, null, true,
                                                      true, null, true));
      }
  
      /**
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} or {@code toKey} is
       *         null and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @throws IllegalArgumentException {@inheritDoc}
       * @since 1.6
       */
      public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                      K toKey,   boolean toInclusive) {
          return new AscendingSubMap<>(this,
                                       false, fromKey, fromInclusive,
                                       false, toKey,   toInclusive);
      }
  
      /**
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException if {@code toKey} is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @throws IllegalArgumentException {@inheritDoc}
       * @since 1.6
       */
      public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
          return new AscendingSubMap<>(this,
                                       true,  null,  true,
                                       false, toKey, inclusive);
      }
  
      /**
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @throws IllegalArgumentException {@inheritDoc}
       * @since 1.6
       */
      public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
          return new AscendingSubMap<>(this,
                                       false, fromKey, inclusive,
                                       true,  null,    true);
      }
  
      /**
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} or {@code toKey} is
       *         null and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public SortedMap<K,V> subMap(K fromKey, K toKey) {
          return subMap(fromKey, true, toKey, false);
      }
  
      /**
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException if {@code toKey} is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public SortedMap<K,V> headMap(K toKey) {
          return headMap(toKey, false);
      }
  
      /**
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} is null
       *         and this map uses natural ordering, or its comparator
       *         does not permit null keys
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public SortedMap<K,V> tailMap(K fromKey) {
          return tailMap(fromKey, true);
      }
  
      @Override
      public boolean replace(K key, V oldValue, V newValue) {
          TreeMapEntry<K,V> p = getEntry(key);
          if (p!=null && Objects.equals(oldValue, p.value)) {
              p.value = newValue;
              return true;
          }
          return false;
      }
  
      @Override
      public V replace(K key, V value) {
          TreeMapEntry<K,V> p = getEntry(key);
          if (p!=null) {
              V oldValue = p.value;
              p.value = value;
              return oldValue;
          }
          return null;
      }
  
      @Override
      public void forEach(BiConsumer<? super K, ? super V> action) {
          Objects.requireNonNull(action);
          int expectedModCount = modCount;
          for (TreeMapEntry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
              action.accept(e.key, e.value);
  
              if (expectedModCount != modCount) {
                  throw new ConcurrentModificationException();
              }
          }
      }
  
      @Override
      public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
          Objects.requireNonNull(function);
          int expectedModCount = modCount;
  
          for (TreeMapEntry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
              e.value = function.apply(e.key, e.value);
  
              if (expectedModCount != modCount) {
                  throw new ConcurrentModificationException();
              }
          }
      }
  
      // View class support
  
      class Values extends AbstractCollection<V> {
          public Iterator<V> iterator() {
              return new ValueIterator(getFirstEntry());
          }
  
          public int size() {
              return TreeMap.this.size();
          }
  
          public boolean contains(Object o) {
              return TreeMap.this.containsValue(o);
          }
  
          public boolean remove(Object o) {
              for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
                  if (valEquals(e.getValue(), o)) {
                      deleteEntry(e);
                      return true;
                  }
              }
              return false;
          }
  
          public void clear() {
              TreeMap.this.clear();
          }
  
          public Spliterator<V> spliterator() {
              return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
          }
      }
  
      class EntrySet extends AbstractSet<Entry<K,V>> {
          public Iterator<Entry<K,V>> iterator() {
              return new EntryIterator(getFirstEntry());
          }
  
          public boolean contains(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> entry = (Entry<?,?>) o;
              Object value = entry.getValue();
              TreeMapEntry<K,V> p = getEntry(entry.getKey());
              return p != null && valEquals(p.getValue(), value);
          }
  
          public boolean remove(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> entry = (Entry<?,?>) o;
              Object value = entry.getValue();
              TreeMapEntry<K,V> p = getEntry(entry.getKey());
              if (p != null && valEquals(p.getValue(), value)) {
                  deleteEntry(p);
                  return true;
              }
              return false;
          }
  
          public int size() {
              return TreeMap.this.size();
          }
  
          public void clear() {
              TreeMap.this.clear();
          }
  
          public Spliterator<Entry<K,V>> spliterator() {
              return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
          }
      }
  
      /*
       * Unlike Values and EntrySet, the KeySet class is static,
       * delegating to a NavigableMap to allow use by SubMaps, which
       * outweighs the ugliness of needing type-tests for the following
       * Iterator methods that are defined appropriately in main versus
       * submap classes.
       */
  
      Iterator<K> keyIterator() {
          return new KeyIterator(getFirstEntry());
      }
  
      Iterator<K> descendingKeyIterator() {
          return new DescendingKeyIterator(getLastEntry());
      }
  
      static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
          private final NavigableMap<E, ?> m;
          KeySet(NavigableMap<E,?> map) { m = map; }
  
          public Iterator<E> iterator() {
              if (m instanceof TreeMap)
                  return ((TreeMap<E,?>)m).keyIterator();
              else
                  return ((NavigableSubMap<E,?>)m).keyIterator();
          }
  
          public Iterator<E> descendingIterator() {
              if (m instanceof TreeMap)
                  return ((TreeMap<E,?>)m).descendingKeyIterator();
              else
                  return ((NavigableSubMap<E,?>)m).descendingKeyIterator();
          }
  
          public int size() { return m.size(); }
          public boolean isEmpty() { return m.isEmpty(); }
          public boolean contains(Object o) { return m.containsKey(o); }
          public void clear() { m.clear(); }
          public E lower(E e) { return m.lowerKey(e); }
          public E floor(E e) { return m.floorKey(e); }
          public E ceiling(E e) { return m.ceilingKey(e); }
          public E higher(E e) { return m.higherKey(e); }
          public E first() { return m.firstKey(); }
          public E last() { return m.lastKey(); }
          public Comparator<? super E> comparator() { return m.comparator(); }
          public E pollFirst() {
              Entry<E,?> e = m.pollFirstEntry();
              return (e == null) ? null : e.getKey();
          }
          public E pollLast() {
              Entry<E,?> e = m.pollLastEntry();
              return (e == null) ? null : e.getKey();
          }
          public boolean remove(Object o) {
              int oldSize = size();
              m.remove(o);
              return size() != oldSize;
          }
          public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                        E toElement,   boolean toInclusive) {
              return new KeySet<>(m.subMap(fromElement, fromInclusive,
                                            toElement,   toInclusive));
          }
          public NavigableSet<E> headSet(E toElement, boolean inclusive) {
              return new KeySet<>(m.headMap(toElement, inclusive));
          }
          public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
              return new KeySet<>(m.tailMap(fromElement, inclusive));
          }
          public SortedSet<E> subSet(E fromElement, E toElement) {
              return subSet(fromElement, true, toElement, false);
          }
          public SortedSet<E> headSet(E toElement) {
              return headSet(toElement, false);
          }
          public SortedSet<E> tailSet(E fromElement) {
              return tailSet(fromElement, true);
          }
          public NavigableSet<E> descendingSet() {
              return new KeySet<>(m.descendingMap());
          }
  
          public Spliterator<E> spliterator() {
              return keySpliteratorFor(m);
          }
      }
  
      /**
       * Base class for TreeMap Iterators
       */
      abstract class PrivateEntryIterator<T> implements Iterator<T> {
          TreeMapEntry<K,V> next;
          TreeMapEntry<K,V> lastReturned;
          int expectedModCount;
  
          PrivateEntryIterator(TreeMapEntry<K,V> first) {
              expectedModCount = modCount;
              lastReturned = null;
              next = first;
          }
  
          public final boolean hasNext() {
              return next != null;
          }
  
          final TreeMapEntry<K,V> nextEntry() {
              TreeMapEntry<K,V> e = next;
              if (e == null)
                  throw new NoSuchElementException();
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              next = successor(e);
              lastReturned = e;
              return e;
          }
  
          final TreeMapEntry<K,V> prevEntry() {
              TreeMapEntry<K,V> e = next;
              if (e == null)
                  throw new NoSuchElementException();
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              next = predecessor(e);
              lastReturned = e;
              return e;
          }
  
          public void remove() {
              if (lastReturned == null)
                  throw new IllegalStateException();
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              // deleted entries are replaced by their successors
              if (lastReturned.left != null && lastReturned.right != null)
                  next = lastReturned;
              deleteEntry(lastReturned);
              expectedModCount = modCount;
              lastReturned = null;
          }
      }
  
      final class EntryIterator extends PrivateEntryIterator<Entry<K,V>> {
          EntryIterator(TreeMapEntry<K,V> first) {
              super(first);
          }
          public Entry<K,V> next() {
              return nextEntry();
          }
      }
  
      final class ValueIterator extends PrivateEntryIterator<V> {
          ValueIterator(TreeMapEntry<K,V> first) {
              super(first);
          }
          public V next() {
              return nextEntry().value;
          }
      }
  
      final class KeyIterator extends PrivateEntryIterator<K> {
          KeyIterator(TreeMapEntry<K,V> first) {
              super(first);
          }
          public K next() {
              return nextEntry().key;
          }
      }
  
      final class DescendingKeyIterator extends PrivateEntryIterator<K> {
          DescendingKeyIterator(TreeMapEntry<K,V> first) {
              super(first);
          }
          public K next() {
              return prevEntry().key;
          }
          public void remove() {
              if (lastReturned == null)
                  throw new IllegalStateException();
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              deleteEntry(lastReturned);
              lastReturned = null;
              expectedModCount = modCount;
          }
      }
  
      // Little utilities
  
      /**
       * Compares two keys using the correct comparison method for this TreeMap.
       */
      @SuppressWarnings("unchecked")
      final int compare(Object k1, Object k2) {
          return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
              : comparator.compare((K)k1, (K)k2);
      }
  
      /**
       * Test two values for equality.  Differs from o1.equals(o2) only in
       * that it copes with {@code null} o1 properly.
       */
      static final boolean valEquals(Object o1, Object o2) {
          return (o1==null ? o2==null : o1.equals(o2));
      }
  
      /**
       * Return SimpleImmutableEntry for entry, or null if null
       */
      static <K,V> Entry<K,V> exportEntry(TreeMapEntry<K,V> e) {
          return (e == null) ? null :
              new SimpleImmutableEntry<>(e);
      }
  
      /**
       * Return key for entry, or null if null
       */
      static <K,V> K keyOrNull(TreeMapEntry<K,V> e) {
          return (e == null) ? null : e.key;
      }
  
      /**
       * Returns the key corresponding to the specified Entry.
       * @throws NoSuchElementException if the Entry is null
       */
      static <K> K key(TreeMapEntry<K,?> e) {
          if (e==null)
              throw new NoSuchElementException();
          return e.key;
      }
  
  
      // SubMaps
  
      /**
       * Dummy value serving as unmatchable fence key for unbounded
       * SubMapIterators
       */
      private static final Object UNBOUNDED = new Object();
  
      /**
       * @serial include
       */
      abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
          implements NavigableMap<K,V>, Serializable {
          // Android-changed: Explicitly add a serialVersionUID so that we're serialization
          // compatible with the Java-7 version of this class. Several new methods were added
          // in Java-8 but none of them have any bearing on the serialized format of the class
          // or require any additional state to be preserved.
          private static final long serialVersionUID = 2765629423043303731L;
  
          /**
           * The backing map.
           */
          final TreeMap<K,V> m;
  
          /**
           * Endpoints are represented as triples (fromStart, lo,
           * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
           * true, then the low (absolute) bound is the start of the
           * backing map, and the other values are ignored. Otherwise,
           * if loInclusive is true, lo is the inclusive bound, else lo
           * is the exclusive bound. Similarly for the upper bound.
           */
          final K lo, hi;
          final boolean fromStart, toEnd;
          final boolean loInclusive, hiInclusive;
  
          NavigableSubMap(TreeMap<K,V> m,
                          boolean fromStart, K lo, boolean loInclusive,
                          boolean toEnd,     K hi, boolean hiInclusive) {
              if (!fromStart && !toEnd) {
                  if (m.compare(lo, hi) > 0)
                      throw new IllegalArgumentException("fromKey > toKey");
              } else {
                  if (!fromStart) // type check
                      m.compare(lo, lo);
                  if (!toEnd)
                      m.compare(hi, hi);
              }
  
              this.m = m;
              this.fromStart = fromStart;
              this.lo = lo;
              this.loInclusive = loInclusive;
              this.toEnd = toEnd;
              this.hi = hi;
              this.hiInclusive = hiInclusive;
          }
  
          // internal utilities
  
          final boolean tooLow(Object key) {
              if (!fromStart) {
                  int c = m.compare(key, lo);
                  if (c < 0 || (c == 0 && !loInclusive))
                      return true;
              }
              return false;
          }
  
          final boolean tooHigh(Object key) {
              if (!toEnd) {
                  int c = m.compare(key, hi);
                  if (c > 0 || (c == 0 && !hiInclusive))
                      return true;
              }
              return false;
          }
  
          final boolean inRange(Object key) {
              return !tooLow(key) && !tooHigh(key);
          }
  
          final boolean inClosedRange(Object key) {
              return (fromStart || m.compare(key, lo) >= 0)
                  && (toEnd || m.compare(hi, key) >= 0);
          }
  
          final boolean inRange(Object key, boolean inclusive) {
              return inclusive ? inRange(key) : inClosedRange(key);
          }
  
          /*
           * Absolute versions of relation operations.
           * Subclasses map to these using like-named "sub"
           * versions that invert senses for descending maps
           */
  
          final TreeMapEntry<K,V> absLowest() {
              TreeMapEntry<K,V> e =
                  (fromStart ?  m.getFirstEntry() :
                   (loInclusive ? m.getCeilingEntry(lo) :
                                  m.getHigherEntry(lo)));
              return (e == null || tooHigh(e.key)) ? null : e;
          }
  
          final TreeMapEntry<K,V> absHighest() {
              TreeMapEntry<K,V> e =
                  (toEnd ?  m.getLastEntry() :
                   (hiInclusive ?  m.getFloorEntry(hi) :
                                   m.getLowerEntry(hi)));
              return (e == null || tooLow(e.key)) ? null : e;
          }
  
          final TreeMapEntry<K,V> absCeiling(K key) {
              if (tooLow(key))
                  return absLowest();
              TreeMapEntry<K,V> e = m.getCeilingEntry(key);
              return (e == null || tooHigh(e.key)) ? null : e;
          }
  
          final TreeMapEntry<K,V> absHigher(K key) {
              if (tooLow(key))
                  return absLowest();
              TreeMapEntry<K,V> e = m.getHigherEntry(key);
              return (e == null || tooHigh(e.key)) ? null : e;
          }
  
          final TreeMapEntry<K,V> absFloor(K key) {
              if (tooHigh(key))
                  return absHighest();
              TreeMapEntry<K,V> e = m.getFloorEntry(key);
              return (e == null || tooLow(e.key)) ? null : e;
          }
  
          final TreeMapEntry<K,V> absLower(K key) {
              if (tooHigh(key))
                  return absHighest();
              TreeMapEntry<K,V> e = m.getLowerEntry(key);
              return (e == null || tooLow(e.key)) ? null : e;
          }
  
          /** Returns the absolute high fence for ascending traversal */
          final TreeMapEntry<K,V> absHighFence() {
              return (toEnd ? null : (hiInclusive ?
                                      m.getHigherEntry(hi) :
                                      m.getCeilingEntry(hi)));
          }
  
          /** Return the absolute low fence for descending traversal  */
          final TreeMapEntry<K,V> absLowFence() {
              return (fromStart ? null : (loInclusive ?
                                          m.getLowerEntry(lo) :
                                          m.getFloorEntry(lo)));
          }
  
          // Abstract methods defined in ascending vs descending classes
          // These relay to the appropriate absolute versions
  
          abstract TreeMapEntry<K,V> subLowest();
          abstract TreeMapEntry<K,V> subHighest();
          abstract TreeMapEntry<K,V> subCeiling(K key);
          abstract TreeMapEntry<K,V> subHigher(K key);
          abstract TreeMapEntry<K,V> subFloor(K key);
          abstract TreeMapEntry<K,V> subLower(K key);
  
          /** Returns ascending iterator from the perspective of this submap */
          abstract Iterator<K> keyIterator();
  
          abstract Spliterator<K> keySpliterator();
  
          /** Returns descending iterator from the perspective of this submap */
          abstract Iterator<K> descendingKeyIterator();
  
          // public methods
  
          public boolean isEmpty() {
              return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
          }
  
          public int size() {
              return (fromStart && toEnd) ? m.size() : entrySet().size();
          }
  
          public final boolean containsKey(Object key) {
              return inRange(key) && m.containsKey(key);
          }
  
          public final V put(K key, V value) {
              if (!inRange(key))
                  throw new IllegalArgumentException("key out of range");
              return m.put(key, value);
          }
  
          public final V get(Object key) {
              return !inRange(key) ? null :  m.get(key);
          }
  
          public final V remove(Object key) {
              return !inRange(key) ? null : m.remove(key);
          }
  
          public final Entry<K,V> ceilingEntry(K key) {
              return exportEntry(subCeiling(key));
          }
  
          public final K ceilingKey(K key) {
              return keyOrNull(subCeiling(key));
          }
  
          public final Entry<K,V> higherEntry(K key) {
              return exportEntry(subHigher(key));
          }
  
          public final K higherKey(K key) {
              return keyOrNull(subHigher(key));
          }
  
          public final Entry<K,V> floorEntry(K key) {
              return exportEntry(subFloor(key));
          }
  
          public final K floorKey(K key) {
              return keyOrNull(subFloor(key));
          }
  
          public final Entry<K,V> lowerEntry(K key) {
              return exportEntry(subLower(key));
          }
  
          public final K lowerKey(K key) {
              return keyOrNull(subLower(key));
          }
  
          public final K firstKey() {
              return key(subLowest());
          }
  
          public final K lastKey() {
              return key(subHighest());
          }
  
          public final Entry<K,V> firstEntry() {
              return exportEntry(subLowest());
          }
  
          public final Entry<K,V> lastEntry() {
              return exportEntry(subHighest());
          }
  
          public final Entry<K,V> pollFirstEntry() {
              TreeMapEntry<K,V> e = subLowest();
              Entry<K,V> result = exportEntry(e);
              if (e != null)
                  m.deleteEntry(e);
              return result;
          }
  
          public final Entry<K,V> pollLastEntry() {
              TreeMapEntry<K,V> e = subHighest();
              Entry<K,V> result = exportEntry(e);
              if (e != null)
                  m.deleteEntry(e);
              return result;
          }
  
          // Views
          transient NavigableMap<K,V> descendingMapView;
          transient EntrySetView entrySetView;
          transient KeySet<K> navigableKeySetView;
  
          public final NavigableSet<K> navigableKeySet() {
              KeySet<K> nksv = navigableKeySetView;
              return (nksv != null) ? nksv :
                  (navigableKeySetView = new KeySet<>(this));
          }
  
          public final Set<K> keySet() {
              return navigableKeySet();
          }
  
          public NavigableSet<K> descendingKeySet() {
              return descendingMap().navigableKeySet();
          }
  
          public final SortedMap<K,V> subMap(K fromKey, K toKey) {
              return subMap(fromKey, true, toKey, false);
          }
  
          public final SortedMap<K,V> headMap(K toKey) {
              return headMap(toKey, false);
          }
  
          public final SortedMap<K,V> tailMap(K fromKey) {
              return tailMap(fromKey, true);
          }
  
          // View classes
  
          abstract class EntrySetView extends AbstractSet<Entry<K,V>> {
              private transient int size = -1, sizeModCount;
  
              public int size() {
                  if (fromStart && toEnd)
                      return m.size();
                  if (size == -1 || sizeModCount != m.modCount) {
                      sizeModCount = m.modCount;
                      size = 0;
                      Iterator<?> i = iterator();
                      while (i.hasNext()) {
                          size++;
                          i.next();
                      }
                  }
                  return size;
              }
  
              public boolean isEmpty() {
                  TreeMapEntry<K,V> n = absLowest();
                  return n == null || tooHigh(n.key);
              }
  
              public boolean contains(Object o) {
                  if (!(o instanceof Map.Entry))
                      return false;
                  Entry<?,?> entry = (Entry<?,?>) o;
                  Object key = entry.getKey();
                  if (!inRange(key))
                      return false;
                  TreeMapEntry<?, ?> node = m.getEntry(key);
                  return node != null &&
                      valEquals(node.getValue(), entry.getValue());
              }
  
              public boolean remove(Object o) {
                  if (!(o instanceof Map.Entry))
                      return false;
                  Entry<?,?> entry = (Entry<?,?>) o;
                  Object key = entry.getKey();
                  if (!inRange(key))
                      return false;
                  TreeMapEntry<K,V> node = m.getEntry(key);
                  if (node!=null && valEquals(node.getValue(),
                                              entry.getValue())) {
                      m.deleteEntry(node);
                      return true;
                  }
                  return false;
              }
          }
  
          /**
           * Iterators for SubMaps
           */
          abstract class SubMapIterator<T> implements Iterator<T> {
              TreeMapEntry<K,V> lastReturned;
              TreeMapEntry<K,V> next;
              final Object fenceKey;
              int expectedModCount;
  
              SubMapIterator(TreeMapEntry<K,V> first,
                             TreeMapEntry<K,V> fence) {
                  expectedModCount = m.modCount;
                  lastReturned = null;
                  next = first;
                  fenceKey = fence == null ? UNBOUNDED : fence.key;
              }
  
              public final boolean hasNext() {
                  return next != null && next.key != fenceKey;
              }
  
              final TreeMapEntry<K,V> nextEntry() {
                  TreeMapEntry<K,V> e = next;
                  if (e == null || e.key == fenceKey)
                      throw new NoSuchElementException();
                  if (m.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
                  next = successor(e);
                  lastReturned = e;
                  return e;
              }
  
              final TreeMapEntry<K,V> prevEntry() {
                  TreeMapEntry<K,V> e = next;
                  if (e == null || e.key == fenceKey)
                      throw new NoSuchElementException();
                  if (m.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
                  next = predecessor(e);
                  lastReturned = e;
                  return e;
              }
  
              final void removeAscending() {
                  if (lastReturned == null)
                      throw new IllegalStateException();
                  if (m.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
                  // deleted entries are replaced by their successors
                  if (lastReturned.left != null && lastReturned.right != null)
                      next = lastReturned;
                  m.deleteEntry(lastReturned);
                  lastReturned = null;
                  expectedModCount = m.modCount;
              }
  
              final void removeDescending() {
                  if (lastReturned == null)
                      throw new IllegalStateException();
                  if (m.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
                  m.deleteEntry(lastReturned);
                  lastReturned = null;
                  expectedModCount = m.modCount;
              }
  
          }
  
          final class SubMapEntryIterator extends SubMapIterator<Entry<K,V>> {
              SubMapEntryIterator(TreeMapEntry<K,V> first,
                                  TreeMapEntry<K,V> fence) {
                  super(first, fence);
              }
              public Entry<K,V> next() {
                  return nextEntry();
              }
              public void remove() {
                  removeAscending();
              }
          }
  
          final class DescendingSubMapEntryIterator extends SubMapIterator<Entry<K,V>> {
              DescendingSubMapEntryIterator(TreeMapEntry<K,V> last,
                                            TreeMapEntry<K,V> fence) {
                  super(last, fence);
              }
  
              public Entry<K,V> next() {
                  return prevEntry();
              }
              public void remove() {
                  removeDescending();
              }
          }
  
          // Implement minimal Spliterator as KeySpliterator backup
          final class SubMapKeyIterator extends SubMapIterator<K>
              implements Spliterator<K> {
              SubMapKeyIterator(TreeMapEntry<K,V> first,
                                TreeMapEntry<K,V> fence) {
                  super(first, fence);
              }
              public K next() {
                  return nextEntry().key;
              }
              public void remove() {
                  removeAscending();
              }
              public Spliterator<K> trySplit() {
                  return null;
              }
              public void forEachRemaining(Consumer<? super K> action) {
                  while (hasNext())
                      action.accept(next());
              }
              public boolean tryAdvance(Consumer<? super K> action) {
                  if (hasNext()) {
                      action.accept(next());
                      return true;
                  }
                  return false;
              }
              public long estimateSize() {
                  return Long.MAX_VALUE;
              }
              public int characteristics() {
                  return Spliterator.DISTINCT | Spliterator.ORDERED |
                      Spliterator.SORTED;
              }
              public final Comparator<? super K>  getComparator() {
                  return NavigableSubMap.this.comparator();
              }
          }
  
          final class DescendingSubMapKeyIterator extends SubMapIterator<K>
              implements Spliterator<K> {
              DescendingSubMapKeyIterator(TreeMapEntry<K,V> last,
                                          TreeMapEntry<K,V> fence) {
                  super(last, fence);
              }
              public K next() {
                  return prevEntry().key;
              }
              public void remove() {
                  removeDescending();
              }
              public Spliterator<K> trySplit() {
                  return null;
              }
              public void forEachRemaining(Consumer<? super K> action) {
                  while (hasNext())
                      action.accept(next());
              }
              public boolean tryAdvance(Consumer<? super K> action) {
                  if (hasNext()) {
                      action.accept(next());
                      return true;
                  }
                  return false;
              }
              public long estimateSize() {
                  return Long.MAX_VALUE;
              }
              public int characteristics() {
                  return Spliterator.DISTINCT | Spliterator.ORDERED;
              }
          }
      }
  
      /**
       * @serial include
       */
      static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
          private static final long serialVersionUID = 912986545866124060L;
  
          AscendingSubMap(TreeMap<K,V> m,
                          boolean fromStart, K lo, boolean loInclusive,
                          boolean toEnd,     K hi, boolean hiInclusive) {
              super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
          }
  
          public Comparator<? super K> comparator() {
              return m.comparator();
          }
  
          public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                          K toKey,   boolean toInclusive) {
              if (!inRange(fromKey, fromInclusive))
                  throw new IllegalArgumentException("fromKey out of range");
              if (!inRange(toKey, toInclusive))
                  throw new IllegalArgumentException("toKey out of range");
              return new AscendingSubMap<>(m,
                                           false, fromKey, fromInclusive,
                                           false, toKey,   toInclusive);
          }
  
          public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
              // BEGIN Android-changed: Fix for edge cases
              // if (!inRange(toKey, inclusive))
              if (!inRange(toKey) && !(!toEnd && m.compare(toKey, hi) == 0 &&
                  !hiInclusive && !inclusive))
              // END Android-changed: Fix for edge cases
                  throw new IllegalArgumentException("toKey out of range");
              return new AscendingSubMap<>(m,
                                           fromStart, lo,    loInclusive,
                                           false,     toKey, inclusive);
          }
  
          public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
              // BEGIN Android-changed: Fix for edge cases
              // if (!inRange(fromKey, inclusive))
              if (!inRange(fromKey) && !(!fromStart && m.compare(fromKey, lo) == 0 &&
                  !loInclusive && !inclusive))
              // END Android-changed: Fix for edge cases
                  throw new IllegalArgumentException("fromKey out of range");
              return new AscendingSubMap<>(m,
                                           false, fromKey, inclusive,
                                           toEnd, hi,      hiInclusive);
          }
  
          public NavigableMap<K,V> descendingMap() {
              NavigableMap<K,V> mv = descendingMapView;
              return (mv != null) ? mv :
                  (descendingMapView =
                   new DescendingSubMap<>(m,
                                          fromStart, lo, loInclusive,
                                          toEnd,     hi, hiInclusive));
          }
  
          Iterator<K> keyIterator() {
              return new SubMapKeyIterator(absLowest(), absHighFence());
          }
  
          Spliterator<K> keySpliterator() {
              return new SubMapKeyIterator(absLowest(), absHighFence());
          }
  
          Iterator<K> descendingKeyIterator() {
              return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
          }
  
          final class AscendingEntrySetView extends EntrySetView {
              public Iterator<Entry<K,V>> iterator() {
                  return new SubMapEntryIterator(absLowest(), absHighFence());
              }
          }
  
          public Set<Entry<K,V>> entrySet() {
              EntrySetView es = entrySetView;
              return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
          }
  
          TreeMapEntry<K,V> subLowest()       { return absLowest(); }
          TreeMapEntry<K,V> subHighest()      { return absHighest(); }
          TreeMapEntry<K,V> subCeiling(K key) { return absCeiling(key); }
          TreeMapEntry<K,V> subHigher(K key)  { return absHigher(key); }
          TreeMapEntry<K,V> subFloor(K key)   { return absFloor(key); }
          TreeMapEntry<K,V> subLower(K key)   { return absLower(key); }
      }
  
      /**
       * @serial include
       */
      static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
          private static final long serialVersionUID = 912986545866120460L;
          DescendingSubMap(TreeMap<K,V> m,
                          boolean fromStart, K lo, boolean loInclusive,
                          boolean toEnd,     K hi, boolean hiInclusive) {
              super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
          }
  
          private final Comparator<? super K> reverseComparator =
              Collections.reverseOrder(m.comparator);
  
          public Comparator<? super K> comparator() {
              return reverseComparator;
          }
  
          public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                          K toKey,   boolean toInclusive) {
              if (!inRange(fromKey, fromInclusive))
                  throw new IllegalArgumentException("fromKey out of range");
              if (!inRange(toKey, toInclusive))
                  throw new IllegalArgumentException("toKey out of range");
              return new DescendingSubMap<>(m,
                                            false, toKey,   toInclusive,
                                            false, fromKey, fromInclusive);
          }
  
          public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
              // BEGIN Android-changed: Fix for edge cases
              // if (!inRange(toKey, inclusive))
              if (!inRange(toKey) && !(!fromStart && m.compare(toKey, lo) == 0 &&
                  !loInclusive && !inclusive))
              // END Android-changed: Fix for edge cases
                  throw new IllegalArgumentException("toKey out of range");
              return new DescendingSubMap<>(m,
                                            false, toKey, inclusive,
                                            toEnd, hi,    hiInclusive);
          }
  
          public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
              // BEGIN Android-changed: Fix for edge cases
              // if (!inRange(fromKey, inclusive))
              if (!inRange(fromKey) && !(!toEnd && m.compare(fromKey, hi) == 0 &&
                  !hiInclusive && !inclusive))
              // END Android-changed: Fix for edge cases
                  throw new IllegalArgumentException("fromKey out of range");
              return new DescendingSubMap<>(m,
                                            fromStart, lo, loInclusive,
                                            false, fromKey, inclusive);
          }
  
          public NavigableMap<K,V> descendingMap() {
              NavigableMap<K,V> mv = descendingMapView;
              return (mv != null) ? mv :
                  (descendingMapView =
                   new AscendingSubMap<>(m,
                                         fromStart, lo, loInclusive,
                                         toEnd,     hi, hiInclusive));
          }
  
          Iterator<K> keyIterator() {
              return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
          }
  
          Spliterator<K> keySpliterator() {
              return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
          }
  
          Iterator<K> descendingKeyIterator() {
              return new SubMapKeyIterator(absLowest(), absHighFence());
          }
  
          final class DescendingEntrySetView extends EntrySetView {
              public Iterator<Entry<K,V>> iterator() {
                  return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
              }
          }
  
          public Set<Entry<K,V>> entrySet() {
              EntrySetView es = entrySetView;
              return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
          }
  
          TreeMapEntry<K,V> subLowest()       { return absHighest(); }
          TreeMapEntry<K,V> subHighest()      { return absLowest(); }
          TreeMapEntry<K,V> subCeiling(K key) { return absFloor(key); }
          TreeMapEntry<K,V> subHigher(K key)  { return absLower(key); }
          TreeMapEntry<K,V> subFloor(K key)   { return absCeiling(key); }
          TreeMapEntry<K,V> subLower(K key)   { return absHigher(key); }
      }
  
      /**
       * This class exists solely for the sake of serialization
       * compatibility with previous releases of TreeMap that did not
       * support NavigableMap.  It translates an old-version SubMap into
       * a new-version AscendingSubMap. This class is never otherwise
       * used.
       *
       * @serial include
       */
      private class SubMap extends AbstractMap<K,V>
          implements SortedMap<K,V>, Serializable {
          private static final long serialVersionUID = -6520786458950516097L;
          private boolean fromStart = false, toEnd = false;
          private K fromKey, toKey;
          private Object readResolve() {
              return new AscendingSubMap<>(TreeMap.this,
                                           fromStart, fromKey, true,
                                           toEnd, toKey, false);
          }
          public Set<Entry<K,V>> entrySet() { throw new InternalError(); }
          public K lastKey() { throw new InternalError(); }
          public K firstKey() { throw new InternalError(); }
          public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
          public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
          public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
          public Comparator<? super K> comparator() { throw new InternalError(); }
      }
  
  
      // Red-black mechanics
  
      private static final boolean RED   = false;
      private static final boolean BLACK = true;
  
      /**
       * Node in the Tree.  Doubles as a means to pass key-value pairs back to
       * user (see Map.Entry).
       */
      // BEGIN Android-changed: Renamed Entry -> TreeMapEntry.
      // Code references to "TreeMap.Entry" must mean Map.Entry
      //
      // This mirrors the corresponding rename of LinkedHashMap's
      // Entry->LinkedHashMapEntry.
      //
      // This is for source compatibility with earlier versions of Android.
      // Otherwise, it would hide Map.Entry.
      // END Android-changed: Renamed Entry -> TreeMapEntry.
      static final class TreeMapEntry<K,V> implements Entry<K,V> {
          K key;
          V value;
          TreeMapEntry<K,V> left;
          TreeMapEntry<K,V> right;
          TreeMapEntry<K,V> parent;
          boolean color = BLACK;
  
          /**
           * Make a new cell with given key, value, and parent, and with
           * {@code null} child links, and BLACK color.
           */
          TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) {
              this.key = key;
              this.value = value;
              this.parent = parent;
          }
  
          /**
           * Returns the key.
           *
           * @return the key
           */
          public K getKey() {
              return key;
          }
  
          /**
           * Returns the value associated with the key.
           *
           * @return the value associated with the key
           */
          public V getValue() {
              return value;
          }
  
          /**
           * Replaces the value currently associated with the key with the given
           * value.
           *
           * @return the value associated with the key before this method was
           *         called
           */
          public V setValue(V value) {
              V oldValue = this.value;
              this.value = value;
              return oldValue;
          }
  
          public boolean equals(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> e = (Entry<?,?>)o;
  
              return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
          }
  
          public int hashCode() {
              int keyHash = (key==null ? 0 : key.hashCode());
              int valueHash = (value==null ? 0 : value.hashCode());
              return keyHash ^ valueHash;
          }
  
          public String toString() {
              return key + "=" + value;
          }
      }
  
      /**
       * Returns the first Entry in the TreeMap (according to the TreeMap's
       * key-sort function).  Returns null if the TreeMap is empty.
       */
      final TreeMapEntry<K,V> getFirstEntry() {
          TreeMapEntry<K,V> p = root;
          if (p != null)
              while (p.left != null)
                  p = p.left;
          return p;
      }
  
      /**
       * Returns the last Entry in the TreeMap (according to the TreeMap's
       * key-sort function).  Returns null if the TreeMap is empty.
       */
      final TreeMapEntry<K,V> getLastEntry() {
          TreeMapEntry<K,V> p = root;
          if (p != null)
              while (p.right != null)
                  p = p.right;
          return p;
      }
  
      /**
       * Returns the successor of the specified Entry, or null if no such.
       */
      static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) {
          if (t == null)
              return null;
          else if (t.right != null) {
              TreeMapEntry<K,V> p = t.right;
              while (p.left != null)
                  p = p.left;
              return p;
          } else {
              TreeMapEntry<K,V> p = t.parent;
              TreeMapEntry<K,V> ch = t;
              while (p != null && ch == p.right) {
                  ch = p;
                  p = p.parent;
              }
              return p;
          }
      }
  
      /**
       * Returns the predecessor of the specified Entry, or null if no such.
       */
      static <K,V> TreeMapEntry<K,V> predecessor(TreeMapEntry<K,V> t) {
          if (t == null)
              return null;
          else if (t.left != null) {
              TreeMapEntry<K,V> p = t.left;
              while (p.right != null)
                  p = p.right;
              return p;
          } else {
              TreeMapEntry<K,V> p = t.parent;
              TreeMapEntry<K,V> ch = t;
              while (p != null && ch == p.left) {
                  ch = p;
                  p = p.parent;
              }
              return p;
          }
      }
  
      /**
       * Balancing operations.
       *
       * Implementations of rebalancings during insertion and deletion are
       * slightly different than the CLR version.  Rather than using dummy
       * nilnodes, we use a set of accessors that deal properly with null.  They
       * are used to avoid messiness surrounding nullness checks in the main
       * algorithms.
       */
  
      private static <K,V> boolean colorOf(TreeMapEntry<K,V> p) {
          return (p == null ? BLACK : p.color);
      }
  
      private static <K,V> TreeMapEntry<K,V> parentOf(TreeMapEntry<K,V> p) {
          return (p == null ? null: p.parent);
      }
  
      private static <K,V> void setColor(TreeMapEntry<K,V> p, boolean c) {
          if (p != null)
              p.color = c;
      }
  
      private static <K,V> TreeMapEntry<K,V> leftOf(TreeMapEntry<K,V> p) {
          return (p == null) ? null: p.left;
      }
  
      private static <K,V> TreeMapEntry<K,V> rightOf(TreeMapEntry<K,V> p) {
          return (p == null) ? null: p.right;
      }
  
      /** From CLR */
      private void rotateLeft(TreeMapEntry<K,V> p) {
          if (p != null) {
              TreeMapEntry<K,V> r = p.right;
              p.right = r.left;
              if (r.left != null)
                  r.left.parent = p;
              r.parent = p.parent;
              if (p.parent == null)
                  root = r;
              else if (p.parent.left == p)
                  p.parent.left = r;
              else
                  p.parent.right = r;
              r.left = p;
              p.parent = r;
          }
      }
  
      /** From CLR */
      private void rotateRight(TreeMapEntry<K,V> p) {
          if (p != null) {
              TreeMapEntry<K,V> l = p.left;
              p.left = l.right;
              if (l.right != null) l.right.parent = p;
              l.parent = p.parent;
              if (p.parent == null)
                  root = l;
              else if (p.parent.right == p)
                  p.parent.right = l;
              else p.parent.left = l;
              l.right = p;
              p.parent = l;
          }
      }
  
      /** From CLR */
      private void fixAfterInsertion(TreeMapEntry<K,V> x) {
          x.color = RED;
  
          while (x != null && x != root && x.parent.color == RED) {
              if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                  TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
                  if (colorOf(y) == RED) {
                      setColor(parentOf(x), BLACK);
                      setColor(y, BLACK);
                      setColor(parentOf(parentOf(x)), RED);
                      x = parentOf(parentOf(x));
                  } else {
                      if (x == rightOf(parentOf(x))) {
                          x = parentOf(x);
                          rotateLeft(x);
                      }
                      setColor(parentOf(x), BLACK);
                      setColor(parentOf(parentOf(x)), RED);
                      rotateRight(parentOf(parentOf(x)));
                  }
              } else {
                  TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));
                  if (colorOf(y) == RED) {
                      setColor(parentOf(x), BLACK);
                      setColor(y, BLACK);
                      setColor(parentOf(parentOf(x)), RED);
                      x = parentOf(parentOf(x));
                  } else {
                      if (x == leftOf(parentOf(x))) {
                          x = parentOf(x);
                          rotateRight(x);
                      }
                      setColor(parentOf(x), BLACK);
                      setColor(parentOf(parentOf(x)), RED);
                      rotateLeft(parentOf(parentOf(x)));
                  }
              }
          }
          root.color = BLACK;
      }
  
      /**
       * Delete node p, and then rebalance the tree.
       */
      private void deleteEntry(TreeMapEntry<K,V> p) {
          modCount++;
          size--;
  
          // If strictly internal, copy successor's element to p and then make p
          // point to successor.
          if (p.left != null && p.right != null) {
              TreeMapEntry<K,V> s = successor(p);
              p.key = s.key;
              p.value = s.value;
              p = s;
          } // p has 2 children
  
          // Start fixup at replacement node, if it exists.
          TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);
  
          if (replacement != null) {
              // Link replacement to parent
              replacement.parent = p.parent;
              if (p.parent == null)
                  root = replacement;
              else if (p == p.parent.left)
                  p.parent.left  = replacement;
              else
                  p.parent.right = replacement;
  
              // Null out links so they are OK to use by fixAfterDeletion.
              p.left = p.right = p.parent = null;
  
              // Fix replacement
              if (p.color == BLACK)
                  fixAfterDeletion(replacement);
          } else if (p.parent == null) { // return if we are the only node.
              root = null;
          } else { //  No children. Use self as phantom replacement and unlink.
              if (p.color == BLACK)
                  fixAfterDeletion(p);
  
              if (p.parent != null) {
                  if (p == p.parent.left)
                      p.parent.left = null;
                  else if (p == p.parent.right)
                      p.parent.right = null;
                  p.parent = null;
              }
          }
      }
  
      /** From CLR */
      private void fixAfterDeletion(TreeMapEntry<K,V> x) {
          while (x != root && colorOf(x) == BLACK) {
              if (x == leftOf(parentOf(x))) {
                  TreeMapEntry<K,V> sib = rightOf(parentOf(x));
  
                  if (colorOf(sib) == RED) {
                      setColor(sib, BLACK);
                      setColor(parentOf(x), RED);
                      rotateLeft(parentOf(x));
                      sib = rightOf(parentOf(x));
                  }
  
                  if (colorOf(leftOf(sib))  == BLACK &&
                      colorOf(rightOf(sib)) == BLACK) {
                      setColor(sib, RED);
                      x = parentOf(x);
                  } else {
                      if (colorOf(rightOf(sib)) == BLACK) {
                          setColor(leftOf(sib), BLACK);
                          setColor(sib, RED);
                          rotateRight(sib);
                          sib = rightOf(parentOf(x));
                      }
                      setColor(sib, colorOf(parentOf(x)));
                      setColor(parentOf(x), BLACK);
                      setColor(rightOf(sib), BLACK);
                      rotateLeft(parentOf(x));
                      x = root;
                  }
              } else { // symmetric
                  TreeMapEntry<K,V> sib = leftOf(parentOf(x));
  
                  if (colorOf(sib) == RED) {
                      setColor(sib, BLACK);
                      setColor(parentOf(x), RED);
                      rotateRight(parentOf(x));
                      sib = leftOf(parentOf(x));
                  }
  
                  if (colorOf(rightOf(sib)) == BLACK &&
                      colorOf(leftOf(sib)) == BLACK) {
                      setColor(sib, RED);
                      x = parentOf(x);
                  } else {
                      if (colorOf(leftOf(sib)) == BLACK) {
                          setColor(rightOf(sib), BLACK);
                          setColor(sib, RED);
                          rotateLeft(sib);
                          sib = leftOf(parentOf(x));
                      }
                      setColor(sib, colorOf(parentOf(x)));
                      setColor(parentOf(x), BLACK);
                      setColor(leftOf(sib), BLACK);
                      rotateRight(parentOf(x));
                      x = root;
                  }
              }
          }
  
          setColor(x, BLACK);
      }
  
      private static final long serialVersionUID = 919286545866124006L;
  
      /**
       * Save the state of the {@code TreeMap} instance to a stream (i.e.,
       * serialize it).
       *
       * @serialData The <em>size</em> of the TreeMap (the number of key-value
       *             mappings) is emitted (int), followed by the key (Object)
       *             and value (Object) for each key-value mapping represented
       *             by the TreeMap. The key-value mappings are emitted in
       *             key-order (as determined by the TreeMap's Comparator,
       *             or by the keys' natural ordering if the TreeMap has no
       *             Comparator).
       */
      private void writeObject(java.io.ObjectOutputStream s)
          throws java.io.IOException {
          // Write out the Comparator and any hidden stuff
          s.defaultWriteObject();
  
          // Write out size (number of Mappings)
          s.writeInt(size);
  
          // Write out keys and values (alternating)
          for (Iterator<Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
              Entry<K,V> e = i.next();
              s.writeObject(e.getKey());
              s.writeObject(e.getValue());
          }
      }
  
      /**
       * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
       * deserialize it).
       */
      private void readObject(final java.io.ObjectInputStream s)
          throws java.io.IOException, ClassNotFoundException {
          // Read in the Comparator and any hidden stuff
          s.defaultReadObject();
  
          // Read in size
          int size = s.readInt();
  
          buildFromSorted(size, null, s, null);
      }
  
      /** Intended to be called only from TreeSet.readObject */
      void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
          throws java.io.IOException, ClassNotFoundException {
          buildFromSorted(size, null, s, defaultVal);
      }
  
      /** Intended to be called only from TreeSet.addAll */
      void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
          try {
              buildFromSorted(set.size(), set.iterator(), null, defaultVal);
          } catch (java.io.IOException cannotHappen) {
          } catch (ClassNotFoundException cannotHappen) {
          }
      }
  
  
      /**
       * Linear time tree building algorithm from sorted data.  Can accept keys
       * and/or values from iterator or stream. This leads to too many
       * parameters, but seems better than alternatives.  The four formats
       * that this method accepts are:
       *
       *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).
       *    2) An iterator of keys.         (it != null, defaultVal != null).
       *    3) A stream of alternating serialized keys and values.
       *                                   (it == null, defaultVal == null).
       *    4) A stream of serialized keys. (it == null, defaultVal != null).
       *
       * It is assumed that the comparator of the TreeMap is already set prior
       * to calling this method.
       *
       * @param size the number of keys (or key-value pairs) to be read from
       *        the iterator or stream
       * @param it If non-null, new entries are created from entries
       *        or keys read from this iterator.
       * @param str If non-null, new entries are created from keys and
       *        possibly values read from this stream in serialized form.
       *        Exactly one of it and str should be non-null.
       * @param defaultVal if non-null, this default value is used for
       *        each value in the map.  If null, each value is read from
       *        iterator or stream, as described above.
       * @throws java.io.IOException propagated from stream reads. This cannot
       *         occur if str is null.
       * @throws ClassNotFoundException propagated from readObject.
       *         This cannot occur if str is null.
       */
      private void buildFromSorted(int size, Iterator<?> it,
                                   java.io.ObjectInputStream str,
                                   V defaultVal)
          throws  java.io.IOException, ClassNotFoundException {
          this.size = size;
          root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                                 it, str, defaultVal);
      }
  
      /**
       * Recursive "helper method" that does the real work of the
       * previous method.  Identically named parameters have
       * identical definitions.  Additional parameters are documented below.
       * It is assumed that the comparator and size fields of the TreeMap are
       * already set prior to calling this method.  (It ignores both fields.)
       *
       * @param level the current level of tree. Initial call should be 0.
       * @param lo the first element index of this subtree. Initial should be 0.
       * @param hi the last element index of this subtree.  Initial should be
       *        size-1.
       * @param redLevel the level at which nodes should be red.
       *        Must be equal to computeRedLevel for tree of this size.
       */
      @SuppressWarnings("unchecked")
      private final TreeMapEntry<K,V> buildFromSorted(int level, int lo, int hi,
                                               int redLevel,
                                               Iterator<?> it,
                                               java.io.ObjectInputStream str,
                                               V defaultVal)
          throws  java.io.IOException, ClassNotFoundException {
          /*
           * Strategy: The root is the middlemost element. To get to it, we
           * have to first recursively construct the entire left subtree,
           * so as to grab all of its elements. We can then proceed with right
           * subtree.
           *
           * The lo and hi arguments are the minimum and maximum
           * indices to pull out of the iterator or stream for current subtree.
           * They are not actually indexed, we just proceed sequentially,
           * ensuring that items are extracted in corresponding order.
           */
  
          if (hi < lo) return null;
  
          int mid = (lo + hi) >>> 1;
  
          TreeMapEntry<K,V> left  = null;
          if (lo < mid)
              left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                                     it, str, defaultVal);
  
          // extract key and/or value from iterator or stream
          K key;
          V value;
          if (it != null) {
              if (defaultVal==null) {
                  Entry<?,?> entry = (Entry<?,?>)it.next();
                  key = (K)entry.getKey();
                  value = (V)entry.getValue();
              } else {
                  key = (K)it.next();
                  value = defaultVal;
              }
          } else { // use stream
              key = (K) str.readObject();
              value = (defaultVal != null ? defaultVal : (V) str.readObject());
          }
  
          TreeMapEntry<K,V> middle =  new TreeMapEntry<>(key, value, null);
  
          // color nodes in non-full bottommost level red
          if (level == redLevel)
              middle.color = RED;
  
          if (left != null) {
              middle.left = left;
              left.parent = middle;
          }
  
          if (mid < hi) {
              TreeMapEntry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                                 it, str, defaultVal);
              middle.right = right;
              right.parent = middle;
          }
  
          return middle;
      }
  
      /**
       * Find the level down to which to assign all nodes BLACK.  This is the
       * last `full' level of the complete binary tree produced by
       * buildTree. The remaining nodes are colored RED. (This makes a `nice'
       * set of color assignments wrt future insertions.) This level number is
       * computed by finding the number of splits needed to reach the zeroeth
       * node.  (The answer is ~lg(N), but in any case must be computed by same
       * quick O(lg(N)) loop.)
       */
      private static int computeRedLevel(int sz) {
          int level = 0;
          for (int m = sz - 1; m >= 0; m = m / 2 - 1)
              level++;
          return level;
      }
  
      /**
       * Currently, we support Spliterator-based versions only for the
       * full map, in either plain of descending form, otherwise relying
       * on defaults because size estimation for submaps would dominate
       * costs. The type tests needed to check these for key views are
       * not very nice but avoid disrupting existing class
       * structures. Callers must use plain default spliterators if this
       * returns null.
       */
      static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
          if (m instanceof TreeMap) {
              @SuppressWarnings("unchecked") TreeMap<K,Object> t =
                  (TreeMap<K,Object>) m;
              return t.keySpliterator();
          }
          if (m instanceof DescendingSubMap) {
              @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
                  (DescendingSubMap<K,?>) m;
              TreeMap<K,?> tm = dm.m;
              if (dm == tm.descendingMap) {
                  @SuppressWarnings("unchecked") TreeMap<K,Object> t =
                      (TreeMap<K,Object>) tm;
                  return t.descendingKeySpliterator();
              }
          }
          @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
              (NavigableSubMap<K,?>) m;
          return sm.keySpliterator();
      }
  
      final Spliterator<K> keySpliterator() {
          return new KeySpliterator<K,V>(this, null, null, 0, -1, 0);
      }
  
      final Spliterator<K> descendingKeySpliterator() {
          return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0);
      }
  
      /**
       * Base class for spliterators.  Iteration starts at a given
       * origin and continues up to but not including a given fence (or
       * null for end).  At top-level, for ascending cases, the first
       * split uses the root as left-fence/right-origin. From there,
       * right-hand splits replace the current fence with its left
       * child, also serving as origin for the split-off spliterator.
       * Left-hands are symmetric. Descending versions place the origin
       * at the end and invert ascending split rules.  This base class
       * is non-commital about directionality, or whether the top-level
       * spliterator covers the whole tree. This means that the actual
       * split mechanics are located in subclasses. Some of the subclass
       * trySplit methods are identical (except for return types), but
       * not nicely factorable.
       *
       * Currently, subclass versions exist only for the full map
       * (including descending keys via its descendingMap).  Others are
       * possible but currently not worthwhile because submaps require
       * O(n) computations to determine size, which substantially limits
       * potential speed-ups of using custom Spliterators versus default
       * mechanics.
       *
       * To boostrap initialization, external constructors use
       * negative size estimates: -1 for ascend, -2 for descend.
       */
      static class TreeMapSpliterator<K,V> {
          final TreeMap<K,V> tree;
          TreeMapEntry<K,V> current; // traverser; initially first node in range
          TreeMapEntry<K,V> fence;   // one past last, or null
          int side;                   // 0: top, -1: is a left split, +1: right
          int est;                    // size estimate (exact only for top-level)
          int expectedModCount;       // for CME checks
  
          TreeMapSpliterator(TreeMap<K,V> tree,
                             TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence,
                             int side, int est, int expectedModCount) {
              this.tree = tree;
              this.current = origin;
              this.fence = fence;
              this.side = side;
              this.est = est;
              this.expectedModCount = expectedModCount;
          }
  
          final int getEstimate() { // force initialization
              int s; TreeMap<K,V> t;
              if ((s = est) < 0) {
                  if ((t = tree) != null) {
                      current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
                      s = est = t.size;
                      expectedModCount = t.modCount;
                  }
                  else
                      s = est = 0;
              }
              return s;
          }
  
          public final long estimateSize() {
              return (long)getEstimate();
          }
      }
  
      static final class KeySpliterator<K,V>
          extends TreeMapSpliterator<K,V>
          implements Spliterator<K> {
          KeySpliterator(TreeMap<K,V> tree,
                         TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence,
                         int side, int est, int expectedModCount) {
              super(tree, origin, fence, side, est, expectedModCount);
          }
  
          public KeySpliterator<K,V> trySplit() {
              if (est < 0)
                  getEstimate(); // force initialization
              int d = side;
              TreeMapEntry<K,V> e = current, f = fence,
                  s = ((e == null || e == f) ? null :      // empty
                       (d == 0)              ? tree.root : // was top
                       (d >  0)              ? e.right :   // was right
                       (d <  0 && f != null) ? f.left :    // was left
                       null);
              if (s != null && s != e && s != f &&
                  tree.compare(e.key, s.key) < 0) {        // e not already past s
                  side = 1;
                  return new KeySpliterator<>
                      (tree, e, current = s, -1, est >>>= 1, expectedModCount);
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super K> action) {
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              TreeMapEntry<K,V> f = fence, e, p, pl;
              if ((e = current) != null && e != f) {
                  current = f; // exhaust
                  do {
                      action.accept(e.key);
                      if ((p = e.right) != null) {
                          while ((pl = p.left) != null)
                              p = pl;
                      }
                      else {
                          while ((p = e.parent) != null && e == p.right)
                              e = p;
                      }
                  } while ((e = p) != null && e != f);
                  if (tree.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
              }
          }
  
          public boolean tryAdvance(Consumer<? super K> action) {
              TreeMapEntry<K,V> e;
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              if ((e = current) == null || e == fence)
                  return false;
              current = successor(e);
              action.accept(e.key);
              if (tree.modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              return true;
          }
  
          public int characteristics() {
              return (side == 0 ? Spliterator.SIZED : 0) |
                  Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
          }
  
          public final Comparator<? super K>  getComparator() {
              return tree.comparator;
          }
  
      }
  
      static final class DescendingKeySpliterator<K,V>
          extends TreeMapSpliterator<K,V>
          implements Spliterator<K> {
          DescendingKeySpliterator(TreeMap<K,V> tree,
                                   TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence,
                                   int side, int est, int expectedModCount) {
              super(tree, origin, fence, side, est, expectedModCount);
          }
  
          public DescendingKeySpliterator<K,V> trySplit() {
              if (est < 0)
                  getEstimate(); // force initialization
              int d = side;
              TreeMapEntry<K,V> e = current, f = fence,
                      s = ((e == null || e == f) ? null :      // empty
                           (d == 0)              ? tree.root : // was top
                           (d <  0)              ? e.left :    // was left
                           (d >  0 && f != null) ? f.right :   // was right
                           null);
              if (s != null && s != e && s != f &&
                  tree.compare(e.key, s.key) > 0) {       // e not already past s
                  side = 1;
                  return new DescendingKeySpliterator<>
                          (tree, e, current = s, -1, est >>>= 1, expectedModCount);
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super K> action) {
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              TreeMapEntry<K,V> f = fence, e, p, pr;
              if ((e = current) != null && e != f) {
                  current = f; // exhaust
                  do {
                      action.accept(e.key);
                      if ((p = e.left) != null) {
                          while ((pr = p.right) != null)
                              p = pr;
                      }
                      else {
                          while ((p = e.parent) != null && e == p.left)
                              e = p;
                      }
                  } while ((e = p) != null && e != f);
                  if (tree.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
              }
          }
  
          public boolean tryAdvance(Consumer<? super K> action) {
              TreeMapEntry<K,V> e;
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              if ((e = current) == null || e == fence)
                  return false;
              current = predecessor(e);
              action.accept(e.key);
              if (tree.modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              return true;
          }
  
          public int characteristics() {
              return (side == 0 ? Spliterator.SIZED : 0) |
                  Spliterator.DISTINCT | Spliterator.ORDERED;
          }
      }
  
      static final class ValueSpliterator<K,V>
              extends TreeMapSpliterator<K,V>
              implements Spliterator<V> {
          ValueSpliterator(TreeMap<K,V> tree,
                           TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence,
                           int side, int est, int expectedModCount) {
              super(tree, origin, fence, side, est, expectedModCount);
          }
  
          public ValueSpliterator<K,V> trySplit() {
              if (est < 0)
                  getEstimate(); // force initialization
              int d = side;
              TreeMapEntry<K,V> e = current, f = fence,
                      s = ((e == null || e == f) ? null :      // empty
                           (d == 0)              ? tree.root : // was top
                           (d >  0)              ? e.right :   // was right
                           (d <  0 && f != null) ? f.left :    // was left
                           null);
              if (s != null && s != e && s != f &&
                  tree.compare(e.key, s.key) < 0) {        // e not already past s
                  side = 1;
                  return new ValueSpliterator<>
                          (tree, e, current = s, -1, est >>>= 1, expectedModCount);
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super V> action) {
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              TreeMapEntry<K,V> f = fence, e, p, pl;
              if ((e = current) != null && e != f) {
                  current = f; // exhaust
                  do {
                      action.accept(e.value);
                      if ((p = e.right) != null) {
                          while ((pl = p.left) != null)
                              p = pl;
                      }
                      else {
                          while ((p = e.parent) != null && e == p.right)
                              e = p;
                      }
                  } while ((e = p) != null && e != f);
                  if (tree.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
              }
          }
  
          public boolean tryAdvance(Consumer<? super V> action) {
              TreeMapEntry<K,V> e;
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              if ((e = current) == null || e == fence)
                  return false;
              current = successor(e);
              action.accept(e.value);
              if (tree.modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              return true;
          }
  
          public int characteristics() {
              return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.ORDERED;
          }
      }
  
      static final class EntrySpliterator<K,V>
          extends TreeMapSpliterator<K,V>
          implements Spliterator<Entry<K,V>> {
          EntrySpliterator(TreeMap<K,V> tree,
                           TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence,
                           int side, int est, int expectedModCount) {
              super(tree, origin, fence, side, est, expectedModCount);
          }
  
          public EntrySpliterator<K,V> trySplit() {
              if (est < 0)
                  getEstimate(); // force initialization
              int d = side;
              TreeMapEntry<K,V> e = current, f = fence,
                      s = ((e == null || e == f) ? null :      // empty
                           (d == 0)              ? tree.root : // was top
                           (d >  0)              ? e.right :   // was right
                           (d <  0 && f != null) ? f.left :    // was left
                           null);
              if (s != null && s != e && s != f &&
                  tree.compare(e.key, s.key) < 0) {        // e not already past s
                  side = 1;
                  return new EntrySpliterator<>
                          (tree, e, current = s, -1, est >>>= 1, expectedModCount);
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super Entry<K, V>> action) {
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              TreeMapEntry<K,V> f = fence, e, p, pl;
              if ((e = current) != null && e != f) {
                  current = f; // exhaust
                  do {
                      action.accept(e);
                      if ((p = e.right) != null) {
                          while ((pl = p.left) != null)
                              p = pl;
                      }
                      else {
                          while ((p = e.parent) != null && e == p.right)
                              e = p;
                      }
                  } while ((e = p) != null && e != f);
                  if (tree.modCount != expectedModCount)
                      throw new ConcurrentModificationException();
              }
          }
  
          public boolean tryAdvance(Consumer<? super Entry<K,V>> action) {
              TreeMapEntry<K,V> e;
              if (action == null)
                  throw new NullPointerException();
              if (est < 0)
                  getEstimate(); // force initialization
              if ((e = current) == null || e == fence)
                  return false;
              current = successor(e);
              action.accept(e);
              if (tree.modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              return true;
          }
  
          public int characteristics() {
              return (side == 0 ? Spliterator.SIZED : 0) |
                      Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
          }
  
          @Override
          public Comparator<Entry<K, V>> getComparator() {
              // Adapt or create a key-based comparator
              if (tree.comparator != null) {
                  return Entry.comparingByKey(tree.comparator);
              }
              else {
                  return (Comparator<Entry<K, V>> & Serializable) (e1, e2) -> {
                      @SuppressWarnings("unchecked")
                      Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
                      return k1.compareTo(e2.getKey());
                  };
              }
          }
      }
  }
  