| 68 |
|
* associated map using <tt>put</tt>.) |
| 69 |
|
* |
| 70 |
|
* <p>This class is a member of the |
| 71 |
< |
* <a href="{@docRoot}/../guide/collections/index.html"> |
| 71 |
> |
* <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
| 72 |
|
* Java Collections Framework</a>. |
| 73 |
|
* |
| 74 |
|
* @param <K> the type of keys maintained by this map |
| 223 |
|
* @since 1.2 |
| 224 |
|
*/ |
| 225 |
|
public boolean containsValue(Object value) { |
| 226 |
< |
return (root==null ? false : |
| 227 |
< |
(value==null ? valueSearchNull(root) |
| 228 |
< |
: valueSearchNonNull(root, value))); |
| 229 |
< |
} |
| 230 |
< |
|
| 231 |
< |
private boolean valueSearchNull(Entry n) { |
| 232 |
< |
if (n.value == null) |
| 233 |
< |
return true; |
| 234 |
< |
|
| 235 |
< |
// Check left and right subtrees for value |
| 236 |
< |
return (n.left != null && valueSearchNull(n.left)) || |
| 237 |
< |
(n.right != null && valueSearchNull(n.right)); |
| 238 |
< |
} |
| 239 |
< |
|
| 240 |
< |
private boolean valueSearchNonNull(Entry n, Object value) { |
| 241 |
< |
// Check this node for the value |
| 242 |
< |
if (value.equals(n.value)) |
| 243 |
< |
return true; |
| 244 |
< |
|
| 245 |
< |
// Check left and right subtrees for value |
| 246 |
< |
return (n.left != null && valueSearchNonNull(n.left, value)) || |
| 247 |
< |
(n.right != null && valueSearchNonNull(n.right, value)); |
| 226 |
> |
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) |
| 227 |
> |
if (valEquals(value, e.value)) |
| 228 |
> |
return true; |
| 229 |
> |
return false; |
| 230 |
|
} |
| 231 |
|
|
| 232 |
|
/** |
| 340 |
|
* Version of getEntry using comparator. Split off from getEntry |
| 341 |
|
* for performance. (This is not worth doing for most methods, |
| 342 |
|
* that are less dependent on comparator performance, but is |
| 343 |
< |
* worthwhile for get and put.) |
| 343 |
> |
* worthwhile here.) |
| 344 |
|
*/ |
| 345 |
|
final Entry<K,V> getEntryUsingComparator(Object key) { |
| 346 |
|
K k = (K) key; |
| 347 |
|
Comparator<? super K> cpr = comparator; |
| 348 |
< |
Entry<K,V> p = root; |
| 349 |
< |
while (p != null) { |
| 350 |
< |
int cmp = cpr.compare(k, p.key); |
| 351 |
< |
if (cmp < 0) |
| 352 |
< |
p = p.left; |
| 353 |
< |
else if (cmp > 0) |
| 354 |
< |
p = p.right; |
| 355 |
< |
else |
| 356 |
< |
return p; |
| 348 |
> |
if (cpr != null) { |
| 349 |
> |
Entry<K,V> p = root; |
| 350 |
> |
while (p != null) { |
| 351 |
> |
int cmp = cpr.compare(k, p.key); |
| 352 |
> |
if (cmp < 0) |
| 353 |
> |
p = p.left; |
| 354 |
> |
else if (cmp > 0) |
| 355 |
> |
p = p.right; |
| 356 |
> |
else |
| 357 |
> |
return p; |
| 358 |
> |
} |
| 359 |
|
} |
| 360 |
|
return null; |
| 361 |
|
} |
| 508 |
|
* does not permit null keys |
| 509 |
|
*/ |
| 510 |
|
public V put(K key, V value) { |
| 527 |
– |
// Offload comparator-based version for sake of performance |
| 528 |
– |
if (comparator != null) |
| 529 |
– |
return putUsingComparator(key, value); |
| 530 |
– |
if (key == null) |
| 531 |
– |
throw new NullPointerException(); |
| 532 |
– |
Comparable<? super K> k = (Comparable<? super K>) key; |
| 533 |
– |
int cmp = 0; |
| 534 |
– |
Entry<K,V> parent = null; |
| 511 |
|
Entry<K,V> t = root; |
| 512 |
< |
while (t != null) { |
| 513 |
< |
parent = t; |
| 514 |
< |
cmp = k.compareTo(t.key); |
| 515 |
< |
if (cmp < 0) |
| 516 |
< |
t = t.left; |
| 517 |
< |
else if (cmp > 0) |
| 518 |
< |
t = t.right; |
| 519 |
< |
else |
| 520 |
< |
return t.setValue(value); |
| 521 |
< |
} |
| 546 |
< |
Entry<K,V> e = new Entry<K,V>((K)k, value, parent); |
| 547 |
< |
size++; |
| 548 |
< |
modCount++; |
| 549 |
< |
if (parent != null) { |
| 550 |
< |
if (cmp < 0) |
| 551 |
< |
parent.left = e; |
| 552 |
< |
else |
| 553 |
< |
parent.right = e; |
| 554 |
< |
fixAfterInsertion(e); |
| 512 |
> |
if (t == null) { |
| 513 |
> |
// TBD: |
| 514 |
> |
// 5045147: (coll) Adding null to an empty TreeSet should |
| 515 |
> |
// throw NullPointerException |
| 516 |
> |
// |
| 517 |
> |
// compare(key, key); // type check |
| 518 |
> |
root = new Entry<K,V>(key, value, null); |
| 519 |
> |
size = 1; |
| 520 |
> |
modCount++; |
| 521 |
> |
return null; |
| 522 |
|
} |
| 523 |
< |
else |
| 524 |
< |
root = e; |
| 525 |
< |
return null; |
| 559 |
< |
} |
| 560 |
< |
|
| 561 |
< |
/** |
| 562 |
< |
* Version of put using comparator. Split off from put for |
| 563 |
< |
* performance. |
| 564 |
< |
*/ |
| 565 |
< |
final V putUsingComparator(K key, V value) { |
| 523 |
> |
int cmp; |
| 524 |
> |
Entry<K,V> parent; |
| 525 |
> |
// split comparator and comparable paths |
| 526 |
|
Comparator<? super K> cpr = comparator; |
| 527 |
< |
int cmp = 0; |
| 528 |
< |
Entry<K,V> parent = null; |
| 529 |
< |
Entry<K,V> t = root; |
| 530 |
< |
if (t == null) |
| 531 |
< |
cpr.compare(key, key); // type check |
| 532 |
< |
while (t != null) { |
| 533 |
< |
parent = t; |
| 534 |
< |
cmp = cpr.compare(key, t.key); |
| 535 |
< |
if (cmp < 0) |
| 536 |
< |
t = t.left; |
| 537 |
< |
else if (cmp > 0) |
| 538 |
< |
t = t.right; |
| 539 |
< |
else |
| 540 |
< |
return t.setValue(value); |
| 527 |
> |
if (cpr != null) { |
| 528 |
> |
do { |
| 529 |
> |
parent = t; |
| 530 |
> |
cmp = cpr.compare(key, t.key); |
| 531 |
> |
if (cmp < 0) |
| 532 |
> |
t = t.left; |
| 533 |
> |
else if (cmp > 0) |
| 534 |
> |
t = t.right; |
| 535 |
> |
else |
| 536 |
> |
return t.setValue(value); |
| 537 |
> |
} while (t != null); |
| 538 |
> |
} |
| 539 |
> |
else { |
| 540 |
> |
if (key == null) |
| 541 |
> |
throw new NullPointerException(); |
| 542 |
> |
Comparable<? super K> k = (Comparable<? super K>) key; |
| 543 |
> |
do { |
| 544 |
> |
parent = t; |
| 545 |
> |
cmp = k.compareTo(t.key); |
| 546 |
> |
if (cmp < 0) |
| 547 |
> |
t = t.left; |
| 548 |
> |
else if (cmp > 0) |
| 549 |
> |
t = t.right; |
| 550 |
> |
else |
| 551 |
> |
return t.setValue(value); |
| 552 |
> |
} while (t != null); |
| 553 |
|
} |
| 554 |
|
Entry<K,V> e = new Entry<K,V>(key, value, parent); |
| 555 |
+ |
if (cmp < 0) |
| 556 |
+ |
parent.left = e; |
| 557 |
+ |
else |
| 558 |
+ |
parent.right = e; |
| 559 |
+ |
fixAfterInsertion(e); |
| 560 |
|
size++; |
| 561 |
|
modCount++; |
| 585 |
– |
if (parent != null) { |
| 586 |
– |
if (cmp < 0) |
| 587 |
– |
parent.left = e; |
| 588 |
– |
else |
| 589 |
– |
parent.right = e; |
| 590 |
– |
fixAfterInsertion(e); |
| 591 |
– |
} |
| 592 |
– |
else |
| 593 |
– |
root = e; |
| 562 |
|
return null; |
| 563 |
|
} |
| 564 |
|
|
| 937 |
|
} |
| 938 |
|
|
| 939 |
|
public boolean contains(Object o) { |
| 940 |
< |
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) |
| 973 |
< |
if (valEquals(e.getValue(), o)) |
| 974 |
< |
return true; |
| 975 |
< |
return false; |
| 940 |
> |
return TreeMap.this.containsValue(o); |
| 941 |
|
} |
| 942 |
|
|
| 943 |
|
public boolean remove(Object o) { |
| 1050 |
|
return size() != oldSize; |
| 1051 |
|
} |
| 1052 |
|
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, |
| 1053 |
< |
E toElement, boolean toInclusive) { |
| 1053 |
> |
E toElement, boolean toInclusive) { |
| 1054 |
|
return new TreeSet<E>(m.subMap(fromElement, fromInclusive, |
| 1055 |
|
toElement, toInclusive)); |
| 1056 |
|
} |
| 1207 |
|
|
| 1208 |
|
// SubMaps |
| 1209 |
|
|
| 1210 |
+ |
/** |
| 1211 |
+ |
* @serial include |
| 1212 |
+ |
*/ |
| 1213 |
|
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V> |
| 1214 |
|
implements NavigableMap<K,V>, java.io.Serializable { |
| 1215 |
< |
/* |
| 1215 |
> |
/** |
| 1216 |
|
* The backing map. |
| 1217 |
|
*/ |
| 1218 |
|
final TreeMap<K,V> m; |
| 1219 |
|
|
| 1220 |
< |
/* |
| 1220 |
> |
/** |
| 1221 |
|
* Endpoints are represented as triples (fromStart, lo, |
| 1222 |
|
* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is |
| 1223 |
|
* true, then the low (absolute) bound is the start of the |
| 1225 |
|
* if loInclusive is true, lo is the inclusive bound, else lo |
| 1226 |
|
* is the exclusive bound. Similarly for the upper bound. |
| 1227 |
|
*/ |
| 1260 |
– |
|
| 1228 |
|
final K lo, hi; |
| 1229 |
|
final boolean fromStart, toEnd; |
| 1230 |
|
final boolean loInclusive, hiInclusive; |
| 1349 |
|
} |
| 1350 |
|
|
| 1351 |
|
// Abstract methods defined in ascending vs descending classes |
| 1352 |
< |
// These relay to the appropriate absolute versions |
| 1352 |
> |
// These relay to the appropriate absolute versions |
| 1353 |
|
|
| 1354 |
|
abstract TreeMap.Entry<K,V> subLowest(); |
| 1355 |
|
abstract TreeMap.Entry<K,V> subHighest(); |
| 1636 |
|
} |
| 1637 |
|
} |
| 1638 |
|
|
| 1639 |
+ |
/** |
| 1640 |
+ |
* @serial include |
| 1641 |
+ |
*/ |
| 1642 |
|
static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| 1643 |
|
private static final long serialVersionUID = 912986545866124060L; |
| 1644 |
|
|
| 1645 |
|
AscendingSubMap(TreeMap<K,V> m, |
| 1646 |
|
boolean fromStart, K lo, boolean loInclusive, |
| 1647 |
< |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1647 |
> |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1648 |
|
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); |
| 1649 |
|
} |
| 1650 |
|
|
| 1653 |
|
} |
| 1654 |
|
|
| 1655 |
|
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| 1656 |
< |
K toKey, boolean toInclusive) { |
| 1656 |
> |
K toKey, boolean toInclusive) { |
| 1657 |
|
if (!inRange(fromKey, fromInclusive)) |
| 1658 |
|
throw new IllegalArgumentException("fromKey out of range"); |
| 1659 |
|
if (!inRange(toKey, toInclusive)) |
| 1715 |
|
TreeMap.Entry<K,V> subLower(K key) { return absLower(key); } |
| 1716 |
|
} |
| 1717 |
|
|
| 1718 |
+ |
/** |
| 1719 |
+ |
* @serial include |
| 1720 |
+ |
*/ |
| 1721 |
|
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| 1722 |
|
private static final long serialVersionUID = 912986545866120460L; |
| 1723 |
|
DescendingSubMap(TreeMap<K,V> m, |
| 1724 |
|
boolean fromStart, K lo, boolean loInclusive, |
| 1725 |
< |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1725 |
> |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1726 |
|
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); |
| 1727 |
|
} |
| 1728 |
|
|
| 1734 |
|
} |
| 1735 |
|
|
| 1736 |
|
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| 1737 |
< |
K toKey, boolean toInclusive) { |
| 1737 |
> |
K toKey, boolean toInclusive) { |
| 1738 |
|
if (!inRange(fromKey, fromInclusive)) |
| 1739 |
|
throw new IllegalArgumentException("fromKey out of range"); |
| 1740 |
|
if (!inRange(toKey, toInclusive)) |
| 1802 |
|
* support NavigableMap. It translates an old-version SubMap into |
| 1803 |
|
* a new-version AscendingSubMap. This class is never otherwise |
| 1804 |
|
* used. |
| 1805 |
+ |
* |
| 1806 |
+ |
* @serial include |
| 1807 |
|
*/ |
| 1808 |
|
private class SubMap extends AbstractMap<K,V> |
| 1809 |
|
implements SortedMap<K,V>, java.io.Serializable { |
| 1887 |
|
public boolean equals(Object o) { |
| 1888 |
|
if (!(o instanceof Map.Entry)) |
| 1889 |
|
return false; |
| 1890 |
< |
Map.Entry e = (Map.Entry)o; |
| 1890 |
> |
Map.Entry<?,?> e = (Map.Entry<?,?>)o; |
| 1891 |
|
|
| 1892 |
|
return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); |
| 1893 |
|
} |
| 2004 |
|
|
| 2005 |
|
/** From CLR */ |
| 2006 |
|
private void rotateLeft(Entry<K,V> p) { |
| 2007 |
< |
Entry<K,V> r = p.right; |
| 2008 |
< |
p.right = r.left; |
| 2009 |
< |
if (r.left != null) |
| 2010 |
< |
r.left.parent = p; |
| 2011 |
< |
r.parent = p.parent; |
| 2012 |
< |
if (p.parent == null) |
| 2013 |
< |
root = r; |
| 2014 |
< |
else if (p.parent.left == p) |
| 2015 |
< |
p.parent.left = r; |
| 2016 |
< |
else |
| 2017 |
< |
p.parent.right = r; |
| 2018 |
< |
r.left = p; |
| 2019 |
< |
p.parent = r; |
| 2007 |
> |
if (p != null) { |
| 2008 |
> |
Entry<K,V> r = p.right; |
| 2009 |
> |
p.right = r.left; |
| 2010 |
> |
if (r.left != null) |
| 2011 |
> |
r.left.parent = p; |
| 2012 |
> |
r.parent = p.parent; |
| 2013 |
> |
if (p.parent == null) |
| 2014 |
> |
root = r; |
| 2015 |
> |
else if (p.parent.left == p) |
| 2016 |
> |
p.parent.left = r; |
| 2017 |
> |
else |
| 2018 |
> |
p.parent.right = r; |
| 2019 |
> |
r.left = p; |
| 2020 |
> |
p.parent = r; |
| 2021 |
> |
} |
| 2022 |
|
} |
| 2023 |
|
|
| 2024 |
|
/** From CLR */ |
| 2025 |
|
private void rotateRight(Entry<K,V> p) { |
| 2026 |
< |
Entry<K,V> l = p.left; |
| 2027 |
< |
p.left = l.right; |
| 2028 |
< |
if (l.right != null) l.right.parent = p; |
| 2029 |
< |
l.parent = p.parent; |
| 2030 |
< |
if (p.parent == null) |
| 2031 |
< |
root = l; |
| 2032 |
< |
else if (p.parent.right == p) |
| 2033 |
< |
p.parent.right = l; |
| 2034 |
< |
else p.parent.left = l; |
| 2035 |
< |
l.right = p; |
| 2036 |
< |
p.parent = l; |
| 2026 |
> |
if (p != null) { |
| 2027 |
> |
Entry<K,V> l = p.left; |
| 2028 |
> |
p.left = l.right; |
| 2029 |
> |
if (l.right != null) l.right.parent = p; |
| 2030 |
> |
l.parent = p.parent; |
| 2031 |
> |
if (p.parent == null) |
| 2032 |
> |
root = l; |
| 2033 |
> |
else if (p.parent.right == p) |
| 2034 |
> |
p.parent.right = l; |
| 2035 |
> |
else p.parent.left = l; |
| 2036 |
> |
l.right = p; |
| 2037 |
> |
p.parent = l; |
| 2038 |
> |
} |
| 2039 |
|
} |
| 2040 |
|
|
| 2062 |
– |
|
| 2041 |
|
/** From CLR */ |
| 2042 |
|
private void fixAfterInsertion(Entry<K,V> x) { |
| 2043 |
|
x.color = RED; |
| 2057 |
|
} |
| 2058 |
|
setColor(parentOf(x), BLACK); |
| 2059 |
|
setColor(parentOf(parentOf(x)), RED); |
| 2060 |
< |
if (parentOf(parentOf(x)) != null) |
| 2083 |
< |
rotateRight(parentOf(parentOf(x))); |
| 2060 |
> |
rotateRight(parentOf(parentOf(x))); |
| 2061 |
|
} |
| 2062 |
|
} else { |
| 2063 |
|
Entry<K,V> y = leftOf(parentOf(parentOf(x))); |
| 2073 |
|
} |
| 2074 |
|
setColor(parentOf(x), BLACK); |
| 2075 |
|
setColor(parentOf(parentOf(x)), RED); |
| 2076 |
< |
if (parentOf(parentOf(x)) != null) |
| 2100 |
< |
rotateLeft(parentOf(parentOf(x))); |
| 2076 |
> |
rotateLeft(parentOf(parentOf(x))); |
| 2077 |
|
} |
| 2078 |
|
} |
| 2079 |
|
} |
| 2083 |
|
/** |
| 2084 |
|
* Delete node p, and then rebalance the tree. |
| 2085 |
|
*/ |
| 2110 |
– |
|
| 2086 |
|
private void deleteEntry(Entry<K,V> p) { |
| 2087 |
|
modCount++; |
| 2088 |
|
size--; |
