8015895: Int/LongStream.range/rangeClosed
8012986: Right-bias range spliterators for large ranges
Reviewed-by: mduigou
--- a/jdk/src/share/classes/java/util/stream/IntStream.java Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/src/share/classes/java/util/stream/IntStream.java Tue Jun 11 12:13:26 2013 +0200
@@ -759,12 +759,13 @@
/**
* Returns a sequential {@code IntStream} from {@code startInclusive}
* (inclusive) to {@code endExclusive} (exclusive) by an incremental step of
- * 1.
+ * {@code 1}.
*
- * @implSpec
- * The implementation behaves as if:
+ * @apiNote
+ * <p>An equivalent sequence of increasing values can be produced
+ * sequentially using a {@code for} loop as follows:
* <pre>{@code
- * intRange(startInclusive, endExclusive, 1);
+ * for (int i = startInclusive; i < endExclusive ; i++) { ... }
* }</pre>
*
* @param startInclusive the (inclusive) initial value
@@ -773,36 +774,37 @@
* elements
*/
public static IntStream range(int startInclusive, int endExclusive) {
- return range(startInclusive, endExclusive, 1);
+ if (startInclusive >= endExclusive) {
+ return empty();
+ } else {
+ return StreamSupport.intStream(
+ new Streams.RangeIntSpliterator(startInclusive, endExclusive, false));
+ }
}
/**
* Returns a sequential {@code IntStream} from {@code startInclusive}
- * (inclusive) to {@code endExclusive} (exclusive) by a positive {@code
- * step}. If {@code startInclusive} is greater than or equal to {@code
- * endExclusive}, an empty stream is returned.
+ * (inclusive) to {@code endInclusive} (inclusive) by an incremental step of
+ * {@code 1}.
*
+ * @apiNote
* <p>An equivalent sequence of increasing values can be produced
* sequentially using a {@code for} loop as follows:
* <pre>{@code
- * for (int i = startInclusive; i < endExclusive ; i += step) { ... }
+ * for (int i = startInclusive; i <= endInclusive ; i++) { ... }
* }</pre>
*
* @param startInclusive the (inclusive) initial value
- * @param endExclusive the exclusive upper bound
- * @param step the positive difference between consecutive values
+ * @param endInclusive the inclusive upper bound
* @return a sequential {@code IntStream} for the range of {@code int}
* elements
- * @throws IllegalArgumentException if {@code step} is less than or equal to
- * 0
*/
- public static IntStream range(int startInclusive, int endExclusive, int step) {
- if (step <= 0) {
- throw new IllegalArgumentException(String.format("Illegal step: %d", step));
- } else if (startInclusive >= endExclusive) {
+ public static IntStream rangeClosed(int startInclusive, int endInclusive) {
+ if (startInclusive > endInclusive) {
return empty();
} else {
- return StreamSupport.intStream(new Streams.RangeIntSpliterator(startInclusive, endExclusive, step));
+ return StreamSupport.intStream(
+ new Streams.RangeIntSpliterator(startInclusive, endInclusive, true));
}
}
}
--- a/jdk/src/share/classes/java/util/stream/LongStream.java Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/src/share/classes/java/util/stream/LongStream.java Tue Jun 11 12:13:26 2013 +0200
@@ -750,12 +750,13 @@
/**
* Returns a sequential {@code LongStream} from {@code startInclusive}
* (inclusive) to {@code endExclusive} (exclusive) by an incremental step of
- * 1.
+ * {@code 1}.
*
- * @implSpec
- * The implementation behaves as if:
+ * @apiNote
+ * <p>An equivalent sequence of increasing values can be produced
+ * sequentially using a {@code for} loop as follows:
* <pre>{@code
- * longRange(startInclusive, endExclusive, 1);
+ * for (long i = startInclusive; i < endExclusive ; i++) { ... }
* }</pre>
*
* @param startInclusive the (inclusive) initial value
@@ -764,36 +765,56 @@
* elements
*/
public static LongStream range(long startInclusive, final long endExclusive) {
- return range(startInclusive, endExclusive, 1);
+ if (startInclusive >= endExclusive) {
+ return empty();
+ } else if (endExclusive - startInclusive < 0) {
+ // Size of range > Long.MAX_VALUE
+ // Split the range in two and concatenate
+ // Note: if the range is [Long.MIN_VALUE, Long.MAX_VALUE) then
+ // the lower range, [Long.MIN_VALUE, 0) will be further split in two
+// long m = startInclusive + Long.divideUnsigned(endExclusive - startInclusive, 2) + 1;
+// return Streams.concat(range(startInclusive, m), range(m, endExclusive));
+ // This is temporary until Streams.concat is supported
+ throw new UnsupportedOperationException();
+ } else {
+ return StreamSupport.longStream(
+ new Streams.RangeLongSpliterator(startInclusive, endExclusive, false));
+ }
}
/**
* Returns a sequential {@code LongStream} from {@code startInclusive}
- * (inclusive) to {@code endExclusive} (exclusive) by {@code step}. If
- * {@code startInclusive} is greater than or equal to {@code
- * endExclusive}, an empty stream is returned.
+ * (inclusive) to {@code endInclusive} (inclusive) by an incremental step of
+ * {@code 1}.
*
+ * @apiNote
* <p>An equivalent sequence of increasing values can be produced
* sequentially using a {@code for} loop as follows:
* <pre>{@code
- * for (long i = startInclusive; i < endExclusive ; i += step) { ... }
+ * for (long i = startInclusive; i <= endInclusive ; i++) { ... }
* }</pre>
*
* @param startInclusive the (inclusive) initial value
- * @param endExclusive the exclusive upper bound
- * @param step the difference between consecutive values
+ * @param endInclusive the inclusive upper bound
* @return a sequential {@code LongStream} for the range of {@code long}
* elements
- * @throws IllegalArgumentException if {@code step} is less than or equal to
- * 0
*/
- public static LongStream range(long startInclusive, final long endExclusive, final long step) {
- if (step <= 0) {
- throw new IllegalArgumentException(String.format("Illegal step: %d", step));
- } else if (startInclusive >= endExclusive) {
+ public static LongStream rangeClosed(long startInclusive, final long endInclusive) {
+ if (startInclusive > endInclusive) {
return empty();
+ } else if (endInclusive - startInclusive + 1 <= 0) {
+ // Size of range > Long.MAX_VALUE
+ // Split the range in two and concatenate
+ // Note: if the range is [Long.MIN_VALUE, Long.MAX_VALUE] then
+ // the lower range, [Long.MIN_VALUE, 0), and upper range,
+ // [0, Long.MAX_VALUE], will both be further split in two
+// long m = startInclusive + Long.divideUnsigned(endInclusive - startInclusive, 2) + 1;
+// return Streams.concat(range(startInclusive, m), rangeClosed(m, endInclusive));
+ // This is temporary until Streams.concat is supported
+ throw new UnsupportedOperationException();
} else {
- return StreamSupport.longStream(new Streams.RangeLongSpliterator(startInclusive, endExclusive, step));
+ return StreamSupport.longStream(
+ new Streams.RangeLongSpliterator(startInclusive, endInclusive, true));
}
}
}
--- 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;
}
}
--- a/jdk/test/java/util/stream/bootlib/java/util/stream/IntStreamTestDataProvider.java Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/test/java/util/stream/bootlib/java/util/stream/IntStreamTestDataProvider.java Tue Jun 11 12:13:26 2013 +0200
@@ -95,12 +95,8 @@
list.add(streamDataDescr("IntStream.intRange(0,l): " + ints.length,
() -> IntStream.range(0, ints.length)));
- list.add(streamDataDescr("IntStream.intRange(0,l,2): " + ints.length,
- () -> IntStream.range(0, ints.length, 2)));
- list.add(streamDataDescr("IntStream.intRange(0,l,3): " + ints.length,
- () -> IntStream.range(0, ints.length, 3)));
- list.add(streamDataDescr("IntStream.intRange(0,l,7): " + ints.length,
- () -> IntStream.range(0, ints.length, 7)));
+ list.add(streamDataDescr("IntStream.rangeClosed(0,l): " + ints.length,
+ () -> IntStream.rangeClosed(0, ints.length)));
}
testData = list.toArray(new Object[0][]);
}
@@ -131,12 +127,8 @@
spliterators.add(splitDescr("IntStream.intRange(0,l):" + name,
() -> IntStream.range(0, ints.length).spliterator()));
- spliterators.add(splitDescr("IntStream.intRange(0,l,2):" + name,
- () -> IntStream.range(0, ints.length, 2).spliterator()));
- spliterators.add(splitDescr("IntStream.intRange(0,l,3):" + name,
- () -> IntStream.range(0, ints.length, 3).spliterator()));
- spliterators.add(splitDescr("IntStream.intRange(0,l,7):" + name,
- () -> IntStream.range(0, ints.length, 7).spliterator()));
+ spliterators.add(splitDescr("IntStream.intRangeClosed(0,l):" + name,
+ () -> IntStream.rangeClosed(0, ints.length).spliterator()));
// Need more!
}
--- a/jdk/test/java/util/stream/bootlib/java/util/stream/LongStreamTestDataProvider.java Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/test/java/util/stream/bootlib/java/util/stream/LongStreamTestDataProvider.java Tue Jun 11 12:13:26 2013 +0200
@@ -95,12 +95,8 @@
list.add(streamDataDescr("LongStream.longRange(0,l): " + longs.length,
() -> LongStream.range(0, longs.length)));
- list.add(streamDataDescr("LongStream.longRange(0,l,2): " + longs.length,
- () -> LongStream.range(0, longs.length, 2)));
- list.add(streamDataDescr("LongStream.longRange(0,l,3): " + longs.length,
- () -> LongStream.range(0, longs.length, 3)));
- list.add(streamDataDescr("LongStream.longRange(0,l,7): " + longs.length,
- () -> LongStream.range(0, longs.length, 7)));
+ list.add(streamDataDescr("LongStream.longRangeClosed(0,l): " + longs.length,
+ () -> LongStream.rangeClosed(0, longs.length)));
}
testData = list.toArray(new Object[0][]);
}
@@ -131,12 +127,8 @@
spliterators.add(splitDescr("LongStream.longRange(0,l):" + name,
() -> LongStream.range(0, longs.length).spliterator()));
- spliterators.add(splitDescr("LongStream.longRange(0,l,2):" + name,
- () -> LongStream.range(0, longs.length, 2).spliterator()));
- spliterators.add(splitDescr("LongStream.longRange(0,l,3):" + name,
- () -> LongStream.range(0, longs.length, 3).spliterator()));
- spliterators.add(splitDescr("LongStream.longRange(0,l,7):" + name,
- () -> LongStream.range(0, longs.length, 7).spliterator()));
+ spliterators.add(splitDescr("LongStream.longRangeClosed(0,l):" + name,
+ () -> LongStream.rangeClosed(0, longs.length).spliterator()));
// Need more!
}
spliteratorTestData = spliterators.toArray(new Object[0][]);
--- a/jdk/test/java/util/stream/test/org/openjdk/tests/java/util/stream/RangeTest.java Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/test/java/util/stream/test/org/openjdk/tests/java/util/stream/RangeTest.java Tue Jun 11 12:13:26 2013 +0200
@@ -24,10 +24,11 @@
import java.util.Arrays;
import java.util.Optional;
-import java.util.stream.DoubleStream;
+import java.util.Spliterator;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.OpTestCase;
+import java.util.stream.SpliteratorTestHelper;
import java.util.stream.Stream;
import java.util.stream.TestData;
@@ -54,73 +55,76 @@
//
- public void testIntRangeErrors() {
+ public void testIntRange() {
+ // Half-open
for (int start : Arrays.asList(1, 10, -1, -10)) {
for (int end : Arrays.asList(1, 10, -1, -10)) {
- for (int step : Arrays.asList(0, 1, -1, Integer.MAX_VALUE, Integer.MIN_VALUE)) {
- if (step > 0)
- executeAndNoCatch(() -> IntStream.range(start, end, step));
- else
- executeAndCatch(() -> IntStream.range(start, end, step));
- }
- }
- }
- }
-
- public void testIntRange() {
- // Without step
- for (int start : Arrays.asList(1, 10, -1, -10)) {
- for (int end : Arrays.asList(1, 10, -1, -10)) {
- int step = 1;
int size = (start < end) ? end - start : 0;
int[] exp = new int[size];
- if (start < end) {
- for (int i = start, p = 0; i < end; i++, p++) {
- exp[p] = i;
- }
+ for (int i = start, p = 0; i < end; i++, p++) {
+ exp[p] = i;
}
int[] inc = IntStream.range(start, end).toArray();
assertEquals(inc.length, size);
assertTrue(Arrays.equals(exp, inc));
- withData(intRangeData(start, end, step)).stream(s -> s).
+ withData(intRangeData(start, end)).stream(s -> s).
+ expectedResult(exp).exercise();
+ }
+ }
+
+ // Closed
+ for (int start : Arrays.asList(1, 10, -1, -10)) {
+ for (int end : Arrays.asList(1, 10, -1, -10)) {
+ int size = (start <= end) ? end - start + 1 : 0;
+ int[] exp = new int[size];
+ for (int i = start, p = 0; i <= end; i++, p++) {
+ exp[p] = i;
+ }
+
+ int[] inc = IntStream.rangeClosed(start, end).toArray();
+ assertEquals(inc.length, size);
+ assertTrue(Arrays.equals(exp, inc));
+
+ withData(intRangeClosedData(start, end)).stream(s -> s).
expectedResult(exp).exercise();
}
}
- // With step
- for (int start : Arrays.asList(1, 10, -1, -10)) {
- for (int end : Arrays.asList(1, 10, -1, -10)) {
- for (int step : Arrays.asList(1, -1, -2, 2)) {
- if (step > 0) {
- int d = end - start;
- int size = (start < end) ? (d / step) + ((d % step == 0) ? 0 : 1) : 0;
- int[] exp = new int[size];
- if (start < end) {
- for (int i = start, p = 0; i < end; i += step, p++) {
- exp[p] = i;
- }
- }
+ // Closed, maximum upper bound of Integer.MAX_VALUE
+ {
+ int[] inc = IntStream.rangeClosed(Integer.MAX_VALUE - 1, Integer.MAX_VALUE).toArray();
+ assertEquals(2, inc.length);
+ assertEquals(Integer.MAX_VALUE - 1, inc[0]);
+ assertEquals(Integer.MAX_VALUE, inc[1]);
- int[] inc = IntStream.range(start, end, step).toArray();
- assertEquals(inc.length, size);
- assertTrue(Arrays.equals(exp, inc));
+ inc = IntStream.rangeClosed(Integer.MAX_VALUE, Integer.MAX_VALUE).toArray();
+ assertEquals(1, inc.length);
+ assertEquals(Integer.MAX_VALUE, inc[0]);
- withData(intRangeData(start, end, step)).stream(s -> s).
- expectedResult(exp).exercise();
- }
- }
- }
+ SpliteratorTestHelper.testIntSpliterator(
+ () -> IntStream.rangeClosed(Integer.MAX_VALUE - 8, Integer.MAX_VALUE).spliterator());
+ }
+
+ // Range wider than Integer.MAX_VALUE
+ {
+ Spliterator.OfInt s = IntStream.rangeClosed(Integer.MIN_VALUE, Integer.MAX_VALUE).
+ spliterator();
+ assertEquals(s.estimateSize(), 1L << 32);
}
}
- TestData.OfInt intRangeData(int start, int end, int step) {
- return TestData.Factory.ofIntSupplier("int range", () -> IntStream.range(start, end, step));
+ TestData.OfInt intRangeData(int start, int end) {
+ return TestData.Factory.ofIntSupplier("int range", () -> IntStream.range(start, end));
+ }
+
+ TestData.OfInt intRangeClosedData(int start, int end) {
+ return TestData.Factory.ofIntSupplier("int rangeClosed", () -> IntStream.rangeClosed(start, end));
}
public void tesIntRangeReduce() {
- withData(intRangeData(0, 10000, 1)).
+ withData(intRangeData(0, 10000)).
terminal(s -> s.reduce(0, Integer::sum)).exercise();
}
@@ -137,74 +141,69 @@
//
- public void testLongRangeErrors() {
- for (long start : Arrays.asList(1, 10, -1, -10)) {
- for (long end : Arrays.asList(1, 10, -1, -10)) {
- for (long step : Arrays.asList(0L, 1L, -1L, Long.MAX_VALUE, Long.MIN_VALUE)) {
- if (step > 0)
- executeAndNoCatch(() -> LongStream.range(start, end, step));
- else
- executeAndCatch(() -> LongStream.range(start, end, step));
- }
- }
- }
- }
-
public void testLongRange() {
- // Without step
+ // Half-open
for (long start : Arrays.asList(1, 1000, -1, -1000)) {
for (long end : Arrays.asList(1, 1000, -1, -1000)) {
- long step = 1;
long size = start < end ? end - start : 0;
long[] exp = new long[(int) size];
- if (start < end) {
- for (long i = start, p = 0; i < end; i++, p++) {
- exp[(int) p] = i;
- }
+ for (long i = start, p = 0; i < end; i++, p++) {
+ exp[(int) p] = i;
}
long[] inc = LongStream.range(start, end).toArray();
assertEquals(inc.length, size);
assertTrue(Arrays.equals(exp, inc));
- withData(longRangeData(start, end, step)).stream(s -> s).
+ withData(longRangeData(start, end)).stream(s -> s).
+ expectedResult(exp).exercise();
+ }
+ }
+
+ // Closed
+ for (long start : Arrays.asList(1, 1000, -1, -1000)) {
+ for (long end : Arrays.asList(1, 1000, -1, -1000)) {
+ long size = start <= end ? end - start + 1: 0;
+ long[] exp = new long[(int) size];
+ for (long i = start, p = 0; i <= end; i++, p++) {
+ exp[(int) p] = i;
+ }
+
+ long[] inc = LongStream.rangeClosed(start, end).toArray();
+ assertEquals(inc.length, size);
+ assertTrue(Arrays.equals(exp, inc));
+
+ withData(longRangeClosedData(start, end)).stream(s -> s).
expectedResult(exp).exercise();
}
}
- // With step
- for (long start : Arrays.asList(1, 1000, -1, -1000)) {
- for (long end : Arrays.asList(1, 1000, -1, -1000)) {
- for (long step : Arrays.asList(1, -1, -2, 2)) {
- if (step > 0) {
+ // Closed, maximum upper bound of Long.MAX_VALUE
+ {
+ long[] inc = LongStream.rangeClosed(Long.MAX_VALUE - 1, Long.MAX_VALUE).toArray();
+ assertEquals(2, inc.length);
+ assertEquals(Long.MAX_VALUE - 1, inc[0]);
+ assertEquals(Long.MAX_VALUE, inc[1]);
- long d = end - start;
- long size = start < end ? (d / step) + ((d % step == 0) ? 0 : 1) : 0;
- long[] exp = new long[(int) size];
- if (start < end) {
- for (long i = start, p = 0; i < end; i += step, p++) {
- exp[(int) p] = i;
- }
- }
+ inc = LongStream.rangeClosed(Long.MAX_VALUE, Long.MAX_VALUE).toArray();
+ assertEquals(1, inc.length);
+ assertEquals(Long.MAX_VALUE, inc[0]);
- long[] inc = LongStream.range(start, end, step).toArray();
- assertEquals(inc.length, size);
- assertTrue(Arrays.equals(exp, inc));
-
- withData(longRangeData(start, end, step)).stream(s -> s).
- expectedResult(exp).exercise();
- }
- }
- }
+ SpliteratorTestHelper.testLongSpliterator(
+ () -> LongStream.rangeClosed(Long.MAX_VALUE - 8, Long.MAX_VALUE).spliterator());
}
}
- TestData.OfLong longRangeData(long start, long end, long step) {
- return TestData.Factory.ofLongSupplier("long range", () -> LongStream.range(start, end, step));
+ TestData.OfLong longRangeData(long start, long end) {
+ return TestData.Factory.ofLongSupplier("long range", () -> LongStream.range(start, end));
+ }
+
+ TestData.OfLong longRangeClosedData(long start, long end) {
+ return TestData.Factory.ofLongSupplier("long rangeClosed", () -> LongStream.rangeClosed(start, end));
}
public void testLongRangeReduce() {
- withData(longRangeData(0, 10000, 1)).
+ withData(longRangeData(0, 10000)).
terminal(s -> s.reduce(0, Long::sum)).exercise();
}
@@ -219,64 +218,116 @@
assertEquals(first, LongStream.iterate(0, i -> i + 1).parallel().filter(i -> i > 10000).findFirst().getAsLong());
}
- //
-
- private static int[] reverse(int[] a) {
- int[] b = new int[a.length];
- for (int i = 0; i < a.length; i++) {
- b[b.length - i - 1] = a[i];
- }
- return b;
- }
-
- private static long[] reverse(long[] a) {
- long[] b = new long[a.length];
- for (int i = 0; i < a.length; i++) {
- b[b.length - i - 1] = a[i];
- }
- return b;
- }
-
- private static double[] reverse(double[] a) {
- double[] b = new double[a.length];
- for (int i = 0; i < a.length; i++) {
- b[b.length - i - 1] = a[i];
- }
- return b;
- }
-
- private void executeAndCatch(Runnable r) {
- executeAndCatch(IllegalArgumentException.class, r);
- }
-
- private void executeAndNoCatch(Runnable r) {
- executeAndCatch(null, r);
- }
-
- private void executeAndCatch(Class<? extends Exception> expected, Runnable r) {
- Exception caught = null;
- try {
- r.run();
- }
- catch (Exception e) {
- caught = e;
- }
-
- if (expected != null) {
- assertNotNull(caught,
- String.format("No Exception was thrown, expected an Exception of %s to be thrown",
- expected.getName()));
- assertTrue(expected.isInstance(caught),
- String.format("Exception thrown %s not an instance of %s",
- caught.getClass().getName(), expected.getName()));
- }
- else {
- if (caught != null) {
- assertNull(caught,
- String.format("Unexpected exception of %s was thrown",
- caught.getClass().getName()));
- }
- }
- }
-
+ // Enable when Stream.concat is present and range implementations are
+ // updated to use that
+// private static void assertSizedAndSubSized(Spliterator<?> s) {
+// assertTrue(s.hasCharacteristics(Spliterator.SIZED | Spliterator.SUBSIZED));
+// }
+//
+// private static void assertNotSizedAndSubSized(Spliterator<?> s) {
+// assertFalse(s.hasCharacteristics(Spliterator.SIZED | Spliterator.SUBSIZED));
+// }
+//
+// public void testLongLongRange() {
+// // Test [Long.MIN_VALUE, Long.MAX_VALUE)
+// // This will concatenate streams of three ranges
+// // [Long.MIN_VALUE, x) [x, 0) [0, Long.MAX_VALUE)
+// // where x = Long.divideUnsigned(0 - Long.MIN_VALUE, 2) + 1
+// {
+// Spliterator.OfLong s = LongStream.range(Long.MIN_VALUE, Long.MAX_VALUE).spliterator();
+//
+// assertEquals(s.estimateSize(), Long.MAX_VALUE);
+// assertNotSizedAndSubSized(s);
+//
+// Spliterator.OfLong s1 = s.trySplit();
+// assertNotSizedAndSubSized(s1);
+// assertSizedAndSubSized(s);
+//
+// Spliterator.OfLong s2 = s1.trySplit();
+// assertSizedAndSubSized(s1);
+// assertSizedAndSubSized(s2);
+//
+// assertTrue(s.estimateSize() == Long.MAX_VALUE);
+// assertTrue(s1.estimateSize() < Long.MAX_VALUE);
+// assertTrue(s2.estimateSize() < Long.MAX_VALUE);
+//
+// assertEquals(s.estimateSize() + s1.estimateSize() + s2.estimateSize(),
+// Long.MAX_VALUE - Long.MIN_VALUE);
+// }
+//
+// long[][] ranges = { {Long.MIN_VALUE, 0}, {-1, Long.MAX_VALUE} };
+// for (int i = 0; i < ranges.length; i++) {
+// long start = ranges[i][0];
+// long end = ranges[i][1];
+//
+// Spliterator.OfLong s = LongStream.range(start, end).spliterator();
+//
+// assertEquals(s.estimateSize(), Long.MAX_VALUE);
+// assertNotSizedAndSubSized(s);
+//
+// Spliterator.OfLong s1 = s.trySplit();
+// assertSizedAndSubSized(s1);
+// assertSizedAndSubSized(s);
+//
+// assertTrue(s.estimateSize() < Long.MAX_VALUE);
+// assertTrue(s1.estimateSize() < Long.MAX_VALUE);
+//
+// assertEquals(s.estimateSize() + s1.estimateSize(), end - start);
+// }
+// }
+//
+// public void testLongLongRangeClosed() {
+// // Test [Long.MIN_VALUE, Long.MAX_VALUE]
+// // This will concatenate streams of four ranges
+// // [Long.MIN_VALUE, x) [x, 0) [0, y) [y, Long.MAX_VALUE]
+// // where x = Long.divideUnsigned(0 - Long.MIN_VALUE, 2) + 1
+// // y = Long.divideUnsigned(Long.MAX_VALUE, 2) + 1
+//
+// {
+// Spliterator.OfLong s = LongStream.rangeClosed(Long.MIN_VALUE, Long.MAX_VALUE).spliterator();
+//
+// assertEquals(s.estimateSize(), Long.MAX_VALUE);
+// assertNotSizedAndSubSized(s);
+//
+// Spliterator.OfLong s1 = s.trySplit();
+// assertNotSizedAndSubSized(s1);
+// assertNotSizedAndSubSized(s);
+//
+// Spliterator.OfLong s2 = s1.trySplit();
+// assertSizedAndSubSized(s1);
+// assertSizedAndSubSized(s2);
+//
+// Spliterator.OfLong s3 = s.trySplit();
+// assertSizedAndSubSized(s3);
+// assertSizedAndSubSized(s);
+//
+// assertTrue(s.estimateSize() < Long.MAX_VALUE);
+// assertTrue(s3.estimateSize() < Long.MAX_VALUE);
+// assertTrue(s1.estimateSize() < Long.MAX_VALUE);
+// assertTrue(s2.estimateSize() < Long.MAX_VALUE);
+//
+// assertEquals(s.estimateSize() + s3.estimateSize() + s1.estimateSize() + s2.estimateSize(),
+// Long.MAX_VALUE - Long.MIN_VALUE + 1);
+// }
+//
+// long[][] ranges = { {Long.MIN_VALUE, 0}, {-1, Long.MAX_VALUE} };
+// for (int i = 0; i < ranges.length; i++) {
+// long start = ranges[i][0];
+// long end = ranges[i][1];
+//
+// Spliterator.OfLong s = LongStream.rangeClosed(start, end).spliterator();
+//
+// assertEquals(s.estimateSize(), Long.MAX_VALUE);
+// assertNotSizedAndSubSized(s);
+//
+// Spliterator.OfLong s1 = s.trySplit();
+// assertSizedAndSubSized(s1);
+// assertSizedAndSubSized(s);
+//
+// assertTrue(s.estimateSize() < Long.MAX_VALUE);
+// assertTrue(s1.estimateSize() < Long.MAX_VALUE);
+//
+// assertEquals(s.estimateSize() + s1.estimateSize(), end - start + 1);
+// }
+// }
}