Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/sources/formale Sprachen/Java/Openjdk/src/java.base/share/classes/java/util/ (Sun/Oracle ^©) Datei vom 13.11.2022 mit Größe 118 kB

Impressum 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);
 }

--> --------------------

--> maximum size reached

--> --------------------

quality92%

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.81Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤

*Eine klare Vorstellung vom Zielzustand

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.