implementation.
The map is sorted according to the {@linkplain Comparable natural
ordering} of its keys, or by a
Note that the ordering maintained by a sorted map (whether or not an
explicit comparator is provided) must be consistent with equals if
this sorted map is to correctly implement the Map interface. (See
Comparable or Comparator for a precise definition of
consistent with equals.) This is so because the Map
interface is defined in terms of the equals operation, but a map performs
all key comparisons using its compareTo (or 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 equals; it
just fails to obey the general contract of the Map interface.
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 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.
| Method from java.util.TreeMap Detail: |
|---|
 void addAllForTreeSet(SortedSet set,
V defaultVal) {
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
Intended to be called only from TreeSet.addAll |
public Entry ceilingEntry(K key) {
return exportEntry(getCeilingEntry(key));
} |
public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
} |
public void clear() {
modCount++;
size = 0;
root = null;
} Removes all of the mappings from this map.
The map will be empty after this call returns. |
public Object clone() {
TreeMap< K,V > clone = null;
try {
clone = (TreeMap< K,V >) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
// 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;
} Returns a shallow copy of this TreeMap instance. (The keys and
values themselves are not cloned.) |
public Comparator comparator() {
return comparator;
} |
final int compare(Object k1,
Object k2) {
return comparator==null ? ((Comparable< ? super K >)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
} Compares two keys using the correct comparison method for this TreeMap. |
public boolean containsKey(Object key) {
return getEntry(key) != null;
} Returns true if this map contains a mapping for the specified
key. |
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 true if this map maps one or more keys to the
specified value. More formally, returns true if and only if
this map contains at least one mapping to a value v such
that (value==null ? v==null : value.equals(v)). This
operation will probably require time linear in the map size for
most implementations. |
Iterator descendingKeyIterator() {
return new DescendingKeyIterator(getLastEntry());
} |
public NavigableSet descendingKeySet() {
return descendingMap().navigableKeySet();
} |
public NavigableMap descendingMap() {
NavigableMap< K, V > km = descendingMap;
return (km != null) ? km :
(descendingMap = new DescendingSubMap(this,
true, null, true,
true, null, true));
} |
public Set entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
} Returns a Set view of the mappings contained in this map.
The set's iterator returns the entries in 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 remove operation, or through the
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 Iterator.remove,
Set.remove, removeAll, retainAll and
clear operations. It does not support the
add or addAll operations. |
static Entry exportEntry(TreeMap.Entry e) {
return e == null? null :
new AbstractMap.SimpleImmutableEntry< K,V >(e);
} Return SimpleImmutableEntry for entry, or null if null |
public Entry firstEntry() {
return exportEntry(getFirstEntry());
} |
public K firstKey() {
return key(getFirstEntry());
} |
public Entry floorEntry(K key) {
return exportEntry(getFloorEntry(key));
} |
public K floorKey(K key) {
return keyOrNull(getFloorEntry(key));
} |
public V get(Object key) {
Entry< K,V > p = getEntry(key);
return (p==null ? null : p.value);
} 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 containsKey operation may be used to
distinguish these two cases. |
final TreeMap.Entry 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 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 null. |
final TreeMap.Entry getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
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;
} Returns this map's entry for the given key, or null if the map
does not contain an entry for the key. |
final TreeMap.Entry getEntryUsingComparator(Object key) {
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;
} 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 TreeMap.Entry getFirstEntry() {
Entry< K,V > p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
} Returns the first Entry in the TreeMap (according to the TreeMap's
key-sort function). Returns null if the TreeMap is empty. |
final TreeMap.Entry 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 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 null. |
final TreeMap.Entry 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;
} 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 null. |
final TreeMap.Entry getLastEntry() {
Entry< K,V > p = root;
if (p != null)
while (p.right != null)
p = p.right;
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 TreeMap.Entry 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;
} 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 null. |
public SortedMap headMap(K toKey) {
return headMap(toKey, false);
} |
public NavigableMap headMap(K toKey,
boolean inclusive) {
return new AscendingSubMap(this,
true, null, true,
false, toKey, inclusive);
} |
public Entry higherEntry(K key) {
return exportEntry(getHigherEntry(key));
} |
public K higherKey(K key) {
return keyOrNull(getHigherEntry(key));
} |
static K key(TreeMap.Entry e) {
if (e==null)
throw new NoSuchElementException();
return e.key;
} Returns the key corresponding to the specified Entry. |
Iterator keyIterator() {
return new KeyIterator(getFirstEntry());
} |
static K keyOrNull(TreeMap.Entry e) {
return e == null? null : e.key;
} Return key for entry, or null if null |
public Set keySet() {
return navigableKeySet();
} Returns a Set view of the keys contained in this map.
The set's iterator returns the keys in ascending 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 remove operation), the results of
the iteration are undefined. The set supports element removal,
which removes the corresponding mapping from the map, via the
Iterator.remove, Set.remove,
removeAll, retainAll, and clear
operations. It does not support the add or addAll
operations. |
public Entry lastEntry() {
return exportEntry(getLastEntry());
} |
public K lastKey() {
return key(getLastEntry());
} |
public Entry lowerEntry(K key) {
return exportEntry(getLowerEntry(key));
} |
public K lowerKey(K key) {
return keyOrNull(getLowerEntry(key));
} |
public NavigableSet navigableKeySet() {
KeySet< K > nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
} |
public Entry pollFirstEntry() {
Entry< K,V > p = getFirstEntry();
Map.Entry< K,V > result = exportEntry(p);
if (p != null)
deleteEntry(p);
return result;
} |
public Entry pollLastEntry() {
Entry< K,V > p = getLastEntry();
Map.Entry< K,V > result = exportEntry(p);
if (p != null)
deleteEntry(p);
return result;
} |
static TreeMap.Entry predecessor(TreeMap.Entry 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;
}
} Returns the predecessor of the specified Entry, or null if no such. |
public V put(K key,
V value) {
Entry< K,V > t = root;
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry< K,V >(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();
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< K,V >(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
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. |
public void putAll(Map 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);
} 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. |
void readTreeSet(int size,
ObjectInputStream s,
V defaultVal) throws ClassNotFoundException, IOException {
buildFromSorted(size, null, s, defaultVal);
} Intended to be called only from TreeSet.readObject |
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 the mapping for this key from this TreeMap if present. |
public int size() {
return size;
} Returns the number of key-value mappings in this map. |
public SortedMap subMap(K fromKey,
K toKey) {
return subMap(fromKey, true, toKey, false);
} |
public NavigableMap subMap(K fromKey,
boolean fromInclusive,
K toKey,
boolean toInclusive) {
return new AscendingSubMap(this,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
} |
static TreeMap.Entry successor(TreeMap.Entry 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 successor of the specified Entry, or null if no such. |
public SortedMap tailMap(K fromKey) {
return tailMap(fromKey, true);
} |
public NavigableMap tailMap(K fromKey,
boolean inclusive) {
return new AscendingSubMap(this,
false, fromKey, inclusive,
true, null, true);
} |
static final boolean valEquals(Object o1,
Object o2) {
return (o1==null ? o2==null : o1.equals(o2));
} Test two values for equality. Differs from o1.equals(o2) only in
that it copes with null o1 properly. |
public Collection values() {
Collection< V > vs = values;
return (vs != null) ? vs : (values = new Values());
} Returns a 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 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 remove operation),
the results of the iteration are undefined. The collection
supports element removal, which removes the corresponding
mapping from the map, via the Iterator.remove,
Collection.remove, removeAll,
retainAll and clear operations. It does not
support the add or addAll operations. |
java.util.AbstractMap
Save This Page