8015895: Int/LongStream.range/rangeClosed

8012986: Right-bias range spliterators for large ranges
Reviewed-by: mduigou

3 files changed, 202 insertions, 81 deletions

diff --git a/src/share/classes/java/util/stream/IntStream.java b/src/share/classes/java/util/stream/IntStream.java
index 35cbe29cc1..3545c9b83a 100644
--- a/src/share/classes/java/util/stream/IntStream.java
+++ b/src/share/classes/java/util/stream/IntStream.java
@@ -759,12 +759,13 @@ public interface IntStream extends BaseStream<Integer, IntStream> {
     /**
      * 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 @@ public interface IntStream extends BaseStream<Integer, IntStream> {
      *         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));
         }
     }
 }
diff --git a/src/share/classes/java/util/stream/LongStream.java b/src/share/classes/java/util/stream/LongStream.java
index cbdae128f9..1a1b241433 100644
--- a/src/share/classes/java/util/stream/LongStream.java
+++ b/src/share/classes/java/util/stream/LongStream.java
@@ -750,12 +750,13 @@ public interface LongStream extends BaseStream<Long, LongStream> {
     /**
      * 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 @@ public interface LongStream extends BaseStream<Long, LongStream> {
      *         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));
         }
     }
 }
diff --git a/src/share/classes/java/util/stream/Streams.java b/src/share/classes/java/util/stream/Streams.java
index 22b973f742..11dbbe3d7c 100644
--- a/src/share/classes/java/util/stream/Streams.java
+++ b/src/share/classes/java/util/stream/Streams.java
@@ -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 @@ class Streams {
      * 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;
+            }
+            else if (last > 0) {
+                last = 0;
+                consumer.accept(i);
+                return true;
             }
-            return hasNext;
+            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)
-                consumer.accept(i);
+            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);
+            }
         }
 
         @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 @@ class Streams {
 
         @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;
+            }
+            else if (last > 0) {
+                last = 0;
+                consumer.accept(i);
+                return true;
             }
-            return hasNext;
+            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)
-                consumer.accept(i);
+            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);
+            }
         }
 
         @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 @@ class Streams {
 
         @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;
         }
     }