1 |
|
/* |
2 |
< |
* %W% %E% |
2 |
> |
* Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved. |
3 |
> |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
|
* |
5 |
< |
* Copyright 2006 Sun Microsystems, Inc. All rights reserved. |
6 |
< |
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. |
5 |
> |
* This code is free software; you can redistribute it and/or modify it |
6 |
> |
* under the terms of the GNU General Public License version 2 only, as |
7 |
> |
* published by the Free Software Foundation. Sun designates this |
8 |
> |
* particular file as subject to the "Classpath" exception as provided |
9 |
> |
* by Sun in the LICENSE file that accompanied this code. |
10 |
> |
* |
11 |
> |
* This code is distributed in the hope that it will be useful, but WITHOUT |
12 |
> |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 |
> |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 |
> |
* version 2 for more details (a copy is included in the LICENSE file that |
15 |
> |
* accompanied this code). |
16 |
> |
* |
17 |
> |
* You should have received a copy of the GNU General Public License version |
18 |
> |
* 2 along with this work; if not, write to the Free Software Foundation, |
19 |
> |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
20 |
> |
* |
21 |
> |
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
22 |
> |
* CA 95054 USA or visit www.sun.com if you need additional information or |
23 |
> |
* have any questions. |
24 |
|
*/ |
25 |
|
|
26 |
|
package java.util; |
93 |
|
* @param <V> the type of mapped values |
94 |
|
* |
95 |
|
* @author Josh Bloch and Doug Lea |
78 |
– |
* @version %I%, %G% |
96 |
|
* @see Map |
97 |
|
* @see HashMap |
98 |
|
* @see Hashtable |
236 |
|
* |
237 |
|
* @param value value whose presence in this map is to be tested |
238 |
|
* @return <tt>true</tt> if a mapping to <tt>value</tt> exists; |
239 |
< |
* <tt>false</tt> otherwise |
239 |
> |
* <tt>false</tt> otherwise |
240 |
|
* @since 1.2 |
241 |
|
*/ |
242 |
|
public boolean containsValue(Object value) { |
308 |
|
if (size==0 && mapSize!=0 && map instanceof SortedMap) { |
309 |
|
Comparator c = ((SortedMap)map).comparator(); |
310 |
|
if (c == comparator || (c != null && c.equals(comparator))) { |
311 |
< |
++modCount; |
312 |
< |
try { |
313 |
< |
buildFromSorted(mapSize, map.entrySet().iterator(), |
314 |
< |
null, null); |
315 |
< |
} catch (java.io.IOException cannotHappen) { |
316 |
< |
} catch (ClassNotFoundException cannotHappen) { |
317 |
< |
} |
318 |
< |
return; |
311 |
> |
++modCount; |
312 |
> |
try { |
313 |
> |
buildFromSorted(mapSize, map.entrySet().iterator(), |
314 |
> |
null, null); |
315 |
> |
} catch (java.io.IOException cannotHappen) { |
316 |
> |
} catch (ClassNotFoundException cannotHappen) { |
317 |
> |
} |
318 |
> |
return; |
319 |
|
} |
320 |
|
} |
321 |
|
super.putAll(map); |
339 |
|
return getEntryUsingComparator(key); |
340 |
|
if (key == null) |
341 |
|
throw new NullPointerException(); |
342 |
< |
Comparable<? super K> k = (Comparable<? super K>) key; |
342 |
> |
Comparable<? super K> k = (Comparable<? super K>) key; |
343 |
|
Entry<K,V> p = root; |
344 |
|
while (p != null) { |
345 |
|
int cmp = k.compareTo(p.key); |
360 |
|
* worthwhile here.) |
361 |
|
*/ |
362 |
|
final Entry<K,V> getEntryUsingComparator(Object key) { |
363 |
< |
K k = (K) key; |
363 |
> |
K k = (K) key; |
364 |
|
Comparator<? super K> cpr = comparator; |
365 |
|
if (cpr != null) { |
366 |
|
Entry<K,V> p = root; |
527 |
|
public V put(K key, V value) { |
528 |
|
Entry<K,V> t = root; |
529 |
|
if (t == null) { |
530 |
< |
// TBD: |
531 |
< |
// 5045147: (coll) Adding null to an empty TreeSet should |
532 |
< |
// throw NullPointerException |
533 |
< |
// |
534 |
< |
// compare(key, key); // type check |
530 |
> |
// TBD: |
531 |
> |
// 5045147: (coll) Adding null to an empty TreeSet should |
532 |
> |
// throw NullPointerException |
533 |
> |
// |
534 |
> |
// compare(key, key); // type check |
535 |
|
root = new Entry<K,V>(key, value, null); |
536 |
|
size = 1; |
537 |
|
modCount++; |
1021 |
|
} |
1022 |
|
|
1023 |
|
Iterator<K> descendingKeyIterator() { |
1024 |
< |
return new DescendingKeyIterator(getFirstEntry()); |
1024 |
> |
return new DescendingKeyIterator(getLastEntry()); |
1025 |
|
} |
1026 |
|
|
1027 |
|
static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { |
1068 |
|
} |
1069 |
|
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, |
1070 |
|
E toElement, boolean toInclusive) { |
1071 |
< |
return new TreeSet<E>(m.subMap(fromElement, fromInclusive, |
1072 |
< |
toElement, toInclusive)); |
1071 |
> |
return new KeySet<E>(m.subMap(fromElement, fromInclusive, |
1072 |
> |
toElement, toInclusive)); |
1073 |
|
} |
1074 |
|
public NavigableSet<E> headSet(E toElement, boolean inclusive) { |
1075 |
< |
return new TreeSet<E>(m.headMap(toElement, inclusive)); |
1075 |
> |
return new KeySet<E>(m.headMap(toElement, inclusive)); |
1076 |
|
} |
1077 |
|
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { |
1078 |
< |
return new TreeSet<E>(m.tailMap(fromElement, inclusive)); |
1078 |
> |
return new KeySet<E>(m.tailMap(fromElement, inclusive)); |
1079 |
|
} |
1080 |
|
public SortedSet<E> subSet(E fromElement, E toElement) { |
1081 |
|
return subSet(fromElement, true, toElement, false); |
1087 |
|
return tailSet(fromElement, true); |
1088 |
|
} |
1089 |
|
public NavigableSet<E> descendingSet() { |
1090 |
< |
return new TreeSet(m.descendingMap()); |
1090 |
> |
return new KeySet(m.descendingMap()); |
1091 |
|
} |
1092 |
|
} |
1093 |
|
|
1109 |
|
return next != null; |
1110 |
|
} |
1111 |
|
|
1112 |
< |
final Entry<K,V> nextEntry() { |
1113 |
< |
Entry<K,V> e = lastReturned = next; |
1112 |
> |
final Entry<K,V> nextEntry() { |
1113 |
> |
Entry<K,V> e = next; |
1114 |
|
if (e == null) |
1115 |
|
throw new NoSuchElementException(); |
1116 |
|
if (modCount != expectedModCount) |
1117 |
|
throw new ConcurrentModificationException(); |
1118 |
|
next = successor(e); |
1119 |
+ |
lastReturned = e; |
1120 |
|
return e; |
1121 |
|
} |
1122 |
|
|
1123 |
|
final Entry<K,V> prevEntry() { |
1124 |
< |
Entry<K,V> e = lastReturned= next; |
1124 |
> |
Entry<K,V> e = next; |
1125 |
|
if (e == null) |
1126 |
|
throw new NoSuchElementException(); |
1127 |
|
if (modCount != expectedModCount) |
1128 |
|
throw new ConcurrentModificationException(); |
1129 |
|
next = predecessor(e); |
1130 |
+ |
lastReturned = e; |
1131 |
|
return e; |
1132 |
|
} |
1133 |
|
|
1228 |
|
// SubMaps |
1229 |
|
|
1230 |
|
/** |
1231 |
+ |
* Dummy value serving as unmatchable fence key for unbounded |
1232 |
+ |
* SubMapIterators |
1233 |
+ |
*/ |
1234 |
+ |
private static final Object UNBOUNDED = new Object(); |
1235 |
+ |
|
1236 |
+ |
/** |
1237 |
|
* @serial include |
1238 |
|
*/ |
1239 |
|
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V> |
1317 |
|
*/ |
1318 |
|
|
1319 |
|
final TreeMap.Entry<K,V> absLowest() { |
1320 |
< |
TreeMap.Entry<K,V> e = |
1320 |
> |
TreeMap.Entry<K,V> e = |
1321 |
|
(fromStart ? m.getFirstEntry() : |
1322 |
|
(loInclusive ? m.getCeilingEntry(lo) : |
1323 |
|
m.getHigherEntry(lo))); |
1325 |
|
} |
1326 |
|
|
1327 |
|
final TreeMap.Entry<K,V> absHighest() { |
1328 |
< |
TreeMap.Entry<K,V> e = |
1328 |
> |
TreeMap.Entry<K,V> e = |
1329 |
|
(toEnd ? m.getLastEntry() : |
1330 |
|
(hiInclusive ? m.getFloorEntry(hi) : |
1331 |
|
m.getLowerEntry(hi))); |
1335 |
|
final TreeMap.Entry<K,V> absCeiling(K key) { |
1336 |
|
if (tooLow(key)) |
1337 |
|
return absLowest(); |
1338 |
< |
TreeMap.Entry<K,V> e = m.getCeilingEntry(key); |
1338 |
> |
TreeMap.Entry<K,V> e = m.getCeilingEntry(key); |
1339 |
|
return (e == null || tooHigh(e.key)) ? null : e; |
1340 |
|
} |
1341 |
|
|
1342 |
|
final TreeMap.Entry<K,V> absHigher(K key) { |
1343 |
|
if (tooLow(key)) |
1344 |
|
return absLowest(); |
1345 |
< |
TreeMap.Entry<K,V> e = m.getHigherEntry(key); |
1345 |
> |
TreeMap.Entry<K,V> e = m.getHigherEntry(key); |
1346 |
|
return (e == null || tooHigh(e.key)) ? null : e; |
1347 |
|
} |
1348 |
|
|
1349 |
|
final TreeMap.Entry<K,V> absFloor(K key) { |
1350 |
|
if (tooHigh(key)) |
1351 |
|
return absHighest(); |
1352 |
< |
TreeMap.Entry<K,V> e = m.getFloorEntry(key); |
1352 |
> |
TreeMap.Entry<K,V> e = m.getFloorEntry(key); |
1353 |
|
return (e == null || tooLow(e.key)) ? null : e; |
1354 |
|
} |
1355 |
|
|
1356 |
|
final TreeMap.Entry<K,V> absLower(K key) { |
1357 |
|
if (tooHigh(key)) |
1358 |
|
return absHighest(); |
1359 |
< |
TreeMap.Entry<K,V> e = m.getLowerEntry(key); |
1359 |
> |
TreeMap.Entry<K,V> e = m.getLowerEntry(key); |
1360 |
|
return (e == null || tooLow(e.key)) ? null : e; |
1361 |
|
} |
1362 |
|
|
1467 |
|
} |
1468 |
|
|
1469 |
|
public final Map.Entry<K,V> pollFirstEntry() { |
1470 |
< |
TreeMap.Entry<K,V> e = subLowest(); |
1470 |
> |
TreeMap.Entry<K,V> e = subLowest(); |
1471 |
|
Map.Entry<K,V> result = exportEntry(e); |
1472 |
|
if (e != null) |
1473 |
|
m.deleteEntry(e); |
1475 |
|
} |
1476 |
|
|
1477 |
|
public final Map.Entry<K,V> pollLastEntry() { |
1478 |
< |
TreeMap.Entry<K,V> e = subHighest(); |
1478 |
> |
TreeMap.Entry<K,V> e = subHighest(); |
1479 |
|
Map.Entry<K,V> result = exportEntry(e); |
1480 |
|
if (e != null) |
1481 |
|
m.deleteEntry(e); |
1572 |
|
abstract class SubMapIterator<T> implements Iterator<T> { |
1573 |
|
TreeMap.Entry<K,V> lastReturned; |
1574 |
|
TreeMap.Entry<K,V> next; |
1575 |
< |
final K fenceKey; |
1575 |
> |
final Object fenceKey; |
1576 |
|
int expectedModCount; |
1577 |
|
|
1578 |
|
SubMapIterator(TreeMap.Entry<K,V> first, |
1580 |
|
expectedModCount = m.modCount; |
1581 |
|
lastReturned = null; |
1582 |
|
next = first; |
1583 |
< |
fenceKey = fence == null ? null : fence.key; |
1583 |
> |
fenceKey = fence == null ? UNBOUNDED : fence.key; |
1584 |
|
} |
1585 |
|
|
1586 |
|
public final boolean hasNext() { |
1588 |
|
} |
1589 |
|
|
1590 |
|
final TreeMap.Entry<K,V> nextEntry() { |
1591 |
< |
TreeMap.Entry<K,V> e = lastReturned = next; |
1591 |
> |
TreeMap.Entry<K,V> e = next; |
1592 |
|
if (e == null || e.key == fenceKey) |
1593 |
|
throw new NoSuchElementException(); |
1594 |
|
if (m.modCount != expectedModCount) |
1595 |
|
throw new ConcurrentModificationException(); |
1596 |
|
next = successor(e); |
1597 |
+ |
lastReturned = e; |
1598 |
|
return e; |
1599 |
|
} |
1600 |
|
|
1601 |
|
final TreeMap.Entry<K,V> prevEntry() { |
1602 |
< |
TreeMap.Entry<K,V> e = lastReturned = next; |
1602 |
> |
TreeMap.Entry<K,V> e = next; |
1603 |
|
if (e == null || e.key == fenceKey) |
1604 |
|
throw new NoSuchElementException(); |
1605 |
|
if (m.modCount != expectedModCount) |
1606 |
|
throw new ConcurrentModificationException(); |
1607 |
|
next = predecessor(e); |
1608 |
+ |
lastReturned = e; |
1609 |
|
return e; |
1610 |
|
} |
1611 |
|
|
1716 |
|
} |
1717 |
|
|
1718 |
|
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
1719 |
< |
if (!inClosedRange(toKey)) |
1719 |
> |
if (!inRange(toKey, inclusive)) |
1720 |
|
throw new IllegalArgumentException("toKey out of range"); |
1721 |
|
return new AscendingSubMap(m, |
1722 |
|
fromStart, lo, loInclusive, |
1858 |
|
* @serial include |
1859 |
|
*/ |
1860 |
|
private class SubMap extends AbstractMap<K,V> |
1861 |
< |
implements SortedMap<K,V>, java.io.Serializable { |
1861 |
> |
implements SortedMap<K,V>, java.io.Serializable { |
1862 |
|
private static final long serialVersionUID = -6520786458950516097L; |
1863 |
|
private boolean fromStart = false, toEnd = false; |
1864 |
|
private K fromKey, toKey; |
1888 |
|
*/ |
1889 |
|
|
1890 |
|
static final class Entry<K,V> implements Map.Entry<K,V> { |
1891 |
< |
K key; |
1891 |
> |
K key; |
1892 |
|
V value; |
1893 |
|
Entry<K,V> left = null; |
1894 |
|
Entry<K,V> right = null; |
2043 |
|
|
2044 |
|
private static <K,V> void setColor(Entry<K,V> p, boolean c) { |
2045 |
|
if (p != null) |
2046 |
< |
p.color = c; |
2046 |
> |
p.color = c; |
2047 |
|
} |
2048 |
|
|
2049 |
|
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) { |
2299 |
|
|
2300 |
|
/** Intended to be called only from TreeSet.addAll */ |
2301 |
|
void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) { |
2302 |
< |
try { |
2303 |
< |
buildFromSorted(set.size(), set.iterator(), null, defaultVal); |
2304 |
< |
} catch (java.io.IOException cannotHappen) { |
2305 |
< |
} catch (ClassNotFoundException cannotHappen) { |
2306 |
< |
} |
2302 |
> |
try { |
2303 |
> |
buildFromSorted(set.size(), set.iterator(), null, defaultVal); |
2304 |
> |
} catch (java.io.IOException cannotHappen) { |
2305 |
> |
} catch (ClassNotFoundException cannotHappen) { |
2306 |
> |
} |
2307 |
|
} |
2308 |
|
|
2309 |
|
|
2338 |
|
* This cannot occur if str is null. |
2339 |
|
*/ |
2340 |
|
private void buildFromSorted(int size, Iterator it, |
2341 |
< |
java.io.ObjectInputStream str, |
2342 |
< |
V defaultVal) |
2341 |
> |
java.io.ObjectInputStream str, |
2342 |
> |
V defaultVal) |
2343 |
|
throws java.io.IOException, ClassNotFoundException { |
2344 |
|
this.size = size; |
2345 |
|
root = buildFromSorted(0, 0, size-1, computeRedLevel(size), |
2346 |
< |
it, str, defaultVal); |
2346 |
> |
it, str, defaultVal); |
2347 |
|
} |
2348 |
|
|
2349 |
|
/** |
2361 |
|
* Must be equal to computeRedLevel for tree of this size. |
2362 |
|
*/ |
2363 |
|
private final Entry<K,V> buildFromSorted(int level, int lo, int hi, |
2364 |
< |
int redLevel, |
2365 |
< |
Iterator it, |
2366 |
< |
java.io.ObjectInputStream str, |
2367 |
< |
V defaultVal) |
2364 |
> |
int redLevel, |
2365 |
> |
Iterator it, |
2366 |
> |
java.io.ObjectInputStream str, |
2367 |
> |
V defaultVal) |
2368 |
|
throws java.io.IOException, ClassNotFoundException { |
2369 |
|
/* |
2370 |
|
* Strategy: The root is the middlemost element. To get to it, we |
2380 |
|
|
2381 |
|
if (hi < lo) return null; |
2382 |
|
|
2383 |
< |
int mid = (lo + hi) / 2; |
2383 |
> |
int mid = (lo + hi) >>> 1; |
2384 |
|
|
2385 |
|
Entry<K,V> left = null; |
2386 |
|
if (lo < mid) |
2387 |
|
left = buildFromSorted(level+1, lo, mid - 1, redLevel, |
2388 |
< |
it, str, defaultVal); |
2388 |
> |
it, str, defaultVal); |
2389 |
|
|
2390 |
|
// extract key and/or value from iterator or stream |
2391 |
|
K key; |
2417 |
|
|
2418 |
|
if (mid < hi) { |
2419 |
|
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, |
2420 |
< |
it, str, defaultVal); |
2420 |
> |
it, str, defaultVal); |
2421 |
|
middle.right = right; |
2422 |
|
right.parent = middle; |
2423 |
|
} |