treemap与map的关系如下图：
treemap介绍：
（1）treemap是一个有序的key-value集合，是通过红黑树来实现的。
（2）treemap是继承于abstractmap，所以他是一个map，是一个key-value集合。
（3）treemap实现了navigable接口，支持一系列的导航方法，treemap是有序集合
（4）实现了cloneable接口，可以被克隆
（5）treemap实现了serializable接口，它支持序列化
（6）treemap基于红黑树数显，映射根据其键的自然排序进行排序
treemap主要的api：
entrya8093152e673feb7aba1828c43532094                ceilingentry(k key) k                          ceilingkey(k key) clear() object                     clone() comparatoradea50645660c00d864f8df96cd78b01      comparator() containskey(object key) navigableseta8093152e673feb7aba1828c43532094            descendingkeyset() navigablemapa8093152e673feb7aba1828c43532094         descendingmap() set           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遍历方式
（1）遍历treemap的键值对：根据entryset()获取treemap的“键值对”集合，对键值对集合通过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）遍历treemap的键：根据keyset()获得“键”集合，通过迭代器去遍历键集合。
string key = integer integ = iterator iter = map.keyset().iterator()(iter.hasnext()) {    key = (string)iter.next()  integ = (integer)map.get(key)}
（3）遍历treemap的值：根据values获得值的集合，通过迭代器去遍历值的集合。
integer value = collection c = map.values()iterator iter= c.iterator()(iter.hasnext())  {     value = (integer)iter.next()}
treemap示例代码：
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));     } }
运行结果：
---- 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]
基于java8的sortedmap接口源代码：
public interface sortedmap<k,v> extends map<k,v> { comparator<? super k> comparator(); sortedmap<k,v> submap(k fromkey, k tokey); sortedmap<k,v> headmap(k tokey); sortedmap<k,v> tailmap(k fromkey); k firstkey(); k lastkey(); set<k> keyset(); collection<v> values(); set<map.entry<k, v>> entryset(); }
基于java8的navigable接口源代码：
public interface navigablemap<k,v> extends sortedmap<k,v> { map.entry<k,v> lowerentry(k key); k lowerkey(k key); map.entry<k,v> floorentry(k key); k floorkey(k key); map.entry<k,v> ceilingentry(k key); k ceilingkey(k key); map.entry<k,v> higherentry(k key); k higherkey(k key); map.entry<k,v> firstentry(); map.entry<k,v> lastentry(); map.entry<k,v> pollfirstentry(); map.entry<k,v> polllastentry(); navigablemap<k,v> descendingmap(); navigableset<k> navigablekeyset(); navigableset<k> descendingkeyset(); navigablemap<k,v> submap(k fromkey, boolean frominclusive, k tokey, boolean toinclusive); navigablemap<k,v> headmap(k tokey, boolean inclusive); navigablemap<k,v> tailmap(k fromkey, boolean inclusive); sortedmap<k,v> submap(k fromkey, k tokey); sortedmap<k,v> headmap(k tokey); sortedmap<k,v> tailmap(k fromkey); }
基于java8的treemap源代码：
public class treemap<k,v>extends abstractmap<k,v> implements navigablemap<k,v>, cloneable, java.io.serializable { private final comparator<? super k> comparator;//比较器 private transient entry<k,v> root;//根节点 private transient int size = 0;//起始个数 private transient int modcount = 0;//tree改变次数 public treemap() { comparator = null; } public treemap(comparator<? super k> comparator) { this.comparator = comparator; } public treemap(map<? extends k, ? extends v> m) { comparator = null; putall(m); } public treemap(sortedmap<k, ? extends v> 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 (entry<k,v> e = getfirstentry(); e != null; e = successor(e)) if (valequals(value, e.value)) return true; return false; } //通过key获得值 public v get(object key) { entry<k,v> p = getentry(key); return (p==null ? null : p.value); } //比较器 public comparator<? super k> 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(map<? extends k, ? extends v> map) { int mapsize = map.size(); if (size==0 && mapsize!=0 && map instanceof sortedmap) { comparator<?> c = ((sortedmap<?,?>)map).comparator(); if (c == comparator || (c != null && c.equals(comparator))) { ++modcount; try { buildfromsorted(mapsize, map.entryset().iterator(), null, null); } catch (java.io.ioexception cannothappen) { } catch (classnotfoundexception cannothappen) { } return; } } super.putall(map); } /** * 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 entry<k,v> 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") comparable<? super k> k = (comparable<? super k>) key; entry<k,v> p = root; while (p != null) { int cmp = k.compareto(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; } /** * 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 entry<k,v> getentryusingcomparator(object key) { @suppresswarnings("unchecked") k k = (k) key; comparator<? super k> cpr = comparator; if (cpr != null) { entry<k,v> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; } /** * 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 entry<k,v> getceilingentry(k key) { entry<k,v> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp < 0) { if (p.left != null) p = p.left; else return p; } else if (cmp > 0) { if (p.right != null) { p = p.right; } else { entry<k,v> parent = p.parent; entry<k,v> ch = p; while (parent != null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } else return p; } return null; } /** * gets the entry corresponding to the specified key; if no such entry * exists, returns the entry for the greatest key less than the specified * key; if no such entry exists, returns {@code null}. */ //获得与key关系最近的entry,下限 final entry<k,v> getfloorentry(k key) { entry<k,v> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp > 0) { if (p.right != null) p = p.right; else return p; } else if (cmp < 0) { if (p.left != null) { p = p.left; } else { entry<k,v> parent = p.parent; entry<k,v> ch = p; while (parent != null && ch == parent.left) { ch = parent; parent = parent.parent; } return parent; } } else return p; } return null; } /** * gets the entry 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 entry<k,v> gethigherentry(k key) { entry<k,v> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp < 0) { if (p.left != null) p = p.left; else return p; } else { if (p.right != null) { p = p.right; } else { entry<k,v> parent = p.parent; entry<k,v> ch = p; while (parent != null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } } return null; } /** * 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 entry<k,v> getlowerentry(k key) { entry<k,v> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp > 0) { if (p.right != null) p = p.right; else return p; } else { if (p.left != null) { p = p.left; } else { entry<k,v> parent = p.parent; entry<k,v> ch = p; while (parent != null && ch == parent.left) { ch = parent; parent = parent.parent; } return parent; } } } return null; } /** * 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) { entry<k,v> t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new entry<>(key, value, null); size = 1; modcount++; return null; } int cmp; entry<k,v> parent; // split comparator and comparable paths comparator<? super k> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setvalue(value); } while (t != null); } else { if (key == null) throw new nullpointerexception(); @suppresswarnings("unchecked") comparable<? super k> k = (comparable<? super k>) key; do { parent = t; cmp = k.compareto(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setvalue(value); } while (t != null); } entry<k,v> e = new entry<>(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) { entry<k,v> 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() { treemap<?,?> clone; try { clone = (treemap<?,?>) 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.entry<k,v> firstentry() { return exportentry(getfirstentry()); } /** * @since 1.6 */ //最后一个entry public map.entry<k,v> lastentry() { return exportentry(getlastentry()); } /** * @since 1.6 */ //弹出第一个entry，并删除 public map.entry<k,v> pollfirstentry() { entry<k,v> p = getfirstentry(); map.entry<k,v> result = exportentry(p); if (p != null) deleteentry(p); return result; } /** * @since 1.6 */ //弹出最后一个entry，并删除 public map.entry<k,v> polllastentry() { entry<k,v> p = getlastentry(); map.entry<k,v> 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.entry<k,v> 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.entry<k,v> 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.entry<k,v> 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.entry<k,v> 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 keyset<k> navigablekeyset; private transient navigablemap<k,v> descendingmap; /** * returns a {@link set} view of the keys contained in this map. * * <p>the set's iterator returns the keys in ascending order. * the set's spliterator is * <em><a href="spliterator.html#binding">late-binding</a></em>, * <em>fail-fast</em>, 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. * * <p>the set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. if the map is modified * while an iteration over the set is in progress (except through * the iterator's own {@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 set<k> keyset() { return navigablekeyset(); } /** * @since 1.6 */ public navigableset<k> navigablekeyset() { keyset<k> nks = navigablekeyset; return (nks != null) ? nks : (navigablekeyset = new keyset<>(this)); } /** * @since 1.6 */ public navigableset<k> descendingkeyset() { return descendingmap().navigablekeyset(); } /** * returns a {@link collection} view of the values contained in this map. * * <p>the collection's iterator returns the values in ascending order * of the corresponding keys. the collection's spliterator is * <em><a href="spliterator.html#binding">late-binding</a></em>, * <em>fail-fast</em>, and additionally reports {@link spliterator#ordered} * with an encounter order that is ascending order of the corresponding * keys. * * <p>the collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. if the map is * modified while an iteration over the collection is in progress * (except through the iterator's own {@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 collection<v> values() { collection<v> vs = values; return (vs != null) ? vs : (values = new values()); } /** * returns a {@link set} view of the mappings contained in this map. * * <p>the set's iterator returns the entries in ascending key order. the * sets's spliterator is * <em><a href="spliterator.html#binding">late-binding</a></em>, * <em>fail-fast</em>, and additionally reports {@link spliterator#sorted} and * {@link spliterator#ordered} with an encounter order that is ascending key * order. * * <p>the set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. if the map is modified * while an iteration over the set is in progress (except through * the iterator's own {@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.entry<k,v>> entryset() { entryset es = entryset; return (es != null) ? es : (entryset = new entryset()); } /** * @since 1.6 */ public navigablemap<k, v> descendingmap() { navigablemap<k, v> km = descendingmap; return (km != null) ? km : (descendingmap = new descendingsubmap<>(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 navigablemap<k,v> submap(k fromkey, boolean frominclusive, k tokey, boolean toinclusive) { return new ascendingsubmap<>(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 navigablemap<k,v> headmap(k tokey, boolean inclusive) { return new ascendingsubmap<>(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 navigablemap<k,v> tailmap(k fromkey, boolean inclusive) { return new ascendingsubmap<>(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 sortedmap<k,v> 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 sortedmap<k,v> 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 sortedmap<k,v> tailmap(k fromkey) { return tailmap(fromkey, true); } @override public boolean replace(k key, v oldvalue, v newvalue) { entry<k,v> 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) { entry<k,v> p = getentry(key); if (p!=null) { v oldvalue = p.value; p.value = value; return oldvalue; } return null; } @override public void foreach(biconsumer<? super k, ? super v> action) { objects.requirenonnull(action); int expectedmodcount = modcount; for (entry<k, v> e = getfirstentry(); e != null; e = successor(e)) { action.accept(e.key, e.value); if (expectedmodcount != modcount) { throw new concurrentmodificationexception(); } } } @override public void replaceall(bifunction<? super k, ? super v, ? extends v> function) { objects.requirenonnull(function); int expectedmodcount = modcount; for (entry<k, v> 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 abstractcollection<v> { public iterator<v> 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 (entry<k,v> 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 spliterator<v> spliterator() { return new valuespliterator<k,v>(treemap.this, null, null, 0, -1, 0); } } class entryset extends abstractset<map.entry<k,v>> { public iterator<map.entry<k,v>> iterator() { return new entryiterator(getfirstentry()); } public boolean contains(object o) { if (!(o instanceof map.entry)) return false; map.entry<?,?> entry = (map.entry<?,?>) o; object value = entry.getvalue(); entry<k,v> p = getentry(entry.getkey()); return p != null && valequals(p.getvalue(), value); } public boolean remove(object o) { if (!(o instanceof map.entry)) return false; map.entry<?,?> entry = (map.entry<?,?>) o; object value = entry.getvalue(); entry<k,v> 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.entry<k,v>> spliterator() { return new entryspliterator<k,v>(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. */ iterator<k> keyiterator() { return new keyiterator(getfirstentry()); } iterator<k> descendingkeyiterator() { return new descendingkeyiterator(getlastentry()); } static final class keyset<e> extends abstractset<e> implements navigableset<e> { private final navigablemap<e, ?> m; keyset(navigablemap<e,?> map) { m = map; } public iterator<e> iterator() { if (m instanceof treemap) return ((treemap<e,?>)m).keyiterator(); else return ((treemap.navigablesubmap<e,?>)m).keyiterator(); } public iterator<e> descendingiterator() { if (m instanceof treemap) return ((treemap<e,?>)m).descendingkeyiterator(); else return ((treemap.navigablesubmap<e,?>)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 comparator<? super e> comparator() { return m.comparator(); } public e pollfirst() { map.entry<e,?> e = m.pollfirstentry(); return (e == null) ? null : e.getkey(); } public e polllast() { map.entry<e,?> e = m.polllastentry(); return (e == null) ? null : e.getkey(); } public boolean remove(object o) { int oldsize = size(); m.remove(o); return size() != oldsize; } public navigableset<e> subset(e fromelement, boolean frominclusive, e toelement, boolean toinclusive) { return new keyset<>(m.submap(fromelement, frominclusive, toelement, toinclusive)); } public navigableset<e> headset(e toelement, boolean inclusive) { return new keyset<>(m.headmap(toelement, inclusive)); } public navigableset<e> tailset(e fromelement, boolean inclusive) { return new keyset<>(m.tailmap(fromelement, inclusive)); } public sortedset<e> subset(e fromelement, e toelement) { return subset(fromelement, true, toelement, false); } public sortedset<e> headset(e toelement) { return headset(toelement, false); } public sortedset<e> tailset(e fromelement) { return tailset(fromelement, true); } public navigableset<e> descendingset() { return new keyset<>(m.descendingmap()); } public spliterator<e> spliterator() { return keyspliteratorfor(m); } } /** * base class for treemap iterators */ abstract class privateentryiterator<t> implements iterator<t> { entry<k,v> next; entry<k,v> lastreturned; int expectedmodcount; privateentryiterator(entry<k,v> first) { expectedmodcount = modcount; lastreturned = null; next = first; } public final boolean hasnext() { return next != null; } final entry<k,v> nextentry() { entry<k,v> e = next; if (e == null) throw new nosuchelementexception(); if (modcount != expectedmodcount) throw new concurrentmodificationexception(); next = successor(e); lastreturned = e; return e; } final entry<k,v> preventry() { entry<k,v> 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.entry<k,v>> { entryiterator(entry<k,v> first) { super(first); } public map.entry<k,v> next() { return nextentry(); } } final class valueiterator extends privateentryiterator<v> { valueiterator(entry<k,v> first) { super(first); } public v next() { return nextentry().value; } } final class keyiterator extends privateentryiterator<k> { keyiterator(entry<k,v> first) { super(first); } public k next() { return nextentry().key; } } final class descendingkeyiterator extends privateentryiterator<k> { descendingkeyiterator(entry<k,v> 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 ? ((comparable<? super k>)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 <k,v> map.entry<k,v> exportentry(treemap.entry<k,v> e) { return (e == null) ? null : new abstractmap.simpleimmutableentry<>(e); } /** * return key for entry, or null if null */ static <k,v> k keyornull(treemap.entry<k,v> e) { return (e == null) ? null : e.key; } /** * returns the key corresponding to the specified entry. * @throws nosuchelementexception if the entry is null */ static <k> k key(entry<k,?> 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 navigablesubmap<k,v> extends abstractmap<k,v> implements navigablemap<k,v>, java.io.serializable { private static final long serialversionuid = -2102997345730753016l; /** * the backing map. */ final treemap<k,v> 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(treemap<k,v> 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 < 0 || (c == 0 && !loinclusive)) return true; } return false; } final boolean toohigh(object key) { if (!toend) { int c = m.compare(key, hi); if (c > 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.entry<k,v> abslowest() { treemap.entry<k,v> e = (fromstart ? m.getfirstentry() : (loinclusive ? m.getceilingentry(lo) : m.gethigherentry(lo))); return (e == null || toohigh(e.key)) ? null : e; } final treemap.entry<k,v> abshighest() { treemap.entry<k,v> e = (toend ? m.getlastentry() : (hiinclusive ? m.getfloorentry(hi) : m.getlowerentry(hi))); return (e == null || toolow(e.key)) ? null : e; } final treemap.entry<k,v> absceiling(k key) { if (toolow(key)) return abslowest(); treemap.entry<k,v> e = m.getceilingentry(key); return (e == null || toohigh(e.key)) ? null : e; } final treemap.entry<k,v> abshigher(k key) { if (toolow(key)) return abslowest(); treemap.entry<k,v> e = m.gethigherentry(key); return (e == null || toohigh(e.key)) ? null : e; } final treemap.entry<k,v> absfloor(k key) { if (toohigh(key)) return abshighest(); treemap.entry<k,v> e = m.getfloorentry(key); return (e == null || toolow(e.key)) ? null : e; } final treemap.entry<k,v> abslower(k key) { if (toohigh(key)) return abshighest(); treemap.entry<k,v> e = m.getlowerentry(key); return (e == null || toolow(e.key)) ? null : e; } /** returns the absolute high fence for ascending traversal */ final treemap.entry<k,v> abshighfence() { return (toend ? null : (hiinclusive ? m.gethigherentry(hi) : m.getceilingentry(hi))); } /** return the absolute low fence for descending traversal */ final treemap.entry<k,v> 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.entry<k,v> sublowest(); abstract treemap.entry<k,v> subhighest(); abstract treemap.entry<k,v> subceiling(k key); abstract treemap.entry<k,v> subhigher(k key); abstract treemap.entry<k,v> subfloor(k key); abstract treemap.entry<k,v> sublower(k key); /** returns ascending iterator from the perspective of this submap */ abstract iterator<k> keyiterator(); abstract spliterator<k> keyspliterator(); /** returns descending iterator from the perspective of this submap */ abstract iterator<k> 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.entry<k,v> ceilingentry(k key) { return exportentry(subceiling(key)); } public final k ceilingkey(k key) { return keyornull(subceiling(key)); } public final map.entry<k,v> higherentry(k key) { return exportentry(subhigher(key)); } public final k higherkey(k key) { return keyornull(subhigher(key)); } public final map.entry<k,v> floorentry(k key) { return exportentry(subfloor(key)); } public final k floorkey(k key) { return keyornull(subfloor(key)); } public final map.entry<k,v> 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.entry<k,v> firstentry() { return exportentry(sublowest()); } public final map.entry<k,v> lastentry() { return exportentry(subhighest()); } public final map.entry<k,v> pollfirstentry() { treemap.entry<k,v> e = sublowest(); map.entry<k,v> result = exportentry(e); if (e != null) m.deleteentry(e); return result; } public final map.entry<k,v> polllastentry() { treemap.entry<k,v> e = subhighest(); map.entry<k,v> result = exportentry(e); if (e != null) m.deleteentry(e); return result; } // views transient navigablemap<k,v> descendingmapview; transient entrysetview entrysetview; transient keyset<k> navigablekeysetview; public final navigableset<k> navigablekeyset() { keyset<k> nksv = navigablekeysetview; return (nksv != null) ? nksv : (navigablekeysetview = new treemap.keyset<>(this)); } public final set<k> keyset() { return navigablekeyset(); } public navigableset<k> descendingkeyset() { return descendingmap().navigablekeyset(); } public final sortedmap<k,v> submap(k fromkey, k tokey) { return submap(fromkey, true, tokey, false); } public final sortedmap<k,v> headmap(k tokey) { return headmap(tokey, false); } public final sortedmap<k,v> tailmap(k fromkey) { return tailmap(fromkey, true); } // view classes abstract class entrysetview extends abstractset<map.entry<k,v>> { 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; iterator<?> i = iterator(); while (i.hasnext()) { size++; i.next(); } } return size; } public boolean isempty() { treemap.entry<k,v> n = abslowest(); return n == null || toohigh(n.key); } public boolean contains(object o) { if (!(o instanceof map.entry)) return false; map.entry<?,?> entry = (map.entry<?,?>) o; object key = entry.getkey(); if (!inrange(key)) return false; treemap.entry<?,?> 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.entry<?,?> entry = (map.entry<?,?>) o; object key = entry.getkey(); if (!inrange(key)) return false; treemap.entry<k,v> node = m.getentry(key); if (node!=null && valequals(node.getvalue(), entry.getvalue())) { m.deleteentry(node); return true; } return false; } } /** * iterators for submaps */ abstract class submapiterator<t> implements iterator<t> { treemap.entry<k,v> lastreturned; treemap.entry<k,v> next; final object fencekey; int expectedmodcount; submapiterator(treemap.entry<k,v> first, treemap.entry<k,v> 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.entry<k,v> nextentry() { treemap.entry<k,v> 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.entry<k,v> preventry() { treemap.entry<k,v> 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.entry<k,v>> { submapentryiterator(treemap.entry<k,v> first, treemap.entry<k,v> fence) { super(first, fence); } public map.entry<k,v> next() { return nextentry(); } public void remove() { removeascending(); } } final class descendingsubmapentryiterator extends submapiterator<map.entry<k,v>> { descendingsubmapentryiterator(treemap.entry<k,v> last, treemap.entry<k,v> fence) { super(last, fence); } public map.entry<k,v> next() { return preventry(); } public void remove() { removedescending(); } } // implement minimal spliterator as keyspliterator backup final class submapkeyiterator extends submapiterator<k> implements spliterator<k> { submapkeyiterator(treemap.entry<k,v> first, treemap.entry<k,v> fence) { super(first, fence); } public k next() { return nextentry().key; } public void remove() { removeascending(); } public spliterator<k> trysplit() { return null; } public void foreachremaining(consumer<? super k> action) { while (hasnext()) action.accept(next()); } public boolean tryadvance(consumer<? super k> 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 comparator<? super k> getcomparator() { return navigablesubmap.this.comparator(); } } final class descendingsubmapkeyiterator extends submapiterator<k> implements spliterator<k> { descendingsubmapkeyiterator(treemap.entry<k,v> last, treemap.entry<k,v> fence) { super(last, fence); } public k next() { return preventry().key; } public void remove() { removedescending(); } public spliterator<k> trysplit() { return null; } public void foreachremaining(consumer<? super k> action) { while (hasnext()) action.accept(next()); } public boolean tryadvance(consumer<? super k> 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 ascendingsubmap<k,v> extends navigablesubmap<k,v> { private static final long serialversionuid = 912986545866124060l; ascendingsubmap(treemap<k,v> m, boolean fromstart, k lo, boolean loinclusive, boolean toend, k hi, boolean hiinclusive) { super(m, fromstart, lo, loinclusive, toend, hi, hiinclusive); } public comparator<? super k> comparator() { return m.comparator(); } public navigablemap<k,v> 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 ascendingsubmap<>(m, false, fromkey, frominclusive, false, tokey, toinclusive); } public navigablemap<k,v> headmap(k tokey, boolean inclusive) { if (!inrange(tokey, inclusive)) throw new illegalargumentexception("tokey out of range"); return new ascendingsubmap<>(m, fromstart, lo, loinclusive, false, tokey, inclusive); } public navigablemap<k,v> tailmap(k fromkey, boolean inclusive) { if (!inrange(fromkey, inclusive)) throw new illegalargumentexception("fromkey out of range"); return new ascendingsubmap<>(m, false, fromkey, inclusive, toend, hi, hiinclusive); } public navigablemap<k,v> descendingmap() { navigablemap<k,v> mv = descendingmapview; return (mv != null) ? mv : (descendingmapview = new descendingsubmap<>(m, fromstart, lo, loinclusive, toend, hi, hiinclusive)); } iterator<k> keyiterator() { return new submapkeyiterator(abslowest(), abshighfence()); } spliterator<k> keyspliterator() { return new submapkeyiterator(abslowest(), abshighfence()); } iterator<k> descendingkeyiterator() { return new descendingsubmapkeyiterator(abshighest(), abslowfence()); } final class ascendingentrysetview extends entrysetview { public iterator<map.entry<k,v>> iterator() { return new submapentryiterator(abslowest(), abshighfence()); } } public set<map.entry<k,v>> entryset() { entrysetview es = entrysetview; return (es != null) ? es : (entrysetview = new ascendingentrysetview()); } treemap.entry<k,v> sublowest() { return abslowest(); } treemap.entry<k,v> subhighest() { return abshighest(); } treemap.entry<k,v> subceiling(k key) { return absceiling(key); } treemap.entry<k,v> subhigher(k key) { return abshigher(key); } treemap.entry<k,v> subfloor(k key) { return absfloor(key); } treemap.entry<k,v> sublower(k key) { return abslower(key); } } /** * @serial include */ static final class descendingsubmap<k,v> extends navigablesubmap<k,v> { private static final long serialversionuid = 912986545866120460l; descendingsubmap(treemap<k,v> m, boolean fromstart, k lo, boolean loinclusive, boolean toend, k hi, boolean hiinclusive) { super(m, fromstart, lo, loinclusive, toend, hi, hiinclusive); } private final comparator<? super k> reversecomparator = collections.reverseorder(m.comparator); public comparator<? super k> comparator() { return reversecomparator; } public navigablemap<k,v> 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 descendingsubmap<>(m, false, tokey, toinclusive, false, fromkey, frominclusive); } public navigablemap<k,v> headmap(k tokey, boolean inclusive) { if (!inrange(tokey, inclusive)) throw new illegalargumentexception("tokey out of range"); return new descendingsubmap<>(m, false, tokey, inclusive, toend, hi, hiinclusive); } public navigablemap<k,v> tailmap(k fromkey, boolean inclusive) { if (!inrange(fromkey, inclusive)) throw new illegalargumentexception("fromkey out of range"); return new descendingsubmap<>(m, fromstart, lo, loinclusive, false, fromkey, inclusive); } public navigablemap<k,v> descendingmap() { navigablemap<k,v> mv = descendingmapview; return (mv != null) ? mv : (descendingmapview = new ascendingsubmap<>(m, fromstart, lo, loinclusive, toend, hi, hiinclusive)); } iterator<k> keyiterator() { return new descendingsubmapkeyiterator(abshighest(), abslowfence()); } spliterator<k> keyspliterator() { return new descendingsubmapkeyiterator(abshighest(), abslowfence()); } iterator<k> descendingkeyiterator() { return new submapkeyiterator(abslowest(), abshighfence()); } final class descendingentrysetview extends entrysetview { public iterator<map.entry<k,v>> iterator() { return new descendingsubmapentryiterator(abshighest(), abslowfence()); } } public set<map.entry<k,v>> entryset() { entrysetview es = entrysetview; return (es != null) ? es : (entrysetview = new descendingentrysetview()); } treemap.entry<k,v> sublowest() { return abshighest(); } treemap.entry<k,v> subhighest() { return abslowest(); } treemap.entry<k,v> subceiling(k key) { return absfloor(key); } treemap.entry<k,v> subhigher(k key) { return abslower(key); } treemap.entry<k,v> subfloor(k key) { return absceiling(key); } treemap.entry<k,v> 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 abstractmap<k,v> implements sortedmap<k,v>, java.io.serializable { private static final long serialversionuid = -6520786458950516097l; private boolean fromstart = false, toend = false; private k fromkey, tokey; private object readresolve() { return new ascendingsubmap<>(treemap.this, fromstart, fromkey, true, toend, tokey, false); } public set<map.entry<k,v>> entryset() { throw new internalerror(); } public k lastkey() { throw new internalerror(); } public k firstkey() { throw new internalerror(); } public sortedmap<k,v> submap(k fromkey, k tokey) { throw new internalerror(); } public sortedmap<k,v> headmap(k tokey) { throw new internalerror(); } public sortedmap<k,v> tailmap(k fromkey) { throw new internalerror(); } public comparator<? super k> 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 entry<k,v> implements map.entry<k,v> { k key; v value; entry<k,v> left; entry<k,v> right; entry<k,v> 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, entry<k,v> 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.entry<?,?> e = (map.entry<?,?>)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 entry<k,v> getfirstentry() { entry<k,v> 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 entry<k,v> getlastentry() { entry<k,v> 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 <k,v> treemap.entry<k,v> successor(entry<k,v> t) { if (t == null) return null; else if (t.right != null) { entry<k,v> p = t.right; while (p.left != null) p = p.left; return p; } else { entry<k,v> p = t.parent; entry<k,v> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } /** * returns the predecessor of the specified entry, or null if no such. */ static <k,v> entry<k,v> predecessor(entry<k,v> t) { if (t == null) return null; else if (t.left != null) { entry<k,v> p = t.left; while (p.right != null) p = p.right; return p; } else { entry<k,v> p = t.parent; entry<k,v> ch = t; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } } /** * 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 <k,v> boolean colorof(entry<k,v> p) { return (p == null ? black : p.color); } private static <k,v> entry<k,v> parentof(entry<k,v> p) { return (p == null ? null: p.parent); } private static <k,v> void setcolor(entry<k,v> p, boolean c) { if (p != null) p.color = c; } private static <k,v> entry<k,v> leftof(entry<k,v> p) { return (p == null) ? null: p.left; } private static <k,v> entry<k,v> rightof(entry<k,v> p) { return (p == null) ? null: p.right; } /** from clr */ private void rotateleft(entry<k,v> p) { if (p != null) { entry<k,v> 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(entry<k,v> p) { if (p != null) { entry<k,v> 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(entry<k,v> x) { x.color = red; while (x != null && x != root && x.parent.color == red) { if (parentof(x) == leftof(parentof(parentof(x)))) { entry<k,v> 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 { entry<k,v> 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(entry<k,v> 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) { entry<k,v> 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. entry<k,v> 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(entry<k,v> x) { while (x != root && colorof(x) == black) { if (x == leftof(parentof(x))) { entry<k,v> 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 entry<k,v> 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 <em>size</em> 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.entry<k,v>> i = entryset().iterator(); i.hasnext(); ) { map.entry<k,v> 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(sortedset<? extends k> 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, iterator<?> 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 entry<k,v> buildfromsorted(int level, int lo, int hi, int redlevel, iterator<?> 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 < lo) return null; int mid = (lo + hi) >>> 1; entry<k,v> 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.entry<?,?> entry = (map.entry<?,?>)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()); } entry<k,v> middle = new entry<>(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) { entry<k,v> 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 <k> spliterator<k> keyspliteratorfor(navigablemap<k,?> m) { if (m instanceof treemap) { @suppresswarnings("unchecked") treemap<k,object> t = (treemap<k,object>) m; return t.keyspliterator(); } if (m instanceof descendingsubmap) { @suppresswarnings("unchecked") descendingsubmap<k,?> dm = (descendingsubmap<k,?>) m; treemap<k,?> tm = dm.m; if (dm == tm.descendingmap) { @suppresswarnings("unchecked") treemap<k,object> t = (treemap<k,object>) tm; return t.descendingkeyspliterator(); } } @suppresswarnings("unchecked") navigablesubmap<k,?> sm = (navigablesubmap<k,?>) m; return sm.keyspliterator(); } final spliterator<k> keyspliterator() { return new keyspliterator<k,v>(this, null, null, 0, -1, 0); } final spliterator<k> descendingkeyspliterator() { return new descendingkeyspliterator<k,v>(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 treemapspliterator<k,v> { final treemap<k,v> tree; treemap.entry<k,v> current; // traverser; initially first node in range treemap.entry<k,v> 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(treemap<k,v> tree, treemap.entry<k,v> origin, treemap.entry<k,v> 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; treemap<k,v> 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 keyspliterator<k,v> extends treemapspliterator<k,v> implements spliterator<k> { keyspliterator(treemap<k,v> tree, treemap.entry<k,v> origin, treemap.entry<k,v> fence, int side, int est, int expectedmodcount) { super(tree, origin, fence, side, est, expectedmodcount); } public keyspliterator<k,v> trysplit() { if (est < 0) getestimate(); // force initialization int d = side; treemap.entry<k,v> 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 keyspliterator<> (tree, e, current = s, -1, est >>>= 1, expectedmodcount); } return null; } public void foreachremaining(consumer<? super k> action) { if (action == null) throw new nullpointerexception(); if (est < 0) getestimate(); // force initialization treemap.entry<k,v> 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(consumer<? super k> action) { treemap.entry<k,v> 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 comparator<? super k> getcomparator() { return tree.comparator; } } static final class descendingkeyspliterator<k,v> extends treemapspliterator<k,v> implements spliterator<k> { descendingkeyspliterator(treemap<k,v> tree, treemap.entry<k,v> origin, treemap.entry<k,v> fence, int side, int est, int expectedmodcount) { super(tree, origin, fence, side, est, expectedmodcount); } public descendingkeyspliterator<k,v> trysplit() { if (est < 0) getestimate(); // force initialization int d = side; treemap.entry<k,v> e = current, f = fence, s = ((e == null || e == f) ? null : // empty (d == 0) ? tree.root : // was top (d < 0) ? e.left : // was left (d > 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 descendingkeyspliterator<> (tree, e, current = s, -1, est >>>= 1, expectedmodcount); } return null; } public void foreachremaining(consumer<? super k> action) { if (action == null) throw new nullpointerexception(); if (est < 0) getestimate(); // force initialization treemap.entry<k,v> 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(consumer<? super k> action) { treemap.entry<k,v> 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 valuespliterator<k,v> extends treemapspliterator<k,v> implements spliterator<v> { valuespliterator(treemap<k,v> tree, treemap.entry<k,v> origin, treemap.entry<k,v> fence, int side, int est, int expectedmodcount) { super(tree, origin, fence, side, est, expectedmodcount); } public valuespliterator<k,v> trysplit() { if (est < 0) getestimate(); // force initialization int d = side; treemap.entry<k,v> 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 valuespliterator<> (tree, e, current = s, -1, est >>>= 1, expectedmodcount); } return null; } public void foreachremaining(consumer<? super v> action) { if (action == null) throw new nullpointerexception(); if (est < 0) getestimate(); // force initialization treemap.entry<k,v> 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(consumer<? super v> action) { treemap.entry<k,v> 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 entryspliterator<k,v> extends treemapspliterator<k,v> implements spliterator<map.entry<k,v>> { entryspliterator(treemap<k,v> tree, treemap.entry<k,v> origin, treemap.entry<k,v> fence, int side, int est, int expectedmodcount) { super(tree, origin, fence, side, est, expectedmodcount); } public entryspliterator<k,v> trysplit() { if (est < 0) getestimate(); // force initialization int d = side; treemap.entry<k,v> 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 entryspliterator<> (tree, e, current = s, -1, est >>>= 1, expectedmodcount); } return null; } public void foreachremaining(consumer<? super map.entry<k, v>> action) { if (action == null) throw new nullpointerexception(); if (est < 0) getestimate(); // force initialization treemap.entry<k,v> 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.entry<k,v>> action) { treemap.entry<k,v> 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 comparator<map.entry<k, v>> getcomparator() { // adapt or create a key-based comparator if (tree.comparator != null) { return map.entry.comparingbykey(tree.comparator); } else { return (comparator<map.entry<k, v>> & serializable) (e1, e2) -> { @suppresswarnings("unchecked") comparable<? super k> k1 = (comparable<? super k>) e1.getkey(); return k1.compareto(e2.getkey()); }; } } } }
以上就是java集合之treemap的代码实例的详细内容。