--- a/jdk/src/share/classes/java/util/TreeMap.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/TreeMap.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -25,6 +25,8 @@
package java.util;
+import java.util.function.Consumer;
+
/**
* A Red-Black tree based {@link NavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
@@ -971,6 +973,10 @@
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>> {
@@ -1007,6 +1013,10 @@
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);
+ }
}
/*
@@ -1090,6 +1100,10 @@
public NavigableSet<E> descendingSet() {
return new KeySet<>(m.descendingMap());
}
+
+ public Spliterator<E> spliterator() {
+ return keySpliteratorFor(m);
+ }
}
/**
@@ -1389,6 +1403,8 @@
/** 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();
@@ -1650,19 +1666,6 @@
}
}
- final class SubMapKeyIterator extends SubMapIterator<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();
- }
- }
-
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
@@ -1677,7 +1680,47 @@
}
}
- final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
+ // 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);
@@ -1688,6 +1731,26 @@
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;
+ }
}
}
@@ -1747,6 +1810,10 @@
return new SubMapKeyIterator(absLowest(), absHighFence());
}
+ Spliterator<K> keySpliterator() {
+ return new SubMapKeyIterator(absLowest(), absHighFence());
+ }
+
Iterator<K> descendingKeyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
@@ -1828,6 +1895,10 @@
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
+ Spliterator<K> keySpliterator() {
+ return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
+ }
+
Iterator<K> descendingKeyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
@@ -2444,4 +2515,407 @@
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);
+ }
+ }
+
+ 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<? super Map.Entry<K, V>> getComparator() {
+ return tree.comparator != null ?
+ Comparators.byKey(tree.comparator) : null;
+ }
+ }
}