Codebeispiel für TreeMap in der Java-Sammlung
- 黄舟Original
- 2017-03-13 14:37:082133Durchsuche
Die Beziehung zwischen TreeMap und Map ist wie folgt:
TreeMap-Einführung:
( 1) TreeMap ist ein geordneter Schlüsselwertsatz, der durch Rot-Schwarz-Bäume implementiert wird.
(2) TreeMap erbt von AbstractMap, es handelt sich also um eine Map und einen Schlüsselwertsatz.
(3) TreeMap implementiert die Navigable-Schnittstelle und unterstützt eine Reihe von Navigationsmethoden. TreeMap ist eine geordnete Sammlung
(4) Es implementiert die Cloneable-Schnittstelle und kann geklont werden
(5) TreeMap implementiert die Serializable-Schnittstelle, die die Serialisierung unterstützt
(6) TreeMap basiert auf der digitalen Rot-Schwarz-Baumdarstellung und die Zuordnung wird nach der natürlichen Reihenfolge seiner Schlüssel sortiert
TreeMap-Haupt-API:
Entrya8093152e673feb7aba1828c43532094 ceilingEntry(K key) K ceilingKey(K key) clear() Object clone() Comparatoradea50645660c00d864f8df96cd78b01 comparator() containsKey(Object key) NavigableSeta8093152e673feb7aba1828c43532094 descendingKeySet() NavigableMapa8093152e673feb7aba1828c43532094 descendingMap() Set<a8093152e673feb7aba1828c43532094> entrySet() Entrya8093152e673feb7aba1828c43532094 firstEntry() K firstKey() Entrya8093152e673feb7aba1828c43532094 floorEntry(K key) K floorKey(K key) V get(Object key) NavigableMapa8093152e673feb7aba1828c43532094 headMap(K toinclusive) SortedMapa8093152e673feb7aba1828c43532094 headMap(K toExclusive) Entrya8093152e673feb7aba1828c43532094 higherEntry(K key) K higherKey(K key) isEmpty() Seta8093152e673feb7aba1828c43532094 keySet() Entrya8093152e673feb7aba1828c43532094 lastEntry() K lastKey() Entrya8093152e673feb7aba1828c43532094 lowerEntry(K key) K lowerKey(K key) NavigableSeta8093152e673feb7aba1828c43532094 navigableKeySet() Entrya8093152e673feb7aba1828c43532094 pollFirstEntry() Entrya8093152e673feb7aba1828c43532094 pollLastEntry() V put(K keyV value) V remove(Object key) size() SortedMapa8093152e673feb7aba1828c43532094 subMap(K fromInclusiveK toExclusive) NavigableMapa8093152e673feb7aba1828c43532094 subMap(K fromfromInclusiveK totoInclusive) NavigableMapa8093152e673feb7aba1828c43532094 tailMap(K frominclusive) SortedMapa8093152e673feb7aba1828c43532094 tailMap(K fromInclusive)
TreeMap-Traversalmethode
(1) Traversieren Sie den Schlüsselwert Paare von TreeMap: Gemäß EntrySet() Rufen Sie die Sammlung „Schlüssel-Wert-Paar“ von TreeMap ab und durchlaufen Sie die Sammlung der Schlüssel-Wert-Paare über Iterator.
String key=Integer value=Iterator iterator=map.entrySet().iterator()(iterator.hasNext())
{
Map.Entry entry=(Map.Entry)iterator.next() key=(String) entry.getKey() value=(Integer)entry.getValue()}
(2) Durchlaufen Sie die Schlüssel von TreeMap: Erhalten Sie den gemäß keySet () festgelegten „Schlüssel“ und durchlaufen Sie den Schlüsselsatz durch den Iterator.
String key = Integer integ = Iterator iter = map.keySet().iterator()(iter.hasNext()) {
key = (String)iter.next() integ = (Integer)map.get(key)}
(3) Durchlaufen Sie die Werte von TreeMap: Erhalten Sie den Wertesatz entsprechend den Werten und durchlaufen Sie den Wertesatz durch Iterator.
Integer value = Collection c = map.values()Iterator iter= c.iterator()(iter.hasNext())
{
value = (Integer)iter.next()}
TreeMap-Beispielcode:
public class Hello {
public static void main(String[] args) {
testTreeMapOridinaryAPIs();
testSubMapAPIs();
}
private static void testTreeMapOridinaryAPIs() {
// 初始化随机种子
Random r = new Random();
// 新建TreeMap
TreeMap tmap = new TreeMap();
// 添加操作
tmap.put("one", r.nextInt(10));
tmap.put("two", r.nextInt(10));
tmap.put("three", r.nextInt(10));
tmap.put("four", r.nextInt(10));
tmap.put("five", r.nextInt(10));
tmap.put("six", r.nextInt(10));
System.out.printf("\n ---- testTreeMapOridinaryAPIs ----\n");
// 打印出TreeMap
System.out.printf("%s\n",tmap );
// 通过Iterator遍历key-value
Iterator iter = tmap.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
System.out.printf("next : %s - %s\n", entry.getKey(), entry.getValue());
}
// TreeMap的键值对个数
System.out.printf("size: %s\n", tmap.size());
// containsKey(Object key) :是否包含键key
System.out.printf("contains key two : %s\n",tmap.containsKey("two"));
System.out.printf("contains key five : %s\n",tmap.containsKey("five"));
// containsValue(Object value) :是否包含值value
System.out.printf("contains value 0 : %s\n",tmap.containsValue(new Integer(0)));
// remove(Object key) ： 删除键key对应的键值对
tmap.remove("three");
System.out.printf("tmap:%s\n",tmap );
// clear() ： 清空TreeMap
tmap.clear();
// isEmpty() : TreeMap是否为空
System.out.printf("%s\n", (tmap.isEmpty()?"tmap is empty":"tmap is not empty") );
}
public static void testSubMapAPIs() {
// 新建TreeMap
TreeMap tmap = new TreeMap();
// 添加“键值对”
tmap.put("a", 101);
tmap.put("b", 102);
tmap.put("c", 103);
tmap.put("d", 104);
tmap.put("e", 105);
System.out.printf("\n ---- testSubMapAPIs ----\n");
// 打印出TreeMap
System.out.printf("tmap:\n\t%s\n", tmap);
// 测试 headMap(K toKey)
System.out.printf("tmap.headMap(\"c\"):\n\t%s\n", tmap.headMap("c"));
// 测试 headMap(K toKey, boolean inclusive)
System.out.printf("tmap.headMap(\"c\", true):\n\t%s\n", tmap.headMap("c", true));
System.out.printf("tmap.headMap(\"c\", false):\n\t%s\n", tmap.headMap("c", false));
// 测试 tailMap(K fromKey)
System.out.printf("tmap.tailMap(\"c\"):\n\t%s\n", tmap.tailMap("c"));
// 测试 tailMap(K fromKey, boolean inclusive)
System.out.printf("tmap.tailMap(\"c\", true):\n\t%s\n", tmap.tailMap("c", true));
System.out.printf("tmap.tailMap(\"c\", false):\n\t%s\n", tmap.tailMap("c", false));
// 测试 subMap(K fromKey, K toKey)
System.out.printf("tmap.subMap(\"a\", \"c\"):\n\t%s\n", tmap.subMap("a", "c"));
// 测试
System.out.printf("tmap.subMap(\"a\", true, \"c\", true):\n\t%s\n",
tmap.subMap("a", true, "c", true));
System.out.printf("tmap.subMap(\"a\", true, \"c\", false):\n\t%s\n",
tmap.subMap("a", true, "c", false));
System.out.printf("tmap.subMap(\"a\", false, \"c\", true):\n\t%s\n",
tmap.subMap("a", false, "c", true));
System.out.printf("tmap.subMap(\"a\", false, \"c\", false):\n\t%s\n",
tmap.subMap("a", false, "c", false));
// 测试 navigableKeySet()
System.out.printf("tmap.navigableKeySet():\n\t%s\n", tmap.navigableKeySet());
// 测试 descendingKeySet()
System.out.printf("tmap.descendingKeySet():\n\t%s\n", tmap.descendingKeySet());
}
public static void testNavigableMapAPIs() {
// 新建TreeMap
NavigableMap nav = new TreeMap();
// 添加“键值对”
nav.put("aaa", 111);
nav.put("bbb", 222);
nav.put("eee", 333);
nav.put("ccc", 555);
nav.put("ddd", 444);
System.out.printf("\n ---- testNavigableMapAPIs ----\n");
// 打印出TreeMap
System.out.printf("Whole list:%s%n", nav);
// 获取第一个key、第一个Entry
System.out.printf("First key: %s\tFirst entry: %s%n",nav.firstKey(), nav.firstEntry());
// 获取最后一个key、最后一个Entry
System.out.printf("Last key: %s\tLast entry: %s%n",nav.lastKey(), nav.lastEntry());
// 获取“小于/等于bbb”的最大键值对
System.out.printf("Key floor before bbb: %s%n",nav.floorKey("bbb"));
// 获取“小于bbb”的最大键值对
System.out.printf("Key lower before bbb: %s%n", nav.lowerKey("bbb"));
// 获取“大于/等于bbb”的最小键值对
System.out.printf("Key ceiling after ccc: %s%n",nav.ceilingKey("ccc"));
// 获取“大于bbb”的最小键值对
System.out.printf("Key higher after ccc: %s%n\n",nav.higherKey("ccc"));
}
}
Laufergebnisse:
---- testTreeMapOridinaryAPIs ----
{five=5, four=5, one=3, six=8, three=1, two=0}
next : five - 5
next : four - 5
next : one - 3
next : six - 8
next : three - 1
next : two - 0
size: 6
contains key two : true
contains key five : true
contains value 0 : true
tmap:{five=5, four=5, one=3, six=8, two=0}
tmap is empty
---- testSubMapAPIs ----
tmap:
{a=101, b=102, c=103, d=104, e=105}
tmap.headMap("c"):
{a=101, b=102}
tmap.headMap("c", true):
{a=101, b=102, c=103}
tmap.headMap("c", false):
{a=101, b=102}
tmap.tailMap("c"):
{c=103, d=104, e=105}
tmap.tailMap("c", true):
{c=103, d=104, e=105}
tmap.tailMap("c", false):
{d=104, e=105}
tmap.subMap("a", "c"):
{a=101, b=102}
tmap.subMap("a", true, "c", true):
{a=101, b=102, c=103}
tmap.subMap("a", true, "c", false):
{a=101, b=102}
tmap.subMap("a", false, "c", true):
{b=102, c=103}
tmap.subMap("a", false, "c", false):
{b=102}
tmap.navigableKeySet():
[a, b, c, d, e]
tmap.descendingKeySet():
[e, d, c, b, a]Quellcode der SortedMap-Schnittstelle basierend auf Java8:
public interface SortedMapb77a8d9c3c319e50d4b02a976b347910 extends Mapb77a8d9c3c319e50d4b02a976b347910 {
Comparator99be4058f294b5c4a6207ddd3216ce19 comparator();
SortedMapb77a8d9c3c319e50d4b02a976b347910 subMap(K fromKey, K toKey);
SortedMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey);
SortedMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey);
K firstKey();
K lastKey();
Set245c3adc26563b673f7297c0b3777639 keySet();
Collectiond94943c0b4933ad8cac500132f64757f values();
Set3b0b8c50db3add957fd22f5a448ffe65> entrySet();
}
Quellcode der navigierbaren Schnittstelle basierend auf Java8:
public interface NavigableMapb77a8d9c3c319e50d4b02a976b347910 extends SortedMapb77a8d9c3c319e50d4b02a976b347910 {
Map.Entryb77a8d9c3c319e50d4b02a976b347910 lowerEntry(K key);
K lowerKey(K key);
Map.Entryb77a8d9c3c319e50d4b02a976b347910 floorEntry(K key);
K floorKey(K key);
Map.Entryb77a8d9c3c319e50d4b02a976b347910 ceilingEntry(K key);
K ceilingKey(K key);
Map.Entryb77a8d9c3c319e50d4b02a976b347910 higherEntry(K key);
K higherKey(K key);
Map.Entryb77a8d9c3c319e50d4b02a976b347910 firstEntry();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 lastEntry();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 pollFirstEntry();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 pollLastEntry();
NavigableMapb77a8d9c3c319e50d4b02a976b347910 descendingMap();
NavigableSet245c3adc26563b673f7297c0b3777639 navigableKeySet();
NavigableSet245c3adc26563b673f7297c0b3777639 descendingKeySet();
NavigableMapb77a8d9c3c319e50d4b02a976b347910 subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
NavigableMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey, boolean inclusive);
NavigableMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey, boolean inclusive);
SortedMapb77a8d9c3c319e50d4b02a976b347910 subMap(K fromKey, K toKey);
SortedMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey);
SortedMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey);
}
TreeMap-Quellcode basierend auf Java8:
public class TreeMapb77a8d9c3c319e50d4b02a976b347910extends AbstractMapb77a8d9c3c319e50d4b02a976b347910
implements NavigableMapb77a8d9c3c319e50d4b02a976b347910, Cloneable, java.io.Serializable
{
private final Comparator99be4058f294b5c4a6207ddd3216ce19 comparator;//比较器
private transient Entryb77a8d9c3c319e50d4b02a976b347910 root;//根节点
private transient int size = 0;//起始个数
private transient int modCount = 0;//tree改变次数
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator99be4058f294b5c4a6207ddd3216ce19 comparator) {
this.comparator = comparator;
}
public TreeMap(Map11df7d36ed146da2cbbceeacbc3a1d74 m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap2f9dcabf899c8b231e84e7d113f62fa8 m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
//获得个数
public int size() {
return size;
}
//是否含有某个key
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
//是否还有某个值
public boolean containsValue(Object value) {
for (Entryb77a8d9c3c319e50d4b02a976b347910 e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
//通过key获得值
public V get(Object key) {
Entryb77a8d9c3c319e50d4b02a976b347910 p = getEntry(key);
return (p==null ? null : p.value);
}
//比较器
public Comparator99be4058f294b5c4a6207ddd3216ce19 comparator() {
return comparator;
}
//获得第一个key
public K firstKey() {
return key(getFirstEntry());
}
//获得最后一个key
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
*/
//拷贝某个特定的map到这个map
public void putAll(Map11df7d36ed146da2cbbceeacbc3a1d74 map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator6b3d0130bba23ae47fe2b8e8cddf0195 c = ((SortedMapc3f2d894ed311a524f031af7191b9ddc)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
*/
//根据某个key获得entry
final Entryb77a8d9c3c319e50d4b02a976b347910 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")
Comparable99be4058f294b5c4a6207ddd3216ce19 k = (Comparable99be4058f294b5c4a6207ddd3216ce19) key;
Entryb77a8d9c3c319e50d4b02a976b347910 p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp aae9587015115356e61d12fb8674d199 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.)
*/
//通过比较器来比较key，返回entry
final Entryb77a8d9c3c319e50d4b02a976b347910 getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator99be4058f294b5c4a6207ddd3216ce19 cpr = comparator;
if (cpr != null) {
Entryb77a8d9c3c319e50d4b02a976b347910 p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp d0c3abbb5622f51845b596aec0a87fb2 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}.
*/
//获得与key关系最近的entry,上限
final Entryb77a8d9c3c319e50d4b02a976b347910 getCeilingEntry(K key) {
Entryb77a8d9c3c319e50d4b02a976b347910 p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp d80917fb16847fc9fb503ca32b02c704 0) {
if (p.right != null) {
p = p.right;
} else {
Entryb77a8d9c3c319e50d4b02a976b347910 parent = p.parent;
Entryb77a8d9c3c319e50d4b02a976b347910 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}.
*/
//获得与key关系最近的entry,下限
final Entryb77a8d9c3c319e50d4b02a976b347910 getFloorEntry(K key) {
Entryb77a8d9c3c319e50d4b02a976b347910 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 {
Entryb77a8d9c3c319e50d4b02a976b347910 parent = p.parent;
Entryb77a8d9c3c319e50d4b02a976b347910 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}.
*/
//比某个key大的entry
final Entryb77a8d9c3c319e50d4b02a976b347910 getHigherEntry(K key) {
Entryb77a8d9c3c319e50d4b02a976b347910 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 {
Entryb77a8d9c3c319e50d4b02a976b347910 parent = p.parent;
Entryb77a8d9c3c319e50d4b02a976b347910 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}.
*/
//获得某个key小于最接近的entry
final Entryb77a8d9c3c319e50d4b02a976b347910 getLowerEntry(K key) {
Entryb77a8d9c3c319e50d4b02a976b347910 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 {
Entryb77a8d9c3c319e50d4b02a976b347910 parent = p.parent;
Entryb77a8d9c3c319e50d4b02a976b347910 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
*/
//插入key-value值
public V put(K key, V value) {
Entryb77a8d9c3c319e50d4b02a976b347910 t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entrya8093152e673feb7aba1828c43532094(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entryb77a8d9c3c319e50d4b02a976b347910 parent;
// split comparator and comparable paths
Comparator99be4058f294b5c4a6207ddd3216ce19 cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp d18c100fefddae3a79e97cb253dc3d81 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable99be4058f294b5c4a6207ddd3216ce19 k = (Comparable99be4058f294b5c4a6207ddd3216ce19) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp d18c100fefddae3a79e97cb253dc3d81 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entryb77a8d9c3c319e50d4b02a976b347910 e = new Entrya8093152e673feb7aba1828c43532094(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
*/
//删掉某个key，并返回value
public V remove(Object key) {
Entryb77a8d9c3c319e50d4b02a976b347910 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() {
TreeMapc3f2d894ed311a524f031af7191b9ddc clone;
try {
clone = (TreeMapc3f2d894ed311a524f031af7191b9ddc) 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
*/
//获得第一个entry
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 firstEntry() {
return exportEntry(getFirstEntry());
}
/**
* @since 1.6
*/
//最后一个entry
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 lastEntry() {
return exportEntry(getLastEntry());
}
/**
* @since 1.6
*/
//弹出第一个entry，并删除
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 pollFirstEntry() {
Entryb77a8d9c3c319e50d4b02a976b347910 p = getFirstEntry();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 result = exportEntry(p);
if (p != null)
deleteEntry(p);
return result;
}
/**
* @since 1.6
*/
//弹出最后一个entry，并删除
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 pollLastEntry() {
Entryb77a8d9c3c319e50d4b02a976b347910 p = getLastEntry();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 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 KeySet245c3adc26563b673f7297c0b3777639 navigableKeySet;
private transient NavigableMapb77a8d9c3c319e50d4b02a976b347910 descendingMap;
/**
* Returns a {@link Set} view of the keys contained in this map.
*
* e388a4556c0f65e1904146cc1a846beeThe set's iterator returns the keys in ascending order.
* The set's spliterator is
* 907fae80ddef53131f3292ee4f81644b47bdf838fe1f241804499a8943350a02late-binding5db79b134e9f6b82c0b36e0489ee08edd1c6776b927dc33c5d9114750b586338,
* 907fae80ddef53131f3292ee4f81644bfail-fastd1c6776b927dc33c5d9114750b586338, 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.
*
* e388a4556c0f65e1904146cc1a846beeThe 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 Set245c3adc26563b673f7297c0b3777639 keySet() {
return navigableKeySet();
}
/**
* @since 1.6
*/
public NavigableSet245c3adc26563b673f7297c0b3777639 navigableKeySet() {
KeySet245c3adc26563b673f7297c0b3777639 nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySeta8093152e673feb7aba1828c43532094(this));
}
/**
* @since 1.6
*/
public NavigableSet245c3adc26563b673f7297c0b3777639 descendingKeySet() {
return descendingMap().navigableKeySet();
}
/**
* Returns a {@link Collection} view of the values contained in this map.
*
* e388a4556c0f65e1904146cc1a846beeThe collection's iterator returns the values in ascending order
* of the corresponding keys. The collection's spliterator is
* 907fae80ddef53131f3292ee4f81644b47bdf838fe1f241804499a8943350a02late-binding5db79b134e9f6b82c0b36e0489ee08edd1c6776b927dc33c5d9114750b586338,
* 907fae80ddef53131f3292ee4f81644bfail-fastd1c6776b927dc33c5d9114750b586338, and additionally reports {@link Spliterator#ORDERED}
* with an encounter order that is ascending order of the corresponding
* keys.
*
* e388a4556c0f65e1904146cc1a846beeThe 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 Collectiond94943c0b4933ad8cac500132f64757f values() {
Collectiond94943c0b4933ad8cac500132f64757f vs = values;
return (vs != null) ? vs : (values = new Values());
}
/**
* Returns a {@link Set} view of the mappings contained in this map.
*
* e388a4556c0f65e1904146cc1a846beeThe set's iterator returns the entries in ascending key order. The
* sets's spliterator is
* 907fae80ddef53131f3292ee4f81644b47bdf838fe1f241804499a8943350a02late-binding5db79b134e9f6b82c0b36e0489ee08edd1c6776b927dc33c5d9114750b586338,
* 907fae80ddef53131f3292ee4f81644bfail-fastd1c6776b927dc33c5d9114750b586338, and additionally reports {@link Spliterator#SORTED} and
* {@link Spliterator#ORDERED} with an encounter order that is ascending key
* order.
*
* e388a4556c0f65e1904146cc1a846beeThe 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.Entryb77a8d9c3c319e50d4b02a976b347910> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
/**
* @since 1.6
*/
public NavigableMap81079595401ce1162abe0d5a660013d8 descendingMap() {
NavigableMap81079595401ce1162abe0d5a660013d8 km = descendingMap;
return (km != null) ? km :
(descendingMap = new DescendingSubMapa8093152e673feb7aba1828c43532094(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 NavigableMapb77a8d9c3c319e50d4b02a976b347910 subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMapa8093152e673feb7aba1828c43532094(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 NavigableMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey, boolean inclusive) {
return new AscendingSubMapa8093152e673feb7aba1828c43532094(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 NavigableMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey, boolean inclusive) {
return new AscendingSubMapa8093152e673feb7aba1828c43532094(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 SortedMapb77a8d9c3c319e50d4b02a976b347910 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 SortedMapb77a8d9c3c319e50d4b02a976b347910 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 SortedMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey) {
return tailMap(fromKey, true);
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
Entryb77a8d9c3c319e50d4b02a976b347910 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) {
Entryb77a8d9c3c319e50d4b02a976b347910 p = getEntry(key);
if (p!=null) {
V oldValue = p.value;
p.value = value;
return oldValue;
}
return null;
}
@Override
public void forEach(BiConsumer8d7aa65c8046027ea338ee53f830d46e action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
for (Entry81079595401ce1162abe0d5a660013d8 e = getFirstEntry(); e != null; e = successor(e)) {
action.accept(e.key, e.value);
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
@Override
public void replaceAll(BiFunction0a1b16d994d218d93e3e331534b14776 function) {
Objects.requireNonNull(function);
int expectedModCount = modCount;
for (Entry81079595401ce1162abe0d5a660013d8 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 AbstractCollectiond94943c0b4933ad8cac500132f64757f {
public Iteratord94943c0b4933ad8cac500132f64757f 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 (Entryb77a8d9c3c319e50d4b02a976b347910 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 Spliteratord94943c0b4933ad8cac500132f64757f spliterator() {
return new ValueSpliteratorb77a8d9c3c319e50d4b02a976b347910(TreeMap.this, null, null, 0, -1, 0);
}
}
class EntrySet extends AbstractSet<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
public Iterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> iterator() {
return new EntryIterator(getFirstEntry());
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entryc3f2d894ed311a524f031af7191b9ddc entry = (Map.Entryc3f2d894ed311a524f031af7191b9ddc) o;
Object value = entry.getValue();
Entryb77a8d9c3c319e50d4b02a976b347910 p = getEntry(entry.getKey());
return p != null && valEquals(p.getValue(), value);
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entryc3f2d894ed311a524f031af7191b9ddc entry = (Map.Entryc3f2d894ed311a524f031af7191b9ddc) o;
Object value = entry.getValue();
Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910> spliterator() {
return new EntrySpliteratorb77a8d9c3c319e50d4b02a976b347910(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.
*/
Iterator245c3adc26563b673f7297c0b3777639 keyIterator() {
return new KeyIterator(getFirstEntry());
}
Iterator245c3adc26563b673f7297c0b3777639 descendingKeyIterator() {
return new DescendingKeyIterator(getLastEntry());
}
static final class KeySet1a4db2c2c2313771e5742b6debf617a1 extends AbstractSet1a4db2c2c2313771e5742b6debf617a1 implements NavigableSet1a4db2c2c2313771e5742b6debf617a1 {
private final NavigableMap166a37135fcf5cb4afec81f553acafe1 m;
KeySet(NavigableMapab4b07cf3a065a76b42638b44364603a map) { m = map; }
public Iterator1a4db2c2c2313771e5742b6debf617a1 iterator() {
if (m instanceof TreeMap)
return ((TreeMapab4b07cf3a065a76b42638b44364603a)m).keyIterator();
else
return ((TreeMap.NavigableSubMapab4b07cf3a065a76b42638b44364603a)m).keyIterator();
}
public Iterator1a4db2c2c2313771e5742b6debf617a1 descendingIterator() {
if (m instanceof TreeMap)
return ((TreeMapab4b07cf3a065a76b42638b44364603a)m).descendingKeyIterator();
else
return ((TreeMap.NavigableSubMapab4b07cf3a065a76b42638b44364603a)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 Comparatordc5aa4f4a38f04210c53c469d00050f9 comparator() { return m.comparator(); }
public E pollFirst() {
Map.Entryab4b07cf3a065a76b42638b44364603a e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public E pollLast() {
Map.Entryab4b07cf3a065a76b42638b44364603a e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
public boolean remove(Object o) {
int oldSize = size();
m.remove(o);
return size() != oldSize;
}
public NavigableSet1a4db2c2c2313771e5742b6debf617a1 subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new KeySeta8093152e673feb7aba1828c43532094(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
public NavigableSet1a4db2c2c2313771e5742b6debf617a1 headSet(E toElement, boolean inclusive) {
return new KeySeta8093152e673feb7aba1828c43532094(m.headMap(toElement, inclusive));
}
public NavigableSet1a4db2c2c2313771e5742b6debf617a1 tailSet(E fromElement, boolean inclusive) {
return new KeySeta8093152e673feb7aba1828c43532094(m.tailMap(fromElement, inclusive));
}
public SortedSet1a4db2c2c2313771e5742b6debf617a1 subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
public SortedSet1a4db2c2c2313771e5742b6debf617a1 headSet(E toElement) {
return headSet(toElement, false);
}
public SortedSet1a4db2c2c2313771e5742b6debf617a1 tailSet(E fromElement) {
return tailSet(fromElement, true);
}
public NavigableSet1a4db2c2c2313771e5742b6debf617a1 descendingSet() {
return new KeySeta8093152e673feb7aba1828c43532094(m.descendingMap());
}
public Spliterator1a4db2c2c2313771e5742b6debf617a1 spliterator() {
return keySpliteratorFor(m);
}
}
/**
* Base class for TreeMap Iterators
*/
abstract class PrivateEntryIterator8742468051c85b06f0a0af9e3e506b5c implements Iterator8742468051c85b06f0a0af9e3e506b5c {
Entryb77a8d9c3c319e50d4b02a976b347910 next;
Entryb77a8d9c3c319e50d4b02a976b347910 lastReturned;
int expectedModCount;
PrivateEntryIterator(Entryb77a8d9c3c319e50d4b02a976b347910 first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
final Entryb77a8d9c3c319e50d4b02a976b347910 nextEntry() {
Entryb77a8d9c3c319e50d4b02a976b347910 e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
final Entryb77a8d9c3c319e50d4b02a976b347910 prevEntry() {
Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910> {
EntryIterator(Entryb77a8d9c3c319e50d4b02a976b347910 first) {
super(first);
}
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 next() {
return nextEntry();
}
}
final class ValueIterator extends PrivateEntryIteratord94943c0b4933ad8cac500132f64757f {
ValueIterator(Entryb77a8d9c3c319e50d4b02a976b347910 first) {
super(first);
}
public V next() {
return nextEntry().value;
}
}
final class KeyIterator extends PrivateEntryIterator245c3adc26563b673f7297c0b3777639 {
KeyIterator(Entryb77a8d9c3c319e50d4b02a976b347910 first) {
super(first);
}
public K next() {
return nextEntry().key;
}
}
final class DescendingKeyIterator extends PrivateEntryIterator245c3adc26563b673f7297c0b3777639 {
DescendingKeyIterator(Entryb77a8d9c3c319e50d4b02a976b347910 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 ? ((Comparable99be4058f294b5c4a6207ddd3216ce19)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 b77a8d9c3c319e50d4b02a976b347910 Map.Entryb77a8d9c3c319e50d4b02a976b347910 exportEntry(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntrya8093152e673feb7aba1828c43532094(e);
}
/**
* Return key for entry, or null if null
*/
static b77a8d9c3c319e50d4b02a976b347910 K keyOrNull(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e) {
return (e == null) ? null : e.key;
}
/**
* Returns the key corresponding to the specified Entry.
* @throws NoSuchElementException if the Entry is null
*/
static 245c3adc26563b673f7297c0b3777639 K key(Entry419e368910ac9b50061d48b64ec849c7 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 NavigableSubMapb77a8d9c3c319e50d4b02a976b347910 extends AbstractMapb77a8d9c3c319e50d4b02a976b347910
implements NavigableMapb77a8d9c3c319e50d4b02a976b347910, java.io.Serializable {
private static final long serialVersionUID = -2102997345730753016L;
/**
* The backing map.
*/
final TreeMapb77a8d9c3c319e50d4b02a976b347910 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(TreeMapb77a8d9c3c319e50d4b02a976b347910 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 ab01c15bfdd6ece5c589f96345e9691c 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.Entryb77a8d9c3c319e50d4b02a976b347910 absLowest() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 absHighest() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e =
(toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
}
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 absCeiling(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 absHigher(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = m.getHigherEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 absFloor(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 absLower(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = m.getLowerEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
/** Returns the absolute high fence for ascending traversal */
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 absHighFence() {
return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
/** Return the absolute low fence for descending traversal */
final TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 subLowest();
abstract TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subHighest();
abstract TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subCeiling(K key);
abstract TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subHigher(K key);
abstract TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subFloor(K key);
abstract TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subLower(K key);
/** Returns ascending iterator from the perspective of this submap */
abstract Iterator245c3adc26563b673f7297c0b3777639 keyIterator();
abstract Spliterator245c3adc26563b673f7297c0b3777639 keySpliterator();
/** Returns descending iterator from the perspective of this submap */
abstract Iterator245c3adc26563b673f7297c0b3777639 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.Entryb77a8d9c3c319e50d4b02a976b347910 ceilingEntry(K key) {
return exportEntry(subCeiling(key));
}
public final K ceilingKey(K key) {
return keyOrNull(subCeiling(key));
}
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 higherEntry(K key) {
return exportEntry(subHigher(key));
}
public final K higherKey(K key) {
return keyOrNull(subHigher(key));
}
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 floorEntry(K key) {
return exportEntry(subFloor(key));
}
public final K floorKey(K key) {
return keyOrNull(subFloor(key));
}
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 firstEntry() {
return exportEntry(subLowest());
}
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 lastEntry() {
return exportEntry(subHighest());
}
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 pollFirstEntry() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = subLowest();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
return result;
}
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 pollLastEntry() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = subHighest();
Map.Entryb77a8d9c3c319e50d4b02a976b347910 result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
return result;
}
// Views
transient NavigableMapb77a8d9c3c319e50d4b02a976b347910 descendingMapView;
transient EntrySetView entrySetView;
transient KeySet245c3adc26563b673f7297c0b3777639 navigableKeySetView;
public final NavigableSet245c3adc26563b673f7297c0b3777639 navigableKeySet() {
KeySet245c3adc26563b673f7297c0b3777639 nksv = navigableKeySetView;
return (nksv != null) ? nksv :
(navigableKeySetView = new TreeMap.KeySeta8093152e673feb7aba1828c43532094(this));
}
public final Set245c3adc26563b673f7297c0b3777639 keySet() {
return navigableKeySet();
}
public NavigableSet245c3adc26563b673f7297c0b3777639 descendingKeySet() {
return descendingMap().navigableKeySet();
}
public final SortedMapb77a8d9c3c319e50d4b02a976b347910 subMap(K fromKey, K toKey) {
return subMap(fromKey, true, toKey, false);
}
public final SortedMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey) {
return headMap(toKey, false);
}
public final SortedMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey) {
return tailMap(fromKey, true);
}
// View classes
abstract class EntrySetView extends AbstractSet<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
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;
Iterator6b3d0130bba23ae47fe2b8e8cddf0195 i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
}
public boolean isEmpty() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 n = absLowest();
return n == null || tooHigh(n.key);
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entryc3f2d894ed311a524f031af7191b9ddc entry = (Map.Entryc3f2d894ed311a524f031af7191b9ddc) o;
Object key = entry.getKey();
if (!inRange(key))
return false;
TreeMap.Entryc3f2d894ed311a524f031af7191b9ddc 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.Entryc3f2d894ed311a524f031af7191b9ddc entry = (Map.Entryc3f2d894ed311a524f031af7191b9ddc) o;
Object key = entry.getKey();
if (!inRange(key))
return false;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 node = m.getEntry(key);
if (node!=null && valEquals(node.getValue(),
entry.getValue())) {
m.deleteEntry(node);
return true;
}
return false;
}
}
/**
* Iterators for SubMaps
*/
abstract class SubMapIterator8742468051c85b06f0a0af9e3e506b5c implements Iterator8742468051c85b06f0a0af9e3e506b5c {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 lastReturned;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 next;
final Object fenceKey;
int expectedModCount;
SubMapIterator(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 first,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 nextEntry() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910 prevEntry() {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910> {
SubMapEntryIterator(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 first,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence) {
super(first, fence);
}
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 next() {
return nextEntry();
}
public void remove() {
removeAscending();
}
}
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
DescendingSubMapEntryIterator(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 last,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence) {
super(last, fence);
}
public Map.Entryb77a8d9c3c319e50d4b02a976b347910 next() {
return prevEntry();
}
public void remove() {
removeDescending();
}
}
// Implement minimal Spliterator as KeySpliterator backup
final class SubMapKeyIterator extends SubMapIterator245c3adc26563b673f7297c0b3777639
implements Spliterator245c3adc26563b673f7297c0b3777639 {
SubMapKeyIterator(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 first,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence) {
super(first, fence);
}
public K next() {
return nextEntry().key;
}
public void remove() {
removeAscending();
}
public Spliterator245c3adc26563b673f7297c0b3777639 trySplit() {
return null;
}
public void forEachRemaining(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
while (hasNext())
action.accept(next());
}
public boolean tryAdvance(Consumer99be4058f294b5c4a6207ddd3216ce19 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 Comparator99be4058f294b5c4a6207ddd3216ce19 getComparator() {
return NavigableSubMap.this.comparator();
}
}
final class DescendingSubMapKeyIterator extends SubMapIterator245c3adc26563b673f7297c0b3777639
implements Spliterator245c3adc26563b673f7297c0b3777639 {
DescendingSubMapKeyIterator(TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 last,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence) {
super(last, fence);
}
public K next() {
return prevEntry().key;
}
public void remove() {
removeDescending();
}
public Spliterator245c3adc26563b673f7297c0b3777639 trySplit() {
return null;
}
public void forEachRemaining(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
while (hasNext())
action.accept(next());
}
public boolean tryAdvance(Consumer99be4058f294b5c4a6207ddd3216ce19 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 AscendingSubMapb77a8d9c3c319e50d4b02a976b347910 extends NavigableSubMapb77a8d9c3c319e50d4b02a976b347910 {
private static final long serialVersionUID = 912986545866124060L;
AscendingSubMap(TreeMapb77a8d9c3c319e50d4b02a976b347910 m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
public Comparator99be4058f294b5c4a6207ddd3216ce19 comparator() {
return m.comparator();
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 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 AscendingSubMapa8093152e673feb7aba1828c43532094(m,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new AscendingSubMapa8093152e673feb7aba1828c43532094(m,
fromStart, lo, loInclusive,
false, toKey, inclusive);
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey, boolean inclusive) {
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new AscendingSubMapa8093152e673feb7aba1828c43532094(m,
false, fromKey, inclusive,
toEnd, hi, hiInclusive);
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 descendingMap() {
NavigableMapb77a8d9c3c319e50d4b02a976b347910 mv = descendingMapView;
return (mv != null) ? mv :
(descendingMapView =
new DescendingSubMapa8093152e673feb7aba1828c43532094(m,
fromStart, lo, loInclusive,
toEnd, hi, hiInclusive));
}
Iterator245c3adc26563b673f7297c0b3777639 keyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
Spliterator245c3adc26563b673f7297c0b3777639 keySpliterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
Iterator245c3adc26563b673f7297c0b3777639 descendingKeyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
final class AscendingEntrySetView extends EntrySetView {
public Iterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> iterator() {
return new SubMapEntryIterator(absLowest(), absHighFence());
}
}
public Set<Map.Entryb77a8d9c3c319e50d4b02a976b347910> entrySet() {
EntrySetView es = entrySetView;
return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
}
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subLowest() { return absLowest(); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subHighest() { return absHighest(); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subCeiling(K key) { return absCeiling(key); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subHigher(K key) { return absHigher(key); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subFloor(K key) { return absFloor(key); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subLower(K key) { return absLower(key); }
}
/**
* @serial include
*/
static final class DescendingSubMapb77a8d9c3c319e50d4b02a976b347910 extends NavigableSubMapb77a8d9c3c319e50d4b02a976b347910 {
private static final long serialVersionUID = 912986545866120460L;
DescendingSubMap(TreeMapb77a8d9c3c319e50d4b02a976b347910 m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
private final Comparator99be4058f294b5c4a6207ddd3216ce19 reverseComparator =
Collections.reverseOrder(m.comparator);
public Comparator99be4058f294b5c4a6207ddd3216ce19 comparator() {
return reverseComparator;
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 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 DescendingSubMapa8093152e673feb7aba1828c43532094(m,
false, toKey, toInclusive,
false, fromKey, fromInclusive);
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new DescendingSubMapa8093152e673feb7aba1828c43532094(m,
false, toKey, inclusive,
toEnd, hi, hiInclusive);
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey, boolean inclusive) {
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new DescendingSubMapa8093152e673feb7aba1828c43532094(m,
fromStart, lo, loInclusive,
false, fromKey, inclusive);
}
public NavigableMapb77a8d9c3c319e50d4b02a976b347910 descendingMap() {
NavigableMapb77a8d9c3c319e50d4b02a976b347910 mv = descendingMapView;
return (mv != null) ? mv :
(descendingMapView =
new AscendingSubMapa8093152e673feb7aba1828c43532094(m,
fromStart, lo, loInclusive,
toEnd, hi, hiInclusive));
}
Iterator245c3adc26563b673f7297c0b3777639 keyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
Spliterator245c3adc26563b673f7297c0b3777639 keySpliterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
Iterator245c3adc26563b673f7297c0b3777639 descendingKeyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
final class DescendingEntrySetView extends EntrySetView {
public Iterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> iterator() {
return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
}
}
public Set<Map.Entryb77a8d9c3c319e50d4b02a976b347910> entrySet() {
EntrySetView es = entrySetView;
return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
}
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subLowest() { return absHighest(); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subHighest() { return absLowest(); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subCeiling(K key) { return absFloor(key); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subHigher(K key) { return absLower(key); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 subFloor(K key) { return absCeiling(key); }
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 AbstractMapb77a8d9c3c319e50d4b02a976b347910
implements SortedMapb77a8d9c3c319e50d4b02a976b347910, java.io.Serializable {
private static final long serialVersionUID = -6520786458950516097L;
private boolean fromStart = false, toEnd = false;
private K fromKey, toKey;
private Object readResolve() {
return new AscendingSubMapa8093152e673feb7aba1828c43532094(TreeMap.this,
fromStart, fromKey, true,
toEnd, toKey, false);
}
public Set<Map.Entryb77a8d9c3c319e50d4b02a976b347910> entrySet() { throw new InternalError(); }
public K lastKey() { throw new InternalError(); }
public K firstKey() { throw new InternalError(); }
public SortedMapb77a8d9c3c319e50d4b02a976b347910 subMap(K fromKey, K toKey) { throw new InternalError(); }
public SortedMapb77a8d9c3c319e50d4b02a976b347910 headMap(K toKey) { throw new InternalError(); }
public SortedMapb77a8d9c3c319e50d4b02a976b347910 tailMap(K fromKey) { throw new InternalError(); }
public Comparator99be4058f294b5c4a6207ddd3216ce19 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 Entryb77a8d9c3c319e50d4b02a976b347910 implements Map.Entryb77a8d9c3c319e50d4b02a976b347910 {
K key;
V value;
Entryb77a8d9c3c319e50d4b02a976b347910 left;
Entryb77a8d9c3c319e50d4b02a976b347910 right;
Entryb77a8d9c3c319e50d4b02a976b347910 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, Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryc3f2d894ed311a524f031af7191b9ddc e = (Map.Entryc3f2d894ed311a524f031af7191b9ddc)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 Entryb77a8d9c3c319e50d4b02a976b347910 getFirstEntry() {
Entryb77a8d9c3c319e50d4b02a976b347910 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 Entryb77a8d9c3c319e50d4b02a976b347910 getLastEntry() {
Entryb77a8d9c3c319e50d4b02a976b347910 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 b77a8d9c3c319e50d4b02a976b347910 TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 successor(Entryb77a8d9c3c319e50d4b02a976b347910 t) {
if (t == null)
return null;
else if (t.right != null) {
Entryb77a8d9c3c319e50d4b02a976b347910 p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entryb77a8d9c3c319e50d4b02a976b347910 p = t.parent;
Entryb77a8d9c3c319e50d4b02a976b347910 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 b77a8d9c3c319e50d4b02a976b347910 Entryb77a8d9c3c319e50d4b02a976b347910 predecessor(Entryb77a8d9c3c319e50d4b02a976b347910 t) {
if (t == null)
return null;
else if (t.left != null) {
Entryb77a8d9c3c319e50d4b02a976b347910 p = t.left;
while (p.right != null)
p = p.right;
return p;
} else {
Entryb77a8d9c3c319e50d4b02a976b347910 p = t.parent;
Entryb77a8d9c3c319e50d4b02a976b347910 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 b77a8d9c3c319e50d4b02a976b347910 boolean colorOf(Entryb77a8d9c3c319e50d4b02a976b347910 p) {
return (p == null ? BLACK : p.color);
}
private static b77a8d9c3c319e50d4b02a976b347910 Entryb77a8d9c3c319e50d4b02a976b347910 parentOf(Entryb77a8d9c3c319e50d4b02a976b347910 p) {
return (p == null ? null: p.parent);
}
private static b77a8d9c3c319e50d4b02a976b347910 void setColor(Entryb77a8d9c3c319e50d4b02a976b347910 p, boolean c) {
if (p != null)
p.color = c;
}
private static b77a8d9c3c319e50d4b02a976b347910 Entryb77a8d9c3c319e50d4b02a976b347910 leftOf(Entryb77a8d9c3c319e50d4b02a976b347910 p) {
return (p == null) ? null: p.left;
}
private static b77a8d9c3c319e50d4b02a976b347910 Entryb77a8d9c3c319e50d4b02a976b347910 rightOf(Entryb77a8d9c3c319e50d4b02a976b347910 p) {
return (p == null) ? null: p.right;
}
/** From CLR */
private void rotateLeft(Entryb77a8d9c3c319e50d4b02a976b347910 p) {
if (p != null) {
Entryb77a8d9c3c319e50d4b02a976b347910 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(Entryb77a8d9c3c319e50d4b02a976b347910 p) {
if (p != null) {
Entryb77a8d9c3c319e50d4b02a976b347910 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(Entryb77a8d9c3c319e50d4b02a976b347910 x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entryb77a8d9c3c319e50d4b02a976b347910 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 {
Entryb77a8d9c3c319e50d4b02a976b347910 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(Entryb77a8d9c3c319e50d4b02a976b347910 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) {
Entryb77a8d9c3c319e50d4b02a976b347910 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.
Entryb77a8d9c3c319e50d4b02a976b347910 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(Entryb77a8d9c3c319e50d4b02a976b347910 x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entryb77a8d9c3c319e50d4b02a976b347910 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
Entryb77a8d9c3c319e50d4b02a976b347910 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 907fae80ddef53131f3292ee4f81644bsized1c6776b927dc33c5d9114750b586338 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.Entryb77a8d9c3c319e50d4b02a976b347910> i = entrySet().iterator(); i.hasNext(); ) {
Map.Entryb77a8d9c3c319e50d4b02a976b347910 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(SortedSetfe0b02f19cd2974163bae9a314deb435 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, Iterator6b3d0130bba23ae47fe2b8e8cddf0195 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 Entryb77a8d9c3c319e50d4b02a976b347910 buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator6b3d0130bba23ae47fe2b8e8cddf0195 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 a583fd020f434d033c283723c8bbe27d>> 1;
Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryc3f2d894ed311a524f031af7191b9ddc entry = (Map.Entryc3f2d894ed311a524f031af7191b9ddc)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());
}
Entryb77a8d9c3c319e50d4b02a976b347910 middle = new Entrya8093152e673feb7aba1828c43532094(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) {
Entryb77a8d9c3c319e50d4b02a976b347910 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 245c3adc26563b673f7297c0b3777639 Spliterator245c3adc26563b673f7297c0b3777639 keySpliteratorFor(NavigableMap419e368910ac9b50061d48b64ec849c7 m) {
if (m instanceof TreeMap) {
@SuppressWarnings("unchecked") TreeMap8671163a62007bad7516d7b0ad34ccfd t =
(TreeMap8671163a62007bad7516d7b0ad34ccfd) m;
return t.keySpliterator();
}
if (m instanceof DescendingSubMap) {
@SuppressWarnings("unchecked") DescendingSubMap419e368910ac9b50061d48b64ec849c7 dm =
(DescendingSubMap419e368910ac9b50061d48b64ec849c7) m;
TreeMap419e368910ac9b50061d48b64ec849c7 tm = dm.m;
if (dm == tm.descendingMap) {
@SuppressWarnings("unchecked") TreeMap8671163a62007bad7516d7b0ad34ccfd t =
(TreeMap8671163a62007bad7516d7b0ad34ccfd) tm;
return t.descendingKeySpliterator();
}
}
@SuppressWarnings("unchecked") NavigableSubMap419e368910ac9b50061d48b64ec849c7 sm =
(NavigableSubMap419e368910ac9b50061d48b64ec849c7) m;
return sm.keySpliterator();
}
final Spliterator245c3adc26563b673f7297c0b3777639 keySpliterator() {
return new KeySpliteratorb77a8d9c3c319e50d4b02a976b347910(this, null, null, 0, -1, 0);
}
final Spliterator245c3adc26563b673f7297c0b3777639 descendingKeySpliterator() {
return new DescendingKeySpliteratorb77a8d9c3c319e50d4b02a976b347910(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 TreeMapSpliteratorb77a8d9c3c319e50d4b02a976b347910 {
final TreeMapb77a8d9c3c319e50d4b02a976b347910 tree;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 current; // traverser; initially first node in range
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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(TreeMapb77a8d9c3c319e50d4b02a976b347910 tree,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 origin, TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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; TreeMapb77a8d9c3c319e50d4b02a976b347910 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 KeySpliteratorb77a8d9c3c319e50d4b02a976b347910
extends TreeMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliterator245c3adc26563b673f7297c0b3777639 {
KeySpliterator(TreeMapb77a8d9c3c319e50d4b02a976b347910 tree,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 origin, TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence,
int side, int est, int expectedModCount) {
super(tree, origin, fence, side, est, expectedModCount);
}
public KeySpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
if (est < 0)
getEstimate(); // force initialization
int d = side;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 KeySpliteratora8093152e673feb7aba1828c43532094
(tree, e, current = s, -1, est >>>= 1, expectedModCount);
}
return null;
}
public void forEachRemaining(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
if (action == null)
throw new NullPointerException();
if (est < 0)
getEstimate(); // force initialization
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 Comparator99be4058f294b5c4a6207ddd3216ce19 getComparator() {
return tree.comparator;
}
}
static final class DescendingKeySpliteratorb77a8d9c3c319e50d4b02a976b347910
extends TreeMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliterator245c3adc26563b673f7297c0b3777639 {
DescendingKeySpliterator(TreeMapb77a8d9c3c319e50d4b02a976b347910 tree,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 origin, TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence,
int side, int est, int expectedModCount) {
super(tree, origin, fence, side, est, expectedModCount);
}
public DescendingKeySpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
if (est < 0)
getEstimate(); // force initialization
int d = side;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 e = current, f = fence,
s = ((e == null || e == f) ? null : // empty
(d == 0) ? tree.root : // was top
(d a2f2e6646807f4cd13cfddd5eb875d9b 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 DescendingKeySpliteratora8093152e673feb7aba1828c43532094
(tree, e, current = s, -1, est >>>= 1, expectedModCount);
}
return null;
}
public void forEachRemaining(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
if (action == null)
throw new NullPointerException();
if (est < 0)
getEstimate(); // force initialization
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 ValueSpliteratorb77a8d9c3c319e50d4b02a976b347910
extends TreeMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliteratord94943c0b4933ad8cac500132f64757f {
ValueSpliterator(TreeMapb77a8d9c3c319e50d4b02a976b347910 tree,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 origin, TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence,
int side, int est, int expectedModCount) {
super(tree, origin, fence, side, est, expectedModCount);
}
public ValueSpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
if (est < 0)
getEstimate(); // force initialization
int d = side;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 ValueSpliteratora8093152e673feb7aba1828c43532094
(tree, e, current = s, -1, est >>>= 1, expectedModCount);
}
return null;
}
public void forEachRemaining(Consumer4b7c428692c243aad23ae950d093df01 action) {
if (action == null)
throw new NullPointerException();
if (est < 0)
getEstimate(); // force initialization
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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(Consumer4b7c428692c243aad23ae950d093df01 action) {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 EntrySpliteratorb77a8d9c3c319e50d4b02a976b347910
extends TreeMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
EntrySpliterator(TreeMapb77a8d9c3c319e50d4b02a976b347910 tree,
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 origin, TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 fence,
int side, int est, int expectedModCount) {
super(tree, origin, fence, side, est, expectedModCount);
}
public EntrySpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
if (est < 0)
getEstimate(); // force initialization
int d = side;
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 EntrySpliteratora8093152e673feb7aba1828c43532094
(tree, e, current = s, -1, est >>>= 1, expectedModCount);
}
return null;
}
public void forEachRemaining(Consumer<? super Map.Entry81079595401ce1162abe0d5a660013d8> action) {
if (action == null)
throw new NullPointerException();
if (est < 0)
getEstimate(); // force initialization
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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.Entryb77a8d9c3c319e50d4b02a976b347910> action) {
TreeMap.Entryb77a8d9c3c319e50d4b02a976b347910 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 Comparator3b0b8c50db3add957fd22f5a448ffe65> getComparator() {
// Adapt or create a key-based comparator
if (tree.comparator != null) {
return Map.Entry.comparingByKey(tree.comparator);
}
else {
return (Comparator3b0b8c50db3add957fd22f5a448ffe65> & Serializable) (e1, e2) -> {
@SuppressWarnings("unchecked")
Comparable99be4058f294b5c4a6207ddd3216ce19 k1 = (Comparable99be4058f294b5c4a6207ddd3216ce19) e1.getKey();
return k1.compareTo(e2.getKey());
};
}
}
}
}Das obige ist der detaillierte Inhalt vonCodebeispiel für TreeMap in der Java-Sammlung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Stellungnahme：
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel：Detaillierte Einführung in Java-Sammlungen Hashtable (Bild und Text)Nächster Artikel：Detaillierte Einführung in Java-Sammlungen Hashtable (Bild und Text)