| Methods Summary |
|---|
| void | balance(java.util.TreeMap$Entry x)
Entry<K, V> y;
x.color = true;
while (x != root && x.parent.color) {
if (x.parent == x.parent.parent.left) {
y = x.parent.parent.right;
if (y != null && y.color) {
x.parent.color = false;
y.color = false;
x.parent.parent.color = true;
x = x.parent.parent;
} else {
if (x == x.parent.right) {
x = x.parent;
leftRotate(x);
}
x.parent.color = false;
x.parent.parent.color = true;
rightRotate(x.parent.parent);
}
} else {
y = x.parent.parent.left;
if (y != null && y.color) {
x.parent.color = false;
y.color = false;
x.parent.parent.color = true;
x = x.parent.parent;
} else {
if (x == x.parent.left) {
x = x.parent;
rightRotate(x);
}
x.parent.color = false;
x.parent.parent.color = true;
leftRotate(x.parent.parent);
}
}
}
root.color = false;
|
| public void | clear()Removes all mappings from this TreeMap, leaving it empty.
root = null;
size = 0;
modCount++;
|
| public java.lang.Object | clone()Returns a new {@code TreeMap} with the same mappings, size and comparator
as this instance.
try {
TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
clone.entrySet = null;
if (root != null) {
clone.root = root.clone(null);
}
return clone;
} catch (CloneNotSupportedException e) {
return null;
}
|
| public java.util.Comparator | comparator()Returns the comparator used to compare elements in this map.
return comparator;
|
| public boolean | containsKey(java.lang.Object key)Returns whether this map contains the specified key.
return find(key) != null;
|
| public boolean | containsValue(java.lang.Object value)Returns whether this map contains the specified value.
if (root != null) {
return containsValue(root, value);
}
return false;
|
| private boolean | containsValue(java.util.TreeMap$Entry node, java.lang.Object value)
if (value == null ? node.value == null : value.equals(node.value)) {
return true;
}
if (node.left != null) {
if (containsValue(node.left, value)) {
return true;
}
}
if (node.right != null) {
if (containsValue(node.right, value)) {
return true;
}
}
return false;
|
| public java.util.Set | entrySet()Returns a set containing all of the mappings in this map. Each mapping is
an instance of {@link Map.Entry}. As the set is backed by this map,
changes in one will be reflected in the other. It does not support adding
operations.
if (entrySet == null) {
entrySet = new AbstractSet<Map.Entry<K, V>>() {
@Override
public int size() {
return size;
}
@Override
public void clear() {
TreeMap.this.clear();
}
@SuppressWarnings("unchecked")
@Override
public boolean contains(Object object) {
if (object instanceof Map.Entry) {
Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
Object v1 = get(entry.getKey()), v2 = entry.getValue();
return v1 == null ? v2 == null : v1.equals(v2);
}
return false;
}
@Override
public Iterator<Map.Entry<K, V>> iterator() {
return new UnboundedEntryIterator<K, V>(TreeMap.this);
}
};
}
return entrySet;
|
| private java.util.TreeMap$Entry | find(java.lang.Object keyObj)
int result;
K key = (K)keyObj;
Comparable<K> object = null;
if (comparator == null) {
object = toComparable(key);
}
Entry<K, V> x = root;
while (x != null) {
result = object != null ? object.compareTo(x.key) : comparator
.compare(key, x.key);
if (result == 0) {
return x;
}
x = result < 0 ? x.left : x.right;
}
return null;
|
| java.util.TreeMap$Entry | findAfter(java.lang.Object keyObj)
K key = (K)keyObj;
int result;
Comparable<K> object = null;
if (comparator == null) {
object = toComparable(key);
}
Entry<K, V> x = root, last = null;
while (x != null) {
result = object != null ? object.compareTo(x.key) : comparator
.compare(key, x.key);
if (result == 0) {
return x;
}
if (result < 0) {
last = x;
x = x.left;
} else {
x = x.right;
}
}
return last;
|
| java.util.TreeMap$Entry | findBefore(K key)
int result;
Comparable<K> object = null;
if (comparator == null) {
object = toComparable(key);
}
Entry<K, V> x = root, last = null;
while (x != null) {
result = object != null ? object.compareTo(x.key) : comparator
.compare(key, x.key);
if (result <= 0) {
x = x.left;
} else {
last = x;
x = x.right;
}
}
return last;
|
| public K | firstKey()Returns the first key in this map.
if (root != null) {
return minimum(root).key;
}
throw new NoSuchElementException();
|
| private void | fixup(java.util.TreeMap$Entry x)
Entry<K, V> w;
while (x != root && !x.color) {
if (x == x.parent.left) {
w = x.parent.right;
if (w == null) {
x = x.parent;
continue;
}
if (w.color) {
w.color = false;
x.parent.color = true;
leftRotate(x.parent);
w = x.parent.right;
if (w == null) {
x = x.parent;
continue;
}
}
if ((w.left == null || !w.left.color)
&& (w.right == null || !w.right.color)) {
w.color = true;
x = x.parent;
} else {
if (w.right == null || !w.right.color) {
w.left.color = false;
w.color = true;
rightRotate(w);
w = x.parent.right;
}
w.color = x.parent.color;
x.parent.color = false;
w.right.color = false;
leftRotate(x.parent);
x = root;
}
} else {
w = x.parent.left;
if (w == null) {
x = x.parent;
continue;
}
if (w.color) {
w.color = false;
x.parent.color = true;
rightRotate(x.parent);
w = x.parent.left;
if (w == null) {
x = x.parent;
continue;
}
}
if ((w.left == null || !w.left.color)
&& (w.right == null || !w.right.color)) {
w.color = true;
x = x.parent;
} else {
if (w.left == null || !w.left.color) {
w.right.color = false;
w.color = true;
leftRotate(w);
w = x.parent.left;
}
w.color = x.parent.color;
x.parent.color = false;
w.left.color = false;
rightRotate(x.parent);
x = root;
}
}
}
x.color = false;
|
| public V | get(java.lang.Object key)Returns the value of the mapping with the specified key.
Entry<K, V> node = find(key);
if (node != null) {
return node.value;
}
return null;
|
| public java.util.SortedMap | headMap(K endKey)Returns a sorted map over a range of this sorted map with all keys that
are less than the specified {@code endKey}. Changes to the returned
sorted map are reflected in this sorted map and vice versa.
Note: The returned map will not allow an insertion of a key outside the
specified range.
// Check for errors
if (comparator == null) {
toComparable(endKey).compareTo(endKey);
} else {
comparator.compare(endKey, endKey);
}
return new SubMap<K, V>(this, endKey);
|
| public java.util.Set | keySet()Returns a set of the keys contained in this map. The set is backed by
this map so changes to one are reflected by the other. The set does not
support adding.
if (keySet == null) {
keySet = new AbstractSet<K>() {
@Override
public boolean contains(Object object) {
return containsKey(object);
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
TreeMap.this.clear();
}
@Override
public Iterator<K> iterator() {
return new UnboundedKeyIterator<K,V> (TreeMap.this);
}
};
}
return keySet;
|
| public K | lastKey()Returns the last key in this map.
if (root != null) {
return maximum(root).key;
}
throw new NoSuchElementException();
|
| private void | leftRotate(java.util.TreeMap$Entry x)
Entry<K, V> y = x.right;
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
|
| static java.util.TreeMap$Entry | maximum(java.util.TreeMap$Entry x)
while (x.right != null) {
x = x.right;
}
return x;
|
| static java.util.TreeMap$Entry | minimum(java.util.TreeMap$Entry x)
while (x.left != null) {
x = x.left;
}
return x;
|
| static java.util.TreeMap$Entry | predecessor(java.util.TreeMap$Entry x)
if (x.left != null) {
return maximum(x.left);
}
Entry<K, V> y = x.parent;
while (y != null && x == y.left) {
x = y;
y = y.parent;
}
return y;
|
| public V | put(K key, V value)Maps the specified key to the specified value.
MapEntry<K, V> entry = rbInsert(key);
V result = entry.value;
entry.value = value;
return result;
|
| public void | putAll(java.util.Map map)Copies all the mappings in the given map to this map. These mappings will
replace all mappings that this map had for any of the keys currently in
the given map.
super.putAll(map);
|
| void | rbDelete(java.util.TreeMap$Entry z)
Entry<K, V> y = z.left == null || z.right == null ? z : successor(z);
Entry<K, V> x = y.left != null ? y.left : y.right;
if (x != null) {
x.parent = y.parent;
}
if (y.parent == null) {
root = x;
} else if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
modCount++;
if (y != z) {
z.key = y.key;
z.value = y.value;
}
if (!y.color && root != null) {
if (x == null) {
fixup(y.parent);
} else {
fixup(x);
}
}
size--;
|
| private java.util.TreeMap$Entry | rbInsert(K object)
int result = 0;
Entry<K, V> y = null;
if (size != 0) {
Comparable<K> key = null;
if (comparator == null) {
key = toComparable(object);
}
Entry<K, V> x = root;
while (x != null) {
y = x;
result = key != null ? key.compareTo(x.key) : comparator
.compare(object, x.key);
if (result == 0) {
return x;
}
x = result < 0 ? x.left : x.right;
}
}
size++;
modCount++;
Entry<K, V> z = new Entry<K, V>(object);
if (y == null) {
return root = z;
}
z.parent = y;
if (result < 0) {
y.left = z;
} else {
y.right = z;
}
balance(z);
return z;
|
| private void | readObject(java.io.ObjectInputStream stream)
stream.defaultReadObject();
size = stream.readInt();
Entry<K, V> last = null;
for (int i = size; --i >= 0;) {
Entry<K, V> node = new Entry<K, V>((K)stream.readObject());
node.value = (V)stream.readObject();
if (last == null) {
root = node;
} else {
node.parent = last;
last.right = node;
balance(node);
}
last = node;
}
|
| public V | remove(java.lang.Object key)Removes the mapping with the specified key from this map.
if (size == 0) {
return null;
}
Entry<K, V> node = find(key);
if (node == null) {
return null;
}
V result = node.value;
rbDelete(node);
return result;
|
| private void | rightRotate(java.util.TreeMap$Entry x)
Entry<K, V> y = x.left;
x.left = y.right;
if (y.right != null) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else {
if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
}
y.right = x;
x.parent = y;
|
| public int | size()Returns the number of mappings in this map.
return size;
|
| public java.util.SortedMap | subMap(K startKey, K endKey)Returns a sorted map over a range of this sorted map with all keys
greater than or equal to the specified {@code startKey} and less than the
specified {@code endKey}. Changes to the returned sorted map are
reflected in this sorted map and vice versa.
Note: The returned map will not allow an insertion of a key outside the
specified range.
if (comparator == null) {
if (toComparable(startKey).compareTo(endKey) <= 0) {
return new SubMap<K, V>(startKey, this, endKey);
}
} else {
if (comparator.compare(startKey, endKey) <= 0) {
return new SubMap<K, V>(startKey, this, endKey);
}
}
throw new IllegalArgumentException();
|
| static java.util.TreeMap$Entry | successor(java.util.TreeMap$Entry x)
if (x.right != null) {
return minimum(x.right);
}
Entry<K, V> y = x.parent;
while (y != null && x == y.right) {
x = y;
y = y.parent;
}
return y;
|
| public java.util.SortedMap | tailMap(K startKey)Returns a sorted map over a range of this sorted map with all keys that
are greater than or equal to the specified {@code startKey}. Changes to
the returned sorted map are reflected in this sorted map and vice versa.
Note: The returned map will not allow an insertion of a key outside the
specified range.
// Check for errors
if (comparator == null) {
toComparable(startKey).compareTo(startKey);
} else {
comparator.compare(startKey, startKey);
}
return new SubMap<K, V>(startKey, this);
|
| private static java.lang.Comparable | toComparable(T obj)
return (Comparable<T>)obj;
|
| public java.util.Collection | values()Returns a collection of the values contained in this map. The collection
is backed by this map so changes to one are reflected by the other. The
collection supports remove, removeAll, retainAll and clear operations,
and it does not support add or addAll operations.
This method returns a collection which is the subclass of
AbstractCollection. The iterator method of this subclass returns a
"wrapper object" over the iterator of map's entrySet(). The {@code size}
method wraps the map's size method and the {@code contains} method wraps
the map's containsValue method.
The collection is created when this method is called for the first time
and returned in response to all subsequent calls. This method may return
different collections when multiple concurrent calls occur, since no
synchronization is performed.
if (valuesCollection == null) {
valuesCollection = new AbstractCollection<V>() {
@Override
public boolean contains(Object object) {
return containsValue(object);
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
TreeMap.this.clear();
}
@Override
public Iterator<V> iterator() {
return new UnboundedValueIterator<K,V> (TreeMap.this);
}
};
}
return valuesCollection;
|
| private void | writeObject(java.io.ObjectOutputStream stream)
stream.defaultWriteObject();
stream.writeInt(size);
if (size > 0) {
Entry<K, V> node = minimum(root);
while (node != null) {
stream.writeObject(node.key);
stream.writeObject(node.value);
node = successor(node);
}
}
|
