--- a/jdk/src/share/classes/java/util/stream/Streams.java Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/src/share/classes/java/util/stream/Streams.java Tue Jun 11 12:13:26 2013 +0200
@@ -25,7 +25,6 @@
package java.util.stream;
import java.util.Comparator;
-import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
@@ -62,39 +61,62 @@
* An {@code int} range spliterator.
*/
static final class RangeIntSpliterator implements Spliterator.OfInt {
+ // Can never be greater that upTo, this avoids overflow if upper bound
+ // is Integer.MAX_VALUE
+ // All elements are traversed if from == upTo & last == 0
private int from;
private final int upTo;
- private final int step;
+ // 1 if the range is closed and the last element has not been traversed
+ // Otherwise, 0 if the range is open, or is a closed range and all
+ // elements have been traversed
+ private int last;
- RangeIntSpliterator(int from, int upTo, int step) {
+ RangeIntSpliterator(int from, int upTo, boolean closed) {
+ this(from, upTo, closed ? 1 : 0);
+ }
+
+ private RangeIntSpliterator(int from, int upTo, int last) {
this.from = from;
this.upTo = upTo;
- this.step = step;
+ this.last = last;
}
@Override
public boolean tryAdvance(IntConsumer consumer) {
- boolean hasNext = from < upTo;
- if (hasNext) {
- consumer.accept(from);
- from += step;
+ final int i = from;
+ if (i < upTo) {
+ from++;
+ consumer.accept(i);
+ return true;
}
- return hasNext;
+ else if (last > 0) {
+ last = 0;
+ consumer.accept(i);
+ return true;
+ }
+ return false;
}
@Override
public void forEachRemaining(IntConsumer consumer) {
- int hUpTo = upTo;
- int hStep = step; // hoist accesses and checks from loop
- for (int i = from; i < hUpTo; i += hStep)
+ int i = from;
+ final int hUpTo = upTo;
+ int hLast = last;
+ from = upTo;
+ last = 0;
+ while (i < hUpTo) {
+ consumer.accept(i++);
+ }
+ if (hLast > 0) {
+ // Last element of closed range
consumer.accept(i);
- from = upTo;
+ }
}
@Override
public long estimateSize() {
- int d = upTo - from;
- return (d / step) + ((d % step == 0) ? 0 : 1);
+ // Ensure ranges of size > Integer.MAX_VALUE report the correct size
+ return ((long) upTo) - from + last;
}
@Override
@@ -111,57 +133,108 @@
@Override
public Spliterator.OfInt trySplit() {
- return estimateSize() <= 1
+ long size = estimateSize();
+ return size <= 1
? null
- : new RangeIntSpliterator(from, from = from + midPoint(), step);
+ // Left split always has a half-open range
+ : new RangeIntSpliterator(from, from = from + splitPoint(size), 0);
}
- private int midPoint() {
- // Size is known to be >= 2
- int bisection = (upTo - from) / 2;
- // If bisection > step then round down to nearest multiple of step
- // otherwise round up to step
- return bisection > step ? bisection - bisection % step : step;
+ /**
+ * The spliterator size below which the spliterator will be split
+ * at the mid-point to produce balanced splits. Above this size the
+ * spliterator will be split at a ratio of
+ * 1:(RIGHT_BALANCED_SPLIT_RATIO - 1)
+ * to produce right-balanced splits.
+ *
+ * <p>Such splitting ensures that for very large ranges that the left
+ * side of the range will more likely be processed at a lower-depth
+ * than a balanced tree at the expense of a higher-depth for the right
+ * side of the range.
+ *
+ * <p>This is optimized for cases such as IntStream.ints() that is
+ * implemented as range of 0 to Integer.MAX_VALUE but is likely to be
+ * augmented with a limit operation that limits the number of elements
+ * to a count lower than this threshold.
+ */
+ private static final int BALANCED_SPLIT_THRESHOLD = 1 << 24;
+
+ /**
+ * The split ratio of the left and right split when the spliterator
+ * size is above BALANCED_SPLIT_THRESHOLD.
+ */
+ private static final int RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;
+
+ private int splitPoint(long size) {
+ int d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;
+ // 2 <= size <= 2^32
+ return (int) (size / d);
}
}
/**
* A {@code long} range spliterator.
+ *
+ * This implementation cannot be used for ranges whose size is greater
+ * than Long.MAX_VALUE
*/
static final class RangeLongSpliterator implements Spliterator.OfLong {
+ // Can never be greater that upTo, this avoids overflow if upper bound
+ // is Long.MAX_VALUE
+ // All elements are traversed if from == upTo & last == 0
private long from;
private final long upTo;
- private final long step;
+ // 1 if the range is closed and the last element has not been traversed
+ // Otherwise, 0 if the range is open, or is a closed range and all
+ // elements have been traversed
+ private int last;
- RangeLongSpliterator(long from, long upTo, long step) {
+ RangeLongSpliterator(long from, long upTo, boolean closed) {
+ this(from, upTo, closed ? 1 : 0);
+ }
+
+ private RangeLongSpliterator(long from, long upTo, int last) {
+ assert upTo - from + last > 0;
this.from = from;
this.upTo = upTo;
- this.step = step;
+ this.last = last;
}
@Override
public boolean tryAdvance(LongConsumer consumer) {
- boolean hasNext = from < upTo;
- if (hasNext) {
- consumer.accept(from);
- from += step;
+ final long i = from;
+ if (i < upTo) {
+ from++;
+ consumer.accept(i);
+ return true;
}
- return hasNext;
+ else if (last > 0) {
+ last = 0;
+ consumer.accept(i);
+ return true;
+ }
+ return false;
}
@Override
public void forEachRemaining(LongConsumer consumer) {
- long hUpTo = upTo;
- long hStep = step; // hoist accesses and checks from loop
- for (long i = from; i < hUpTo; i += hStep)
+ long i = from;
+ final long hUpTo = upTo;
+ int hLast = last;
+ from = upTo;
+ last = 0;
+ while (i < hUpTo) {
+ consumer.accept(i++);
+ }
+ if (hLast > 0) {
+ // Last element of closed range
consumer.accept(i);
- from = upTo;
+ }
}
@Override
public long estimateSize() {
- long d = upTo - from;
- return (d / step) + ((d % step == 0) ? 0 : 1);
+ return upTo - from + last;
}
@Override
@@ -178,17 +251,42 @@
@Override
public Spliterator.OfLong trySplit() {
- return estimateSize() <= 1
+ long size = estimateSize();
+ return size <= 1
? null
- : new RangeLongSpliterator(from, from = from + midPoint(), step);
+ // Left split always has a half-open range
+ : new RangeLongSpliterator(from, from = from + splitPoint(size), 0);
}
- private long midPoint() {
- // Size is known to be >= 2
- long bisection = (upTo - from) / 2;
- // If bisection > step then round down to nearest multiple of step
- // otherwise round up to step
- return bisection > step ? bisection - bisection % step : step;
+ /**
+ * The spliterator size below which the spliterator will be split
+ * at the mid-point to produce balanced splits. Above this size the
+ * spliterator will be split at a ratio of
+ * 1:(RIGHT_BALANCED_SPLIT_RATIO - 1)
+ * to produce right-balanced splits.
+ *
+ * <p>Such splitting ensures that for very large ranges that the left
+ * side of the range will more likely be processed at a lower-depth
+ * than a balanced tree at the expense of a higher-depth for the right
+ * side of the range.
+ *
+ * <p>This is optimized for cases such as LongStream.longs() that is
+ * implemented as range of 0 to Long.MAX_VALUE but is likely to be
+ * augmented with a limit operation that limits the number of elements
+ * to a count lower than this threshold.
+ */
+ private static final long BALANCED_SPLIT_THRESHOLD = 1 << 24;
+
+ /**
+ * The split ratio of the left and right split when the spliterator
+ * size is above BALANCED_SPLIT_THRESHOLD.
+ */
+ private static final long RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;
+
+ private long splitPoint(long size) {
+ long d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;
+ // 2 <= size <= Long.MAX_VALUE
+ return size / d;
}
}