/*
* Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package java.util.stream;
import java.util.
Comparator;
import java.util.
Objects;
import java.util.
Spliterator;
import java.util.function.
Consumer;
import java.util.function.
DoubleConsumer;
import java.util.function.
IntConsumer;
import java.util.function.
LongConsumer;
/**
* Utility methods for operating on and creating streams.
*
* <p>Unless otherwise stated, streams are created as sequential streams. A
* sequential stream can be transformed into a parallel stream by calling the
* {@code parallel()} method on the created stream.
*
* @since 1.8
*/
final class
Streams {
private
Streams() {
throw new
Error("no instances");
}
/**
* An object instance representing no value, that cannot be an actual
* data element of a stream. Used when processing streams that can contain
* {@code null} elements to distinguish between a {@code null} value and no
* value.
*/
static final
Object NONE = new
Object();
/**
* 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;
// 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, boolean
closed) {
this(
from,
upTo,
closed ? 1 : 0);
}
private
RangeIntSpliterator(int
from, int
upTo, int
last) {
this.
from =
from;
this.
upTo =
upTo;
this.
last =
last;
}
@
Override
public boolean
tryAdvance(
IntConsumer consumer) {
Objects.
requireNonNull(
consumer);
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 false;
}
@
Override
public void
forEachRemaining(
IntConsumer consumer) {
Objects.
requireNonNull(
consumer);
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() {
// Ensure ranges of size > Integer.MAX_VALUE report the correct size
return ((long)
upTo) -
from +
last;
}
@
Override
public int
characteristics() {
return
Spliterator.
ORDERED |
Spliterator.
SIZED |
Spliterator.
SUBSIZED |
Spliterator.
IMMUTABLE |
Spliterator.
NONNULL |
Spliterator.
DISTINCT |
Spliterator.
SORTED;
}
@
Override
public
Comparator<? super
Integer>
getComparator() {
return null;
}
@
Override
public
Spliterator.
OfInt trySplit() {
long
size =
estimateSize();
return
size <= 1
? null
// Left split always has a half-open range
: new
RangeIntSpliterator(
from,
from =
from +
splitPoint(
size), 0);
}
/**
* 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;
// Cast to int is safe since:
// 2 <= size < 2^32
// 2 <= d <= 8
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;
// 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, 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.
last =
last;
}
@
Override
public boolean
tryAdvance(
LongConsumer consumer) {
Objects.
requireNonNull(
consumer);
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 false;
}
@
Override
public void
forEachRemaining(
LongConsumer consumer) {
Objects.
requireNonNull(
consumer);
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() {
return
upTo -
from +
last;
}
@
Override
public int
characteristics() {
return
Spliterator.
ORDERED |
Spliterator.
SIZED |
Spliterator.
SUBSIZED |
Spliterator.
IMMUTABLE |
Spliterator.
NONNULL |
Spliterator.
DISTINCT |
Spliterator.
SORTED;
}
@
Override
public
Comparator<? super
Long>
getComparator() {
return null;
}
@
Override
public
Spliterator.
OfLong trySplit() {
long
size =
estimateSize();
return
size <= 1
? null
// Left split always has a half-open range
: new
RangeLongSpliterator(
from,
from =
from +
splitPoint(
size), 0);
}
/**
* 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;
}
}
private static abstract class
AbstractStreamBuilderImpl<T, S extends
Spliterator<T>> implements
Spliterator<T> {
// >= 0 when building, < 0 when built
// -1 == no elements
// -2 == one element, held by first
// -3 == two or more elements, held by buffer
int
count;
// Spliterator implementation for 0 or 1 element
// count == -1 for no elements
// count == -2 for one element held by first
@
Override
public S
trySplit() {
return null;
}
@
Override
public long
estimateSize() {
return -
count - 1;
}
@
Override
public int
characteristics() {
return
Spliterator.
SIZED |
Spliterator.
SUBSIZED |
Spliterator.
ORDERED |
Spliterator.
IMMUTABLE;
}
}
static final class
StreamBuilderImpl<T>
extends
AbstractStreamBuilderImpl<T,
Spliterator<T>>
implements
Stream.
Builder<T> {
// The first element in the stream
// valid if count == 1
T
first;
// The first and subsequent elements in the stream
// non-null if count == 2
SpinedBuffer<T>
buffer;
/**
* Constructor for building a stream of 0 or more elements.
*/
StreamBuilderImpl() { }
/**
* Constructor for a singleton stream.
*
* @param t the single element
*/
StreamBuilderImpl(T
t) {
first =
t;
count = -2;
}
// StreamBuilder implementation
@
Override
public void
accept(T
t) {
if (
count == 0) {
first =
t;
count++;
}
else if (
count > 0) {
if (
buffer == null) {
buffer = new
SpinedBuffer<>();
buffer.
accept(
first);
count++;
}
buffer.
accept(
t);
}
else {
throw new
IllegalStateException();
}
}
public
Stream.
Builder<T>
add(T
t) {
accept(
t);
return this;
}
@
Override
public
Stream<T>
build() {
int
c =
count;
if (
c >= 0) {
// Switch count to negative value signalling the builder is built
count = -
count - 1;
// Use this spliterator if 0 or 1 elements, otherwise use
// the spliterator of the spined buffer
return (
c < 2) ?
StreamSupport.
stream(this, false) :
StreamSupport.
stream(
buffer.
spliterator(), false);
}
throw new
IllegalStateException();
}
// Spliterator implementation for 0 or 1 element
// count == -1 for no elements
// count == -2 for one element held by first
@
Override
public boolean
tryAdvance(
Consumer<? super T>
action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
return true;
}
else {
return false;
}
}
@
Override
public void
forEachRemaining(
Consumer<? super T>
action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
}
}
}
static final class
IntStreamBuilderImpl
extends
AbstractStreamBuilderImpl<
Integer,
Spliterator.
OfInt>
implements
IntStream.
Builder,
Spliterator.
OfInt {
// The first element in the stream
// valid if count == 1
int
first;
// The first and subsequent elements in the stream
// non-null if count == 2
SpinedBuffer.
OfInt buffer;
/**
* Constructor for building a stream of 0 or more elements.
*/
IntStreamBuilderImpl() { }
/**
* Constructor for a singleton stream.
*
* @param t the single element
*/
IntStreamBuilderImpl(int
t) {
first =
t;
count = -2;
}
// StreamBuilder implementation
@
Override
public void
accept(int
t) {
if (
count == 0) {
first =
t;
count++;
}
else if (
count > 0) {
if (
buffer == null) {
buffer = new
SpinedBuffer.
OfInt();
buffer.
accept(
first);
count++;
}
buffer.
accept(
t);
}
else {
throw new
IllegalStateException();
}
}
@
Override
public
IntStream build() {
int
c =
count;
if (
c >= 0) {
// Switch count to negative value signalling the builder is built
count = -
count - 1;
// Use this spliterator if 0 or 1 elements, otherwise use
// the spliterator of the spined buffer
return (
c < 2) ?
StreamSupport.
intStream(this, false) :
StreamSupport.
intStream(
buffer.
spliterator(), false);
}
throw new
IllegalStateException();
}
// Spliterator implementation for 0 or 1 element
// count == -1 for no elements
// count == -2 for one element held by first
@
Override
public boolean
tryAdvance(
IntConsumer action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
return true;
}
else {
return false;
}
}
@
Override
public void
forEachRemaining(
IntConsumer action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
}
}
}
static final class
LongStreamBuilderImpl
extends
AbstractStreamBuilderImpl<
Long,
Spliterator.
OfLong>
implements
LongStream.
Builder,
Spliterator.
OfLong {
// The first element in the stream
// valid if count == 1
long
first;
// The first and subsequent elements in the stream
// non-null if count == 2
SpinedBuffer.
OfLong buffer;
/**
* Constructor for building a stream of 0 or more elements.
*/
LongStreamBuilderImpl() { }
/**
* Constructor for a singleton stream.
*
* @param t the single element
*/
LongStreamBuilderImpl(long
t) {
first =
t;
count = -2;
}
// StreamBuilder implementation
@
Override
public void
accept(long
t) {
if (
count == 0) {
first =
t;
count++;
}
else if (
count > 0) {
if (
buffer == null) {
buffer = new
SpinedBuffer.
OfLong();
buffer.
accept(
first);
count++;
}
buffer.
accept(
t);
}
else {
throw new
IllegalStateException();
}
}
@
Override
public
LongStream build() {
int
c =
count;
if (
c >= 0) {
// Switch count to negative value signalling the builder is built
count = -
count - 1;
// Use this spliterator if 0 or 1 elements, otherwise use
// the spliterator of the spined buffer
return (
c < 2) ?
StreamSupport.
longStream(this, false) :
StreamSupport.
longStream(
buffer.
spliterator(), false);
}
throw new
IllegalStateException();
}
// Spliterator implementation for 0 or 1 element
// count == -1 for no elements
// count == -2 for one element held by first
@
Override
public boolean
tryAdvance(
LongConsumer action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
return true;
}
else {
return false;
}
}
@
Override
public void
forEachRemaining(
LongConsumer action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
}
}
}
static final class
DoubleStreamBuilderImpl
extends
AbstractStreamBuilderImpl<
Double,
Spliterator.
OfDouble>
implements
DoubleStream.
Builder,
Spliterator.
OfDouble {
// The first element in the stream
// valid if count == 1
double
first;
// The first and subsequent elements in the stream
// non-null if count == 2
SpinedBuffer.
OfDouble buffer;
/**
* Constructor for building a stream of 0 or more elements.
*/
DoubleStreamBuilderImpl() { }
/**
* Constructor for a singleton stream.
*
* @param t the single element
*/
DoubleStreamBuilderImpl(double
t) {
first =
t;
count = -2;
}
// StreamBuilder implementation
@
Override
public void
accept(double
t) {
if (
count == 0) {
first =
t;
count++;
}
else if (
count > 0) {
if (
buffer == null) {
buffer = new
SpinedBuffer.
OfDouble();
buffer.
accept(
first);
count++;
}
buffer.
accept(
t);
}
else {
throw new
IllegalStateException();
}
}
@
Override
public
DoubleStream build() {
int
c =
count;
if (
c >= 0) {
// Switch count to negative value signalling the builder is built
count = -
count - 1;
// Use this spliterator if 0 or 1 elements, otherwise use
// the spliterator of the spined buffer
return (
c < 2) ?
StreamSupport.
doubleStream(this, false) :
StreamSupport.
doubleStream(
buffer.
spliterator(), false);
}
throw new
IllegalStateException();
}
// Spliterator implementation for 0 or 1 element
// count == -1 for no elements
// count == -2 for one element held by first
@
Override
public boolean
tryAdvance(
DoubleConsumer action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
return true;
}
else {
return false;
}
}
@
Override
public void
forEachRemaining(
DoubleConsumer action) {
Objects.
requireNonNull(
action);
if (
count == -2) {
action.
accept(
first);
count = -1;
}
}
}
abstract static class
ConcatSpliterator<T, T_SPLITR extends
Spliterator<T>>
implements
Spliterator<T> {
protected final T_SPLITR
aSpliterator;
protected final T_SPLITR
bSpliterator;
// True when no split has occurred, otherwise false
boolean
beforeSplit;
// Never read after splitting
final boolean
unsized;
public
ConcatSpliterator(T_SPLITR
aSpliterator, T_SPLITR
bSpliterator) {
this.
aSpliterator =
aSpliterator;
this.
bSpliterator =
bSpliterator;
beforeSplit = true;
// The spliterator is known to be unsized before splitting if the
// sum of the estimates overflows.
unsized =
aSpliterator.
estimateSize() +
bSpliterator.
estimateSize() < 0;
}
@
Override
public T_SPLITR
trySplit() {
@
SuppressWarnings("unchecked")
T_SPLITR
ret =
beforeSplit ?
aSpliterator : (T_SPLITR)
bSpliterator.
trySplit();
beforeSplit = false;
return
ret;
}
@
Override
public boolean
tryAdvance(
Consumer<? super T>
consumer) {
boolean
hasNext;
if (
beforeSplit) {
hasNext =
aSpliterator.
tryAdvance(
consumer);
if (!
hasNext) {
beforeSplit = false;
hasNext =
bSpliterator.
tryAdvance(
consumer);
}
}
else
hasNext =
bSpliterator.
tryAdvance(
consumer);
return
hasNext;
}
@
Override
public void
forEachRemaining(
Consumer<? super T>
consumer) {
if (
beforeSplit)
aSpliterator.
forEachRemaining(
consumer);
bSpliterator.
forEachRemaining(
consumer);
}
@
Override
public long
estimateSize() {
if (
beforeSplit) {
// If one or both estimates are Long.MAX_VALUE then the sum
// will either be Long.MAX_VALUE or overflow to a negative value
long
size =
aSpliterator.
estimateSize() +
bSpliterator.
estimateSize();
return (
size >= 0) ?
size :
Long.
MAX_VALUE;
}
else {
return
bSpliterator.
estimateSize();
}
}
@
Override
public int
characteristics() {
if (
beforeSplit) {
// Concatenation loses DISTINCT and SORTED characteristics
return
aSpliterator.
characteristics() &
bSpliterator.
characteristics()
& ~(
Spliterator.
DISTINCT |
Spliterator.
SORTED
| (
unsized ?
Spliterator.
SIZED |
Spliterator.
SUBSIZED : 0));
}
else {
return
bSpliterator.
characteristics();
}
}
@
Override
public
Comparator<? super T>
getComparator() {
if (
beforeSplit)
throw new
IllegalStateException();
return
bSpliterator.
getComparator();
}
static class
OfRef<T> extends
ConcatSpliterator<T,
Spliterator<T>> {
OfRef(
Spliterator<T>
aSpliterator,
Spliterator<T>
bSpliterator) {
super(
aSpliterator,
bSpliterator);
}
}
private static abstract class
OfPrimitive<T, T_CONS, T_SPLITR extends
Spliterator.
OfPrimitive<T, T_CONS, T_SPLITR>>
extends
ConcatSpliterator<T, T_SPLITR>
implements
Spliterator.
OfPrimitive<T, T_CONS, T_SPLITR> {
private
OfPrimitive(T_SPLITR
aSpliterator, T_SPLITR
bSpliterator) {
super(
aSpliterator,
bSpliterator);
}
@
Override
public boolean
tryAdvance(T_CONS
action) {
boolean
hasNext;
if (
beforeSplit) {
hasNext =
aSpliterator.
tryAdvance(
action);
if (!
hasNext) {
beforeSplit = false;
hasNext =
bSpliterator.
tryAdvance(
action);
}
}
else
hasNext =
bSpliterator.
tryAdvance(
action);
return
hasNext;
}
@
Override
public void
forEachRemaining(T_CONS
action) {
if (
beforeSplit)
aSpliterator.
forEachRemaining(
action);
bSpliterator.
forEachRemaining(
action);
}
}
static class
OfInt
extends
ConcatSpliterator.
OfPrimitive<
Integer,
IntConsumer,
Spliterator.
OfInt>
implements
Spliterator.
OfInt {
OfInt(
Spliterator.
OfInt aSpliterator,
Spliterator.
OfInt bSpliterator) {
super(
aSpliterator,
bSpliterator);
}
}
static class
OfLong
extends
ConcatSpliterator.
OfPrimitive<
Long,
LongConsumer,
Spliterator.
OfLong>
implements
Spliterator.
OfLong {
OfLong(
Spliterator.
OfLong aSpliterator,
Spliterator.
OfLong bSpliterator) {
super(
aSpliterator,
bSpliterator);
}
}
static class
OfDouble
extends
ConcatSpliterator.
OfPrimitive<
Double,
DoubleConsumer,
Spliterator.
OfDouble>
implements
Spliterator.
OfDouble {
OfDouble(
Spliterator.
OfDouble aSpliterator,
Spliterator.
OfDouble bSpliterator) {
super(
aSpliterator,
bSpliterator);
}
}
}
/**
* Given two Runnables, return a Runnable that executes both in sequence,
* even if the first throws an exception, and if both throw exceptions, add
* any exceptions thrown by the second as suppressed exceptions of the first.
*/
static
Runnable composeWithExceptions(
Runnable a,
Runnable b) {
return new
Runnable() {
@
Override
public void
run() {
try {
a.
run();
}
catch (
Throwable e1) {
try {
b.
run();
}
catch (
Throwable e2) {
try {
e1.
addSuppressed(
e2);
} catch (
Throwable ignore) {}
}
throw
e1;
}
b.
run();
}
};
}
/**
* Given two streams, return a Runnable that
* executes both of their {@link BaseStream#close} methods in sequence,
* even if the first throws an exception, and if both throw exceptions, add
* any exceptions thrown by the second as suppressed exceptions of the first.
*/
static
Runnable composedClose(
BaseStream<?, ?>
a,
BaseStream<?, ?>
b) {
return new
Runnable() {
@
Override
public void
run() {
try {
a.
close();
}
catch (
Throwable e1) {
try {
b.
close();
}
catch (
Throwable e2) {
try {
e1.
addSuppressed(
e2);
} catch (
Throwable ignore) {}
}
throw
e1;
}
b.
close();
}
};
}
}