Quelle TreeMap.java

Sprache: JAVA

/*
* Copyright (c) 1997, 2022, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/

package java.util;

import java.io.Serializable;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

/**
* 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.
*
* 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 Introduction to Algorithms.
*
* Note that the ordering maintained by a tree map, like any sorted map, and
* whether or not an explicit comparator is provided, must be consistent
* with {@code equals} if this sorted map is to correctly implement the
* {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
* precise definition of consistent with equals.) 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 is well-defined even if its ordering is
* inconsistent with {@code equals}; it just fails to obey the general contract
* of the {@code Map} interface.
*
* Note that this implementation is not synchronized.
* If multiple threads access a map concurrently, and at least one of the
* threads modifies the map structurally, it must 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>
*
* The iterators returned by the {@code iterator} method of the collections
* returned by all of this class's "collection view methods" are
* fail-fast: 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.
*
* 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: the fail-fast behavior of iterators
* should be used only to detect bugs.
*
* 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 not support the {@code Entry.setValue}
* method. (Note however that it is possible to change mappings in the
* associated map using {@code put}.)
*
* This class is a member of the
* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
* 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
 */
 @SuppressWarnings("serial") // Conditionally serializable
 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
 * mutually comparable: {@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 mutually
 * comparable 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 natural ordering of its keys.
 * All keys inserted into the new map must implement the {@link
 * Comparable} interface. Furthermore, all such keys must be
 * mutually comparable: {@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 | 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.
 *
 * 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.)
 *
 * A return value of {@code null} does not necessarily
 * 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) {
 if (Objects.equals(comparator, ((SortedMap<?,?>)map).comparator())) {
 ++modCount;
 try {
 buildFromSorted(mapSize, map.entrySet().iterator(),
 null, null);
 } catch (java.io.IOException | 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);
 Objects.requireNonNull(key);
 @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) {
 return put(key, value, true);
 }

 @Override
 public V putIfAbsent(K key, V value) {
 return put(key, value, false);
 }

 /**
 * {@inheritDoc}
 *
 * This method will, on a best-effort basis, throw a
 * {@link ConcurrentModificationException} if it is detected that the
 * mapping function modifies this map during computation.
 *
 * @throws ConcurrentModificationException if it is detected that the
 * mapping function modified this map
 */
 @Override
 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
 Objects.requireNonNull(mappingFunction);
 V newValue;
 Entry<K,V> t = root;
 if (t == null) {
 newValue = callMappingFunctionWithCheck(key, mappingFunction);
 if (newValue != null) {
 addEntryToEmptyMap(key, newValue);
 return newValue;
 } else {
 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 {
 if (t.value == null) {
 t.value = callMappingFunctionWithCheck(key, mappingFunction);
 }
 return t.value;
 }
 } while (t != null);
 } else {
 Objects.requireNonNull(key);
 @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 {
 if (t.value == null) {
 t.value = callMappingFunctionWithCheck(key, mappingFunction);
 }
 return t.value;
 }
 } while (t != null);
 }
 newValue = callMappingFunctionWithCheck(key, mappingFunction);
 if (newValue != null) {
 addEntry(key, newValue, parent, cmp < 0);
 return newValue;
 }
 return null;
 }

 /**
 * {@inheritDoc}
 *
 * This method will, on a best-effort basis, throw a
 * {@link ConcurrentModificationException} if it is detected that the
 * remapping function modifies this map during computation.
 *
 * @throws ConcurrentModificationException if it is detected that the
 * remapping function modified this map
 */
 @Override
 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 Objects.requireNonNull(remappingFunction);
 Entry<K,V> oldEntry = getEntry(key);
 if (oldEntry != null && oldEntry.value != null) {
 return remapValue(oldEntry, key, remappingFunction);
 } else {
 return null;
 }
 }

 /**
 * {@inheritDoc}
 *
 * This method will, on a best-effort basis, throw a
 * {@link ConcurrentModificationException} if it is detected that the
 * remapping function modifies this map during computation.
 *
 * @throws ConcurrentModificationException if it is detected that the
 * remapping function modified this map
 */
 @Override
 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 Objects.requireNonNull(remappingFunction);
 V newValue;
 Entry<K,V> t = root;
 if (t == null) {
 newValue = callRemappingFunctionWithCheck(key, null, remappingFunction);
 if (newValue != null) {
 addEntryToEmptyMap(key, newValue);
 return newValue;
 } else {
 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 remapValue(t, key, remappingFunction);
 } while (t != null);
 } else {
 Objects.requireNonNull(key);
 @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 remapValue(t, key, remappingFunction);
 } while (t != null);
 }
 newValue = callRemappingFunctionWithCheck(key, null, remappingFunction);
 if (newValue != null) {
 addEntry(key, newValue, parent, cmp < 0);
 return newValue;
 }
 return null;
 }

 /**
 * {@inheritDoc}
 *
 * This method will, on a best-effort basis, throw a
 * {@link ConcurrentModificationException} if it is detected that the
 * remapping function modifies this map during computation.
 *
 * @throws ConcurrentModificationException if it is detected that the
 * remapping function modified this map
 */
 @Override
 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
 Objects.requireNonNull(remappingFunction);
 Objects.requireNonNull(value);
 Entry<K,V> t = root;
 if (t == null) {
 addEntryToEmptyMap(key, value);
 return value;
 }
 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 mergeValue(t, value, remappingFunction);
 } while (t != null);
 } else {
 Objects.requireNonNull(key);
 @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 mergeValue(t, value, remappingFunction);
 } while (t != null);
 }
 addEntry(key, value, parent, cmp < 0);
 return value;
 }

 private V callMappingFunctionWithCheck(K key, Function<? super K, ? extends V> mappingFunction) {
 int mc = modCount;
 V newValue = mappingFunction.apply(key);
 if (mc != modCount) {
 throw new ConcurrentModificationException();
 }
 return newValue;
 }

 private V callRemappingFunctionWithCheck(K key, V oldValue, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 int mc = modCount;
 V newValue = remappingFunction.apply(key, oldValue);
 if (mc != modCount) {
 throw new ConcurrentModificationException();
 }
 return newValue;
 }

 private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
 Entry<K,V> e = new Entry<>(key, value, parent);
 if (addToLeft)
 parent.left = e;
 else
 parent.right = e;
 fixAfterInsertion(e);
 size++;
 modCount++;
 }

 private void addEntryToEmptyMap(K key, V value) {
 compare(key, key); // type (and possibly null) check
 root = new Entry<>(key, value, null);
 size = 1;
 modCount++;
 }

 private V put(K key, V value, boolean replaceOld) {
 Entry<K,V> t = root;
 if (t == null) {
 addEntryToEmptyMap(key, value);
 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 {
 V oldValue = t.value;
 if (replaceOld || oldValue == null) {
 t.value = value;
 }
 return oldValue;
 }
 } while (t != null);
 } else {
 Objects.requireNonNull(key);
 @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 {
 V oldValue = t.value;
 if (replaceOld || oldValue == null) {
 t.value = value;
 }
 return oldValue;
 }
 } while (t != null);
 }
 addEntry(key, value, parent, cmp < 0);
 return null;
 }

 private V remapValue(Entry<K,V> t, K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 V newValue = callRemappingFunctionWithCheck(key, t.value, remappingFunction);
 if (newValue == null) {
 deleteEntry(t);
 return null;
 } else {
 // replace old mapping
 t.value = newValue;
 return newValue;
 }
 }

 private V mergeValue(Entry<K,V> t, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
 V oldValue = t.value;
 V newValue;
 if (t.value == null) {
 newValue = value;
 } else {
 int mc = modCount;
 newValue = remappingFunction.apply(oldValue, value);
 if (mc != modCount) {
 throw new ConcurrentModificationException();
 }
 }
 if (newValue == null) {
 deleteEntry(t);
 return null;
 } else {
 // replace old mapping
 t.value = newValue;
 return newValue;
 }
 }

 /**
 * 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 | 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.
 *
 * The set's iterator returns the keys in ascending order.
 * The set's spliterator is
 * <a href="Spliterator.html#binding">late-binding</a>,
 * fail-fast, 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.
 *
 * 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.
 *
 * The collection's iterator returns the values in ascending order
 * of the corresponding keys. The collection's spliterator is
 * <a href="Spliterator.html#binding">late-binding</a>,
 * fail-fast, and additionally reports {@link Spliterator#ORDERED}
 * with an encounter order that is ascending order of the corresponding
 * keys.
 *
 * 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.
 *
 * The set's iterator returns the entries in ascending key order. The
 * set's spliterator is
 * <a href="Spliterator.html#binding">late-binding</a>,
 * fail-fast, and additionally reports {@link Spliterator#SORTED} and
 * {@link Spliterator#ORDERED} with an encounter order that is ascending key
 * order.
 *
 * 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<>(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<?, ?> entry))
 return false;
 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<?, ?> entry))
 return false;
 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<>(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 {
 @java.io.Serial
 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.
 */
 @SuppressWarnings("serial") // Conditionally serializable
 final K lo;
 @SuppressWarnings("serial") // Conditionally serializable
 final K 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 V putIfAbsent(K key, V value) {
 if (!inRange(key))
 throw new IllegalArgumentException("key out of range");
 return m.putIfAbsent(key, value);
 }

 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
 if (!inRange(key))
 throw new IllegalArgumentException("key out of range");
 return m.merge(key, value, remappingFunction);
 }

 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
 if (!inRange(key)) {
 // Do not throw if mapping function returns null
 // to preserve compatibility with default computeIfAbsent implementation
 if (mappingFunction.apply(key) == null) return null;
 throw new IllegalArgumentException("key out of range");
 }
 return m.computeIfAbsent(key, mappingFunction);
 }

 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 if (!inRange(key)) {
 // Do not throw if remapping function returns null
 // to preserve compatibility with default computeIfAbsent implementation
 if (remappingFunction.apply(key, null) == null) return null;
 throw new IllegalArgumentException("key out of range");
 }
 return m.compute(key, remappingFunction);
 }

 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 return !inRange(key) ? null : m.computeIfPresent(key, remappingFunction);
 }

 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 Entry<?, ?> entry))
 return false;
 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 Entry<?, ?> entry))
 return false;
 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> {
 @java.io.Serial
 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> {
 @java.io.Serial
 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);
 }

 @SuppressWarnings("serial") // Conditionally serializable
 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 {
 @java.io.Serial
 private static final long serialVersionUID = -6520786458950516097L;
 private boolean fromStart = false, toEnd = false;
 @SuppressWarnings("serial") // Conditionally serializable
 private K fromKey;
 @SuppressWarnings("serial") // Conditionally serializable
 private K toKey;
 @java.io.Serial
 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) {
 return o instanceof Map.Entry<?, ?> e
 && 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.color = RED;

 while (x != null && x != root && x.parent.color == RED) {
 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
 if (colorOf(y) == RED) {
 setColor(parentOf(x), BLACK);
 setColor(y, BLACK);
 setColor(parentOf(parentOf(x)), RED);
 x = parentOf(parentOf(x));
 } else {
 if (x == rightOf(parentOf(x))) {
 x = parentOf(x);
 rotateLeft(x);
 }
 setColor(parentOf(x), BLACK);
 setColor(parentOf(parentOf(x)), RED);
 rotateRight(parentOf(parentOf(x)));
 }
 } else {
 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);
 }

 @java.io.Serial
 private static final long serialVersionUID = 919286545866124006L;

 /**
 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
 * serialize it).
 *
 * @serialData The size 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).
 */
 @java.io.Serial
 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 (Map.Entry<K, V> e : entrySet()) {
 s.writeObject(e.getKey());
 s.writeObject(e.getValue());
 }
 }

 /**
 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
 * deserialize it).
 */
 @java.io.Serial
 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 | 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;
 }

 /**
 * Finds 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.
 *
 * @param size the (non-negative) number of keys in the tree to be built
 */
 private static int computeRedLevel(int size) {
 return 31 - Integer.numberOfLeadingZeros(size + 1);
 }

 /**
 * 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<>(this, null, null, 0, -1, 0);
 }

 final Spliterator<K> descendingKeySpliterator() {
 return new DescendingKeySpliterator<>(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-committal 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 bootstrap 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());
 };
 }
 }
 }
}

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.56 Sekunden (vorverarbeitet am 2026-05-02) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.