Collection
, an IO channel, or a generator function.
A Spliterator may traverse elements individually (tryAdvance()
) or sequentially in bulk
(forEachRemaining()
).
A Spliterator may also partition off some of its elements (using
trySplit
) as another Spliterator, to be used in
possibly-parallel operations. Operations using a Spliterator that
cannot split, or does so in a highly imbalanced or inefficient
manner, are unlikely to benefit from parallelism. Traversal
and splitting exhaust elements; each Spliterator is useful for only a single
bulk computation.
A Spliterator also reports a set of characteristics()
of its
structure, source, and elements from among ORDERED
,
DISTINCT
, SORTED
, SIZED
, NONNULL
,
IMMUTABLE
, CONCURRENT
, and SUBSIZED
. These may
be employed by Spliterator clients to control, specialize or simplify
computation. For example, a Spliterator for a Collection
would
report SIZED
, a Spliterator for a Set
would report
DISTINCT
, and a Spliterator for a SortedSet
would also
report SORTED
. Characteristics are reported as a simple unioned bit
set.
Some characteristics additionally constrain method behavior; for example if
ORDERED
, traversal methods must conform to their documented ordering.
New characteristics may be defined in the future, so implementors should not
assign meanings to unlisted values.
A Spliterator that does not report IMMUTABLE
or
CONCURRENT
is expected to have a documented policy concerning:
when the spliterator binds to the element source; and detection of
structural interference of the element source detected after binding. A
late-binding Spliterator binds to the source of elements at the
point of first traversal, first split, or first query for estimated size,
rather than at the time the Spliterator is created. A Spliterator that is
not late-binding binds to the source of elements at the point of
construction or first invocation of any method. Modifications made to the
source prior to binding are reflected when the Spliterator is traversed.
After binding a Spliterator should, on a best-effort basis, throw
ConcurrentModificationException
if structural interference is
detected. Spliterators that do this are called fail-fast. The
bulk traversal method (forEachRemaining()
) of a
Spliterator may optimize traversal and check for structural interference
after all elements have been traversed, rather than checking per-element and
failing immediately.
Spliterators can provide an estimate of the number of remaining elements
via the estimateSize
method. Ideally, as reflected in characteristic
SIZED
, this value corresponds exactly to the number of elements
that would be encountered in a successful traversal. However, even when not
exactly known, an estimated value may still be useful to operations
being performed on the source, such as helping to determine whether it is
preferable to split further or traverse the remaining elements sequentially.
Despite their obvious utility in parallel algorithms, spliterators are not
expected to be thread-safe; instead, implementations of parallel algorithms
using spliterators should ensure that the spliterator is only used by one
thread at a time. This is generally easy to attain via serial
thread-confinement, which often is a natural consequence of typical
parallel algorithms that work by recursive decomposition. A thread calling
trySplit()
may hand over the returned Spliterator to another thread,
which in turn may traverse or further split that Spliterator. The behaviour
of splitting and traversal is undefined if two or more threads operate
concurrently on the same spliterator. If the original thread hands a
spliterator off to another thread for processing, it is best if that handoff
occurs before any elements are consumed with tryAdvance()
, as certain guarantees (such as the accuracy of
estimateSize()
for SIZED
spliterators) are only valid before
traversal has begun.
Primitive subtype specializations of Spliterator
are provided for
int
, long
, and double
values.
The subtype default implementations of
Spliterator#tryAdvance(java.
and Spliterator#forEachRemaining(java.
box
primitive values to instances of their corresponding wrapper class. Such
boxing may undermine any performance advantages gained by using the primitive
specializations. To avoid boxing, the corresponding primitive-based methods
should be used. For example,
Spliterator.
and Spliterator.
should be used in preference to
Spliterator.
and
Spliterator.
.
Traversal of primitive values using boxing-based methods
tryAdvance()
and
forEachRemaining()
does not affect the order in which the values, transformed to boxed values,
are encountered.
API Note
Spliterators, like Iterator
s, are for traversing the elements of
a source. The Spliterator
API was designed to support efficient
parallel traversal in addition to sequential traversal, by supporting
decomposition as well as single-element iteration. In addition, the
protocol for accessing elements via a Spliterator is designed to impose
smaller per-element overhead than Iterator
, and to avoid the inherent
race involved in having separate methods for hasNext()
and
next()
.
For mutable sources, arbitrary and non-deterministic behavior may occur if
the source is structurally interfered with (elements added, replaced, or
removed) between the time that the Spliterator binds to its data source and
the end of traversal. For example, such interference will produce arbitrary,
non-deterministic results when using the java.util.stream
framework.
Structural interference of a source can be managed in the following ways (in approximate order of decreasing desirability):
java.util.concurrent.CopyOnWriteArrayList
is an immutable source.
A Spliterator created from the source reports a characteristic of
IMMUTABLE
.java.util.concurrent.ConcurrentHashMap
is a concurrent source. A Spliterator created from the source reports a
characteristic of CONCURRENT
.ConcurrentModificationException
. For example, ArrayList
,
and many other non-concurrent Collection
classes in the JDK, provide
a late-binding, fail-fast spliterator.ConcurrentModificationException
since the window of potential
interference is larger.Example. Here is a class (not a very useful one, except for illustration) that maintains an array in which the actual data are held in even locations, and unrelated tag data are held in odd locations. Its Spliterator ignores the tags.
class TaggedArray<T> {
private final Object[] elements; // immutable after construction
TaggedArray(T[] data, Object[] tags) {
int size = data.length;
if (tags.length != size) throw new IllegalArgumentException();
this.elements = new Object[2 * size];
for (int i = 0, j = 0; i < size; ++i) {
elements[j++] = data[i];
elements[j++] = tags[i];
}
}
public Spliterator<T> spliterator() {
return new TaggedArraySpliterator<>(elements, 0, elements.length);
}
static class TaggedArraySpliterator<T> implements Spliterator<T> {
private final Object[] array;
private int origin; // current index, advanced on split or traversal
private final int fence; // one past the greatest index
TaggedArraySpliterator(Object[] array, int origin, int fence) {
this.array = array; this.origin = origin; this.fence = fence;
}
public void forEachRemaining(Consumer<? super T> action) {
for (; origin < fence; origin += 2)
action.accept((T) array[origin]);
}
public boolean tryAdvance(Consumer<? super T> action) {
if (origin < fence) {
action.accept((T) array[origin]);
origin += 2;
return true;
}
else // cannot advance
return false;
}
public Spliterator<T> trySplit() {
int lo = origin; // divide range in half
int mid = ((lo + fence) >>> 1) & ~1; // force midpoint to be even
if (lo < mid) { // split out left half
origin = mid; // reset this Spliterator's origin
return new TaggedArraySpliterator<>(array, lo, mid);
}
else // too small to split
return null;
}
public long estimateSize() {
return (long)((fence - origin) / 2);
}
public int characteristics() {
return ORDERED | SIZED | IMMUTABLE | SUBSIZED;
}
}
}
As an example how a parallel computation framework, such as the
java.util.stream
package, would use Spliterator in a parallel
computation, here is one way to implement an associated parallel forEach,
that illustrates the primary usage idiom of splitting off subtasks until
the estimated amount of work is small enough to perform
sequentially. Here we assume that the order of processing across
subtasks doesn't matter; different (forked) tasks may further split
and process elements concurrently in undetermined order. This
example uses a java.
;
similar usages apply to other parallel task constructions.
static <T> void parEach(TaggedArray<T> a, Consumer<T> action) {
Spliterator<T> s = a.spliterator();
long targetBatchSize = s.estimateSize() / (ForkJoinPool.getCommonPoolParallelism() * 8);
new ParEach(null, s, action, targetBatchSize).invoke();
}
static class ParEach<T> extends CountedCompleter<Void> {
final Spliterator<T> spliterator;
final Consumer<T> action;
final long targetBatchSize;
ParEach(ParEach<T> parent, Spliterator<T> spliterator,
Consumer<T> action, long targetBatchSize) {
super(parent);
this.spliterator = spliterator; this.action = action;
this.targetBatchSize = targetBatchSize;
}
public void compute() {
Spliterator<T> sub;
while (spliterator.estimateSize() > targetBatchSize &&
(sub = spliterator.trySplit()) != null) {
addToPendingCount(1);
new ParEach<>(this, sub, action, targetBatchSize).fork();
}
spliterator.forEachRemaining(action);
propagateCompletion();
}
}
Implementation Note
If the boolean system property org.openjdk.java.util.stream.tripwire
is set to true
then diagnostic warnings are reported if boxing of
primitive values occur when operating on primitive subtype specializations.
Collection
Modifier and Type | Class and Description |
---|---|
public static interface | Spliterator.
A Spliterator specialized for |
public static interface | Spliterator.
A Spliterator specialized for |
public static interface | Spliterator.
A Spliterator specialized for |
public static interface | Spliterator.
the type of elements returned by this Spliterator. The
type must be a wrapper type for a primitive type, such as T, Integer
for the primitive int type.the type of primitive consumer. The type must be a
primitive specialization of T_CONS, java. for
T , such as java. for
Integer .the type of primitive Spliterator. The type must be
a primitive specialization of Spliterator for T_SPLITR extends Spliterator.T , such as
Spliterator. for Integer .A Spliterator specialized for primitive values. |
Modifier and Type | Field and Description |
---|---|
public static final int | CONCURRENT
Characteristic value signifying that the element source may be safely concurrently modified (allowing additions, replacements, and/or removals) by multiple threads without external synchronization. |
public static final int | DISTINCT
Characteristic value signifying that, for each pair of
encountered elements |
public static final int | IMMUTABLE
Characteristic value signifying that the element source cannot be structurally modified; that is, elements cannot be added, replaced, or removed, so such changes cannot occur during traversal. |
public static final int | NONNULL
Characteristic value signifying that the source guarantees that
encountered elements will not be |
public static final int | ORDERED
Characteristic value signifying that an encounter order is defined for elements. |
public static final int | SIZED
Characteristic value signifying that the value returned from
|
public static final int | SORTED
Characteristic value signifying that encounter order follows a defined sort order. |
public static final int |
Modifier and Type | Method and Description |
---|---|
public int | Returns: a representation of characteristicsReturns a set of characteristics of this Spliterator and its elements. |
public long | Returns: the estimated size, orLong.MAX_VALUE if infinite,
unknown, or too expensive to compute.Returns an estimate of the number of elements that would be
encountered by a |
public default void | forEachRemaining(Consumer<? super T>
The action action)Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public default Comparator | Returns: a Comparator, ornull if the elements are sorted in the
natural order.If this Spliterator's source is |
public default long | Returns: the exact size, if known, else-1 .Convenience method that returns |
public default boolean | Returns: true if all the specified characteristics are present,
else false the characteristics to check for characteristics)Returns |
public boolean | Returns: false if no remaining elements existed
upon entry to this method, else true .The action whose operation is performed at-most once action)If a remaining element exists: performs the given action on it,
returning |
public Spliterator | Returns: aSpliterator covering some portion of the
elements, or null if this spliterator cannot be splitIf this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. |
CONCURRENT | back to summary |
---|---|
public static final int CONCURRENT Characteristic value signifying that the element source may be safely concurrently modified (allowing additions, replacements, and/or removals) by multiple threads without external synchronization. If so, the Spliterator is expected to have a documented policy concerning the impact of modifications during traversal. A top-level Spliterator should not report both A top-level Spliterator should not report both API Note Most concurrent collections maintain a consistency policy guaranteeing accuracy with respect to elements present at the point of Spliterator construction, but possibly not reflecting subsequent additions or removals. |
DISTINCT | back to summary |
---|---|
public static final int DISTINCT Characteristic value signifying that, for each pair of
encountered elements |
IMMUTABLE | back to summary |
---|---|
public static final int IMMUTABLE Characteristic value signifying that the element source cannot be
structurally modified; that is, elements cannot be added, replaced, or
removed, so such changes cannot occur during traversal. A Spliterator
that does not report |
NONNULL | back to summary |
---|---|
public static final int NONNULL Characteristic value signifying that the source guarantees that
encountered elements will not be |
ORDERED | back to summary |
---|---|
public static final int ORDERED Characteristic value signifying that an encounter order is defined for
elements. If so, this Spliterator guarantees that method
A |
SIZED | back to summary |
---|---|
public static final int SIZED Characteristic value signifying that the value returned from
API Note Most Spliterators for Collections, that cover all elements of a
|
SORTED | back to summary |
---|---|
public static final int SORTED Characteristic value signifying that encounter order follows a defined
sort order. If so, method A Spliterator that reports API Note The spliterators for |
SUBSIZED | back to summary |
---|---|
public static final int SUBSIZED Characteristic value signifying that all Spliterators resulting from
A Spliterator that does not report API Note Some spliterators, such as the top-level spliterator for an
approximately balanced binary tree, will report |
characteristics | back to summary |
---|---|
public int characteristics() Returns a set of characteristics of this Spliterator and its
elements. The result is represented as ORed values from If a Spliterator reports an inconsistent set of characteristics (either those returned from a single invocation or across multiple invocations), no guarantees can be made about any computation using this Spliterator. API Note The characteristics of a given spliterator before splitting
may differ from the characteristics after splitting. For specific
examples see the characteristic values
|
estimateSize | back to summary |
---|---|
public long estimateSize() Returns an estimate of the number of elements that would be
encountered by a If this Spliterator is API Note Even an inexact estimate is often useful and inexpensive to compute. For example, a sub-spliterator of an approximately balanced binary tree may return a value that estimates the number of elements to be half of that of its parent; if the root Spliterator does not maintain an accurate count, it could estimate size to be the power of two corresponding to its maximum depth.
|
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(Consumer<? super T> action) Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the action
throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification The default implementation repeatedly invokes
|
getComparator | back to summary |
---|---|
public default Comparator If this Spliterator's source is Implementation Specification The default implementation always throws
|
getExactSizeIfKnown | back to summary |
---|---|
public default long getExactSizeIfKnown() Convenience method that returns Implementation Specification The default implementation returns the result of
|
hasCharacteristics | back to summary |
---|---|
public default boolean hasCharacteristics(int characteristics) Returns Implementation Specification The default implementation returns true if the corresponding bits of the given characteristics are set.
|
tryAdvance | back to summary |
---|---|
public boolean tryAdvance(Consumer<? super T> action) If a remaining element exists: performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
trySplit | back to summary |
---|---|
public Spliterator If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. If this Spliterator is Unless this Spliterator covers an infinite number of elements,
repeated calls to
This method may return API Note An ideal
|
double
values.
Modifier and Type | Method and Description |
---|---|
public default void | forEachRemaining(DoubleConsumer
The action action)Overrides default java. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public default void | forEachRemaining(Consumer<? super Double>
The action action)Overrides default java. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public boolean | tryAdvance(DoubleConsumer
The action action)Redeclares java. If a remaining element exists, performs the given action on it,
returning |
public default boolean | tryAdvance(Consumer<? super Double>
The action action)Implements java. If a remaining element exists, performs the given action on it,
returning |
public Spliterator. | trySplit()
Redeclares java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. |
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(DoubleConsumer action) Overrides default java. Doc from java. Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(Consumer<? super Double> action) Overrides default java. Doc from java. Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification If the action is an instance of |
tryAdvance | back to summary |
---|---|
public boolean tryAdvance(DoubleConsumer action) Redeclares java. Doc from java. If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
tryAdvance | back to summary |
---|---|
public default boolean tryAdvance(Consumer<? super Double> action) Implements java. Doc from java. If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification If the action is an instance of |
trySplit | back to summary |
---|---|
public Spliterator. Redeclares java. Doc from java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. If this Spliterator is Unless this Spliterator covers an infinite number of elements,
repeated calls to
This method may return
|
int
values.
Modifier and Type | Method and Description |
---|---|
public default void | forEachRemaining(IntConsumer
The action action)Overrides default java. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public default void | forEachRemaining(Consumer<? super Integer>
The action action)Overrides default java. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public boolean | tryAdvance(IntConsumer
The action action)Redeclares java. If a remaining element exists, performs the given action on it,
returning |
public default boolean | tryAdvance(Consumer<? super Integer>
The action action)Implements java. If a remaining element exists, performs the given action on it,
returning |
public Spliterator. | trySplit()
Redeclares java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. |
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(IntConsumer action) Overrides default java. Doc from java. Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(Consumer<? super Integer> action) Overrides default java. Doc from java. Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification If the action is an instance of |
tryAdvance | back to summary |
---|---|
public boolean tryAdvance(IntConsumer action) Redeclares java. Doc from java. If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
tryAdvance | back to summary |
---|---|
public default boolean tryAdvance(Consumer<? super Integer> action) Implements java. Doc from java. If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification If the action is an instance of |
trySplit | back to summary |
---|---|
public Spliterator. Redeclares java. Doc from java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. If this Spliterator is Unless this Spliterator covers an infinite number of elements,
repeated calls to
This method may return
|
long
values.
Modifier and Type | Method and Description |
---|---|
public default void | forEachRemaining(LongConsumer
The action action)Overrides default java. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public default void | forEachRemaining(Consumer<? super Long>
The action action)Overrides default java. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public boolean | tryAdvance(LongConsumer
The action action)Redeclares java. If a remaining element exists, performs the given action on it,
returning |
public default boolean | tryAdvance(Consumer<? super Long>
The action action)Implements java. If a remaining element exists, performs the given action on it,
returning |
public Spliterator. | trySplit()
Redeclares java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. |
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(LongConsumer action) Overrides default java. Doc from java. Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(Consumer<? super Long> action) Overrides default java. Doc from java. Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification If the action is an instance of |
tryAdvance | back to summary |
---|---|
public boolean tryAdvance(LongConsumer action) Redeclares java. Doc from java. If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
tryAdvance | back to summary |
---|---|
public default boolean tryAdvance(Consumer<? super Long> action) Implements java. Doc from java. If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification If the action is an instance of |
trySplit | back to summary |
---|---|
public Spliterator. Redeclares java. Doc from java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. If this Spliterator is Unless this Spliterator covers an infinite number of elements,
repeated calls to
This method may return
|
Integer
for the primitive int
type.
java.util.function.Consumer
for
T
, such as java.util.function.IntConsumer
for
Integer
.
T
, such as
Spliterator.OfInt
for Integer
.
Spliterator.OfInt
, Spliterator.OfLong
, Spliterator.OfDouble
Modifier and Type | Method and Description |
---|---|
public default void | forEachRemaining(T_CONS
The action action)Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. |
public boolean | Returns: false if no remaining elements existed
upon entry to this method, else true .The action action)If a remaining element exists, performs the given action on it,
returning |
public T_SPLITR | trySplit()
Redeclares java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. |
forEachRemaining | back to summary |
---|---|
public default void forEachRemaining(T_CONS action) Performs the given action for each remaining element, sequentially in
the current thread, until all elements have been processed or the
action throws an exception. If this Spliterator is Subsequent behavior of a spliterator is unspecified if the action throws an exception. Implementation Specification The default implementation repeatedly invokes
|
tryAdvance | back to summary |
---|---|
public boolean tryAdvance(T_CONS action) If a remaining element exists, performs the given action on it,
returning Subsequent behavior of a spliterator is unspecified if the action throws an exception.
|
trySplit | back to summary |
---|---|
public T_SPLITR trySplit() Redeclares java. Doc from java. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. If this Spliterator is Unless this Spliterator covers an infinite number of elements,
repeated calls to
This method may return
|