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