package com.dream.tree;//package fanrui.study.tree;
///*
// * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.
// * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// *
// */
//
////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, java.io.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 Entry<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 (Entry<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) {
//        Entry<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 Entry<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;
//        Entry<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 Entry<K,V> getEntryUsingComparator(Object key) {
//        @SuppressWarnings("unchecked")
//        K k = (K) key;
//        Comparator<? super K> cpr = comparator;
//        if (cpr != null) {
//            Entry<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 Entry<K,V> getCeilingEntry(K key) {
//        Entry<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 {
//                    Entry<K,V> parent = p.parent;
//                    Entry<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 Entry<K,V> getFloorEntry(K key) {
//        Entry<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 {
//                    Entry<K,V> parent = p.parent;
//                    Entry<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 Entry<K,V> getHigherEntry(K key) {
//        Entry<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 {
//                    Entry<K,V> parent = p.parent;
//                    Entry<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 Entry<K,V> getLowerEntry(K key) {
//        Entry<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 {
//                    Entry<K,V> parent = p.parent;
//                    Entry<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) {
//        Entry<K,V> t = root;
//        if (t == null) {
//            compare(key, key); // type (and possibly null) check
//
//            root = new Entry<>(key, value, null);
//            size = 1;
//            modCount++;
//            return null;
//        }
//        int cmp;
//        Entry<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);
//        }
//        Entry<K,V> e = new Entry<>(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) {
//        Entry<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 Map.Entry<K,V> firstEntry() {
//        return exportEntry(getFirstEntry());
//    }
//
//    /**
//     * @since 1.6
//     */
//    public Map.Entry<K,V> lastEntry() {
//        return exportEntry(getLastEntry());
//    }
//
//    /**
//     * @since 1.6
//     */
//    public Map.Entry<K,V> pollFirstEntry() {
//        Entry<K,V> p = getFirstEntry();
//        Map.Entry<K,V> result = exportEntry(p);
//        if (p != null)
//            deleteEntry(p);
//        return result;
//    }
//
//    /**
//     * @since 1.6
//     */
//    public Map.Entry<K,V> pollLastEntry() {
//        Entry<K,V> p = getLastEntry();
//        Map.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 Map.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 Map.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 Map.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 Map.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 java.util.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<Map.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) {
//        Entry<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) {
//        Entry<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 (Entry<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 (Entry<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 (Entry<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<Map.Entry<K,V>> {
//        public Iterator<Map.Entry<K,V>> iterator() {
//            return new EntryIterator(getFirstEntry());
//        }
//
//        public boolean contains(Object o) {
//            if (!(o instanceof Map.Entry))
//                return false;
//            Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
//            Object value = entry.getValue();
//            Entry<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;
//            Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
//            Object value = entry.getValue();
//            Entry<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<Map.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 ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
//        }
//
//        public Iterator<E> descendingIterator() {
//            if (m instanceof TreeMap)
//                return ((TreeMap<E,?>)m).descendingKeyIterator();
//            else
//                return ((TreeMap.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() {
//            Map.Entry<E,?> e = m.pollFirstEntry();
//            return (e == null) ? null : e.getKey();
//        }
//        public E pollLast() {
//            Map.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> {
//        Entry<K,V> next;
//        Entry<K,V> lastReturned;
//        int expectedModCount;
//
//        PrivateEntryIterator(Entry<K,V> first) {
//            expectedModCount = modCount;
//            lastReturned = null;
//            next = first;
//        }
//
//        public final boolean hasNext() {
//            return next != null;
//        }
//
//        final Entry<K,V> nextEntry() {
//            Entry<K,V> e = next;
//            if (e == null)
//                throw new NoSuchElementException();
//            if (modCount != expectedModCount)
//                throw new ConcurrentModificationException();
//            next = successor(e);
//            lastReturned = e;
//            return e;
//        }
//
//        final Entry<K,V> prevEntry() {
//            Entry<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<Map.Entry<K,V>> {
//        EntryIterator(Entry<K,V> first) {
//            super(first);
//        }
//        public Map.Entry<K,V> next() {
//            return nextEntry();
//        }
//    }
//
//    final class ValueIterator extends PrivateEntryIterator<V> {
//        ValueIterator(Entry<K,V> first) {
//            super(first);
//        }
//        public V next() {
//            return nextEntry().value;
//        }
//    }
//
//    final class KeyIterator extends PrivateEntryIterator<K> {
//        KeyIterator(Entry<K,V> first) {
//            super(first);
//        }
//        public K next() {
//            return nextEntry().key;
//        }
//    }
//
//    final class DescendingKeyIterator extends PrivateEntryIterator<K> {
//        DescendingKeyIterator(Entry<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> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
//        return (e == null) ? null :
//                new AbstractMap.SimpleImmutableEntry<>(e);
//    }
//
//    /**
//     * Return key for entry, or null if null
//     */
//    static <K,V> K keyOrNull(TreeMap.Entry<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(Entry<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>, java.io.Serializable {
//        private static final long serialVersionUID = -2102997345730753016L;
//        /**
//         * 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 TreeMap.Entry<K,V> absLowest() {
//            TreeMap.Entry<K,V> e =
//                    (fromStart ?  m.getFirstEntry() :
//                            (loInclusive ? m.getCeilingEntry(lo) :
//                                    m.getHigherEntry(lo)));
//            return (e == null || tooHigh(e.key)) ? null : e;
//        }
//
//        final TreeMap.Entry<K,V> absHighest() {
//            TreeMap.Entry<K,V> e =
//                    (toEnd ?  m.getLastEntry() :
//                            (hiInclusive ?  m.getFloorEntry(hi) :
//                                    m.getLowerEntry(hi)));
//            return (e == null || tooLow(e.key)) ? null : e;
//        }
//
//        final TreeMap.Entry<K,V> absCeiling(K key) {
//            if (tooLow(key))
//                return absLowest();
//            TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
//            return (e == null || tooHigh(e.key)) ? null : e;
//        }
//
//        final TreeMap.Entry<K,V> absHigher(K key) {
//            if (tooLow(key))
//                return absLowest();
//            TreeMap.Entry<K,V> e = m.getHigherEntry(key);
//            return (e == null || tooHigh(e.key)) ? null : e;
//        }
//
//        final TreeMap.Entry<K,V> absFloor(K key) {
//            if (tooHigh(key))
//                return absHighest();
//            TreeMap.Entry<K,V> e = m.getFloorEntry(key);
//            return (e == null || tooLow(e.key)) ? null : e;
//        }
//
//        final TreeMap.Entry<K,V> absLower(K key) {
//            if (tooHigh(key))
//                return absHighest();
//            TreeMap.Entry<K,V> e = m.getLowerEntry(key);
//            return (e == null || tooLow(e.key)) ? null : e;
//        }
//
//        /** Returns the absolute high fence for ascending traversal */
//        final TreeMap.Entry<K,V> absHighFence() {
//            return (toEnd ? null : (hiInclusive ?
//                    m.getHigherEntry(hi) :
//                    m.getCeilingEntry(hi)));
//        }
//
//        /** Return the absolute low fence for descending traversal  */
//        final TreeMap.Entry<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 TreeMap.Entry<K,V> subLowest();
//        abstract TreeMap.Entry<K,V> subHighest();
//        abstract TreeMap.Entry<K,V> subCeiling(K key);
//        abstract TreeMap.Entry<K,V> subHigher(K key);
//        abstract TreeMap.Entry<K,V> subFloor(K key);
//        abstract TreeMap.Entry<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 Map.Entry<K,V> ceilingEntry(K key) {
//            return exportEntry(subCeiling(key));
//        }
//
//        public final K ceilingKey(K key) {
//            return keyOrNull(subCeiling(key));
//        }
//
//        public final Map.Entry<K,V> higherEntry(K key) {
//            return exportEntry(subHigher(key));
//        }
//
//        public final K higherKey(K key) {
//            return keyOrNull(subHigher(key));
//        }
//
//        public final Map.Entry<K,V> floorEntry(K key) {
//            return exportEntry(subFloor(key));
//        }
//
//        public final K floorKey(K key) {
//            return keyOrNull(subFloor(key));
//        }
//
//        public final Map.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 Map.Entry<K,V> firstEntry() {
//            return exportEntry(subLowest());
//        }
//
//        public final Map.Entry<K,V> lastEntry() {
//            return exportEntry(subHighest());
//        }
//
//        public final Map.Entry<K,V> pollFirstEntry() {
//            TreeMap.Entry<K,V> e = subLowest();
//            Map.Entry<K,V> result = exportEntry(e);
//            if (e != null)
//                m.deleteEntry(e);
//            return result;
//        }
//
//        public final Map.Entry<K,V> pollLastEntry() {
//            TreeMap.Entry<K,V> e = subHighest();
//            Map.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 TreeMap.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<Map.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() {
//                TreeMap.Entry<K,V> n = absLowest();
//                return n == null || tooHigh(n.key);
//            }
//
//            public boolean contains(Object o) {
//                if (!(o instanceof Map.Entry))
//                    return false;
//                Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
//                Object key = entry.getKey();
//                if (!inRange(key))
//                    return false;
//                TreeMap.Entry<?,?> node = m.getEntry(key);
//                return node != null &&
//                        valEquals(node.getValue(), entry.getValue());
//            }
//
//            public boolean remove(Object o) {
//                if (!(o instanceof Map.Entry))
//                    return false;
//                Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
//                Object key = entry.getKey();
//                if (!inRange(key))
//                    return false;
//                TreeMap.Entry<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> {
//            TreeMap.Entry<K,V> lastReturned;
//            TreeMap.Entry<K,V> next;
//            final Object fenceKey;
//            int expectedModCount;
//
//            SubMapIterator(TreeMap.Entry<K,V> first,
//                           TreeMap.Entry<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 TreeMap.Entry<K,V> nextEntry() {
//                TreeMap.Entry<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 TreeMap.Entry<K,V> prevEntry() {
//                TreeMap.Entry<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<Map.Entry<K,V>> {
//            SubMapEntryIterator(TreeMap.Entry<K,V> first,
//                                TreeMap.Entry<K,V> fence) {
//                super(first, fence);
//            }
//            public Map.Entry<K,V> next() {
//                return nextEntry();
//            }
//            public void remove() {
//                removeAscending();
//            }
//        }
//
//        final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
//            DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
//                                          TreeMap.Entry<K,V> fence) {
//                super(last, fence);
//            }
//
//            public Map.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(TreeMap.Entry<K,V> first,
//                              TreeMap.Entry<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(TreeMap.Entry<K,V> last,
//                                        TreeMap.Entry<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) {
//            if (!inRange(toKey, inclusive))
//                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) {
//            if (!inRange(fromKey, inclusive))
//                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<Map.Entry<K,V>> iterator() {
//                return new SubMapEntryIterator(absLowest(), absHighFence());
//            }
//        }
//
//        public Set<Map.Entry<K,V>> entrySet() {
//            EntrySetView es = entrySetView;
//            return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
//        }
//
//        TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
//        TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
//        TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
//        TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
//        TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
//        TreeMap.Entry<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) {
//            if (!inRange(toKey, inclusive))
//                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) {
//            if (!inRange(fromKey, inclusive))
//                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<Map.Entry<K,V>> iterator() {
//                return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
//            }
//        }
//
//        public Set<Map.Entry<K,V>> entrySet() {
//            EntrySetView es = entrySetView;
//            return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
//        }
//
//        TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
//        TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
//        TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
//        TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
//        TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
//        TreeMap.Entry<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>, java.io.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<Map.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).
//     */
//
//    static final class Entry<K,V> implements Map.Entry<K,V> {
//        K key;
//        V value;
//        Entry<K,V> left;
//        Entry<K,V> right;
//        Entry<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.
//         */
//        Entry(K key, V value, Entry<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;
//            Map.Entry<?,?> e = (Map.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 Entry<K,V> getFirstEntry() {
//        Entry<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 Entry<K,V> getLastEntry() {
//        Entry<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> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//        if (t == null)
//            return null;
//        else if (t.right != null) {
//            Entry<K,V> p = t.right;
//            while (p.left != null)
//                p = p.left;
//            return p;
//        } else {
//            Entry<K,V> p = t.parent;
//            Entry<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> Entry<K,V> predecessor(Entry<K,V> t) {
//        if (t == null)
//            return null;
//        else if (t.left != null) {
//            Entry<K,V> p = t.left;
//            while (p.right != null)
//                p = p.right;
//            return p;
//        } else {
//            Entry<K,V> p = t.parent;
//            Entry<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(Entry<K,V> p) {
//        return (p == null ? BLACK : p.color);
//    }
//
//    private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
//        return (p == null ? null: p.parent);
//    }
//
//    private static <K,V> void setColor(Entry<K,V> p, boolean c) {
//        if (p != null)
//            p.color = c;
//    }
//
//    private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
//        return (p == null) ? null: p.left;
//    }
//
//    private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
//        return (p == null) ? null: p.right;
//    }
//
//    /** From CLR */
//    private void rotateLeft(Entry<K,V> p) {
//        if (p != null) {
//            Entry<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(Entry<K,V> p) {
//        if (p != null) {
//            Entry<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(Entry<K,V> x) {
//        // x 为关注节点
//        x.color = RED;
//        while (x != null && x != root && x.parent.color == RED) {
//            // 关注节点的父节点是爷爷节点左孩子
//            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//                // y表示关注节点的叔叔节点
//                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//                // 看叔叔节点的脸色
//                // 叔叔为 红色 case1
//                if (colorOf(y) == RED) {
//                    // 变色
//                    setColor(parentOf(x), BLACK);
//                    setColor(y, BLACK);
//                    setColor(parentOf(parentOf(x)), RED);
//                    // 关注节点变成 x 的祖父节点，向上回溯
//                    x = parentOf(parentOf(x));
//                // 叔叔节点 是黑色
//                } else {
//                    // 关注节点 是其父节点 的右子节点 case 2
//                    if (x == rightOf(parentOf(x))) {
//                        // 关注节点变成 x 的父节点
//                        x = parentOf(x);
//                        // 围绕新的关注节点 左旋
//                        rotateLeft(x);
//                        // 关注节点已变成了父节点的左子节点，跳至 case3
//                    }
//                    // 叔叔节点 是黑色，关注节点 是其父节点 的左子节点，case3
//                    // 将关注节点 的父节点 变黑，祖父节点变红
//                    setColor(parentOf(x), BLACK);
//                    setColor(parentOf(parentOf(x)), RED);
//                    // 围绕 祖父节点 右旋
//                    rotateRight(parentOf(parentOf(x)));
//                    // 运行到这里 已经满足红黑树性质了，要结束循环了
//                }
//            // 关注节点的父节点是爷爷节点 右孩子
//            } else {
//                Entry<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(Entry<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) {
//            Entry<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.
//        Entry<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(Entry<K,V> x) {
//        while (x != root && colorOf(x) == BLACK) {
//            if (x == leftOf(parentOf(x))) {
//                Entry<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
//                Entry<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<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
//            Map.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 Entry<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;
//
//        Entry<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) {
//                Map.Entry<?,?> entry = (Map.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());
//        }
//
//        Entry<K,V> middle =  new Entry<>(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) {
//            Entry<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;
//        TreeMap.Entry<K,V> current; // traverser; initially first node in range
//        TreeMap.Entry<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,
//                           TreeMap.Entry<K,V> origin, TreeMap.Entry<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,
//                       TreeMap.Entry<K,V> origin, TreeMap.Entry<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;
//            TreeMap.Entry<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
//            TreeMap.Entry<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) {
//            TreeMap.Entry<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,
//                                 TreeMap.Entry<K,V> origin, TreeMap.Entry<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;
//            TreeMap.Entry<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
//            TreeMap.Entry<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) {
//            TreeMap.Entry<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,
//                         TreeMap.Entry<K,V> origin, TreeMap.Entry<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;
//            TreeMap.Entry<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
//            TreeMap.Entry<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) {
//            TreeMap.Entry<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<Map.Entry<K,V>> {
//        EntrySpliterator(TreeMap<K,V> tree,
//                         TreeMap.Entry<K,V> origin, TreeMap.Entry<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;
//            TreeMap.Entry<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 Map.Entry<K, V>> action) {
//            if (action == null)
//                throw new NullPointerException();
//            if (est < 0)
//                getEstimate(); // force initialization
//            TreeMap.Entry<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 Map.Entry<K,V>> action) {
//            TreeMap.Entry<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<Map.Entry<K, V>> getComparator() {
//            // Adapt or create a key-based comparator
//            if (tree.comparator != null) {
//                return Map.Entry.comparingByKey(tree.comparator);
//            }
//            else {
//                return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> {
//                    @SuppressWarnings("unchecked")
//                    Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
//                    return k1.compareTo(e2.getKey());
//                };
//            }
//        }
//    }
//}
