Spliterator
public
interface
Spliterator
java.util.Spliterator<T> |
An object for traversing and partitioning elements of a source. The source
of elements covered by a Spliterator could be, for example, an array, a
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.util.function.Consumer)
and Spliterator#forEachRemaining(java.util.function.Consumer)
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.OfInt#tryAdvance(java.util.function.IntConsumer)
and Spliterator.OfInt#forEachRemaining(java.util.function.IntConsumer)
should be used in preference to
Spliterator.OfInt#tryAdvance(java.util.function.Consumer)
and
Spliterator.OfInt#forEachRemaining(java.util.function.Consumer)
.
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.
See also:
Summary
Nested classes | |
---|---|
interface |
Spliterator.OfDouble
A Spliterator specialized for |
interface |
Spliterator.OfInt
A Spliterator specialized for |
interface |
Spliterator.OfLong
A Spliterator specialized for |
interface |
Spliterator.OfPrimitive<T, T_CONS, T_SPLITR extends OfPrimitive<T, T_CONS, T_SPLITR>>
A Spliterator specialized for primitive values. |
Constants | |
---|---|
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. |
int |
DISTINCT
Characteristic value signifying that, for each pair of
encountered elements |
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. |
int |
NONNULL
Characteristic value signifying that the source guarantees that
encountered elements will not be |
int |
ORDERED
Characteristic value signifying that an encounter order is defined for elements. |
int |
SIZED
Characteristic value signifying that the value returned from
|
int |
SORTED
Characteristic value signifying that encounter order follows a defined sort order. |
int |
SUBSIZED
Characteristic value signifying that all Spliterators resulting from
|
Public methods | |
---|---|
abstract
int
|
characteristics()
Returns a set of characteristics of this Spliterator and its elements. |
abstract
long
|
estimateSize()
Returns an estimate of the number of elements that would be
encountered by a |
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. |
default
Comparator<? super T>
|
getComparator()
If this Spliterator's source is |
default
long
|
getExactSizeIfKnown()
Convenience method that returns |
default
boolean
|
hasCharacteristics(int characteristics)
Returns |
abstract
boolean
|
tryAdvance(Consumer<? super T> action)
If a remaining element exists, performs the given action on it,
returning |
abstract
Spliterator<T>
|
trySplit()
If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator. |
Constants
CONCURRENT
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 CONCURRENT
and
SIZED
, since the finite size, if known, may change if the source
is concurrently modified during traversal. Such a Spliterator is
inconsistent and no guarantees can be made about any computation using
that Spliterator. Sub-spliterators may report SIZED
if the
sub-split size is known and additions or removals to the source are not
reflected when traversing.
A top-level Spliterator should not report both CONCURRENT
and
IMMUTABLE
, since they are mutually exclusive. Such a Spliterator
is inconsistent and no guarantees can be made about any computation using
that Spliterator. Sub-spliterators may report IMMUTABLE
if
additions or removals to the source are not reflected when traversing.
Constant Value: 4096 (0x00001000)
DISTINCT
public static final int DISTINCT
Characteristic value signifying that, for each pair of
encountered elements x, y
, !x.equals(y)
. This
applies for example, to a Spliterator based on a Set
.
Constant Value: 1 (0x00000001)
IMMUTABLE
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 IMMUTABLE
or CONCURRENT
is expected
to have a documented policy (for example throwing
ConcurrentModificationException
) concerning structural
interference detected during traversal.
Constant Value: 1024 (0x00000400)
NONNULL
public static final int NONNULL
Characteristic value signifying that the source guarantees that
encountered elements will not be null
. (This applies,
for example, to most concurrent collections, queues, and maps.)
Constant Value: 256 (0x00000100)
ORDERED
public static final int ORDERED
Characteristic value signifying that an encounter order is defined for
elements. If so, this Spliterator guarantees that method
trySplit()
splits a strict prefix of elements, that method
tryAdvance(Consumer)
steps by one element in prefix order, and that
forEachRemaining(Consumer)
performs actions in encounter order.
A Collection
has an encounter order if the corresponding
Collection#iterator
documents an order. If so, the encounter
order is the same as the documented order. Otherwise, a collection does
not have an encounter order.
Constant Value: 16 (0x00000010)
SIZED
public static final int SIZED
Characteristic value signifying that the value returned from
estimateSize()
prior to traversal or splitting represents a
finite size that, in the absence of structural source modification,
represents an exact count of the number of elements that would be
encountered by a complete traversal.
Constant Value: 64 (0x00000040)
SORTED
public static final int SORTED
Characteristic value signifying that encounter order follows a defined
sort order. If so, method getComparator()
returns the associated
Comparator, or null
if all elements are Comparable
and
are sorted by their natural ordering.
A Spliterator that reports SORTED
must also report
ORDERED
.
Constant Value: 4 (0x00000004)
SUBSIZED
public static final int SUBSIZED
Characteristic value signifying that all Spliterators resulting from
trySplit()
will be both SIZED
and SUBSIZED
.
(This means that all child Spliterators, whether direct or indirect, will
be SIZED
.)
A Spliterator that does not report SIZED
as required by
SUBSIZED
is inconsistent and no guarantees can be made about any
computation using that Spliterator.
Constant Value: 16384 (0x00004000)
Public methods
characteristics
public abstract int characteristics ()
Returns a set of characteristics of this Spliterator and its
elements. The result is represented as ORed values from ORDERED
, DISTINCT
, SORTED
, SIZED
,
NONNULL
, IMMUTABLE
, CONCURRENT
,
SUBSIZED
. Repeated calls to characteristics()
on
a given spliterator, prior to or in-between calls to trySplit
,
should always return the same result.
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
SIZED
,SUBSIZED
andCONCURRENT
.
Returns | |
---|---|
int |
a representation of characteristics |
estimateSize
public abstract long estimateSize ()
Returns an estimate of the number of elements that would be
encountered by a forEachRemaining(Consumer)
traversal, or returns Long.MAX_VALUE
if infinite, unknown, or too expensive to compute.
If this Spliterator is SIZED
and has not yet been partially
traversed or split, or this Spliterator is SUBSIZED
and has
not yet been partially traversed, this estimate must be an accurate
count of elements that would be encountered by a complete traversal.
Otherwise, this estimate may be arbitrarily inaccurate, but must decrease
as specified across invocations of trySplit()
.
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.
Returns | |
---|---|
long |
the estimated size, or Long.MAX_VALUE if infinite,
unknown, or too expensive to compute. |
forEachRemaining
public 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 ORDERED
, actions
are performed in encounter order. Exceptions thrown by the action
are relayed to the caller.
Subsequent behavior of a spliterator is unspecified if the action throws an exception.
Implementation Requirements:
- The default implementation repeatedly invokes
tryAdvance(Consumer)
until it returnsfalse
. It should be overridden whenever possible.
Parameters | |
---|---|
action |
Consumer : The action |
Throws | |
---|---|
NullPointerException |
if the specified action is null |
getComparator
public Comparator<? super T> getComparator ()
If this Spliterator's source is SORTED
by a Comparator
,
returns that Comparator
. If the source is SORTED
in
natural order, returns null
. Otherwise,
if the source is not SORTED
, throws IllegalStateException
.
Implementation Requirements:
- The default implementation always throws
IllegalStateException
.
Returns | |
---|---|
Comparator<? super T> |
a Comparator, or null if the elements are sorted in the
natural order. |
Throws | |
---|---|
IllegalStateException |
if the spliterator does not report
a characteristic of SORTED . |
getExactSizeIfKnown
public long getExactSizeIfKnown ()
Convenience method that returns estimateSize()
if this
Spliterator is SIZED
, else -1
.
Implementation Requirements:
- The default implementation returns the result of
estimateSize()
if the Spliterator reports a characteristic ofSIZED
, and-1
otherwise.
Returns | |
---|---|
long |
the exact size, if known, else -1 . |
hasCharacteristics
public boolean hasCharacteristics (int characteristics)
Returns true
if this Spliterator's characteristics()
contain all of the given characteristics.
Implementation Requirements:
- The default implementation returns true if the corresponding bits of the given characteristics are set.
Parameters | |
---|---|
characteristics |
int : the characteristics to check for |
Returns | |
---|---|
boolean |
true if all the specified characteristics are present,
else false |
tryAdvance
public abstract boolean tryAdvance (Consumer<? super T> action)
If a remaining element exists, performs the given action on it,
returning true
; else returns false
. If this
Spliterator is ORDERED
the action is performed on the
next element in encounter order. Exceptions thrown by the
action are relayed to the caller.
Subsequent behavior of a spliterator is unspecified if the action throws an exception.
Parameters | |
---|---|
action |
Consumer : The action |
Returns | |
---|---|
boolean |
false if no remaining elements existed
upon entry to this method, else true . |
Throws | |
---|---|
NullPointerException |
if the specified action is null |
trySplit
public abstract Spliterator<T> trySplit ()
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 ORDERED
, the returned Spliterator
must cover a strict prefix of the elements.
Unless this Spliterator covers an infinite number of elements,
repeated calls to trySplit()
must eventually return null
.
Upon non-null return:
- the value reported for
estimateSize()
before splitting, must, after splitting, be greater than or equal toestimateSize()
for this and the returned Spliterator; and - if this Spliterator is
SUBSIZED
, thenestimateSize()
for this spliterator before splitting must be equal to the sum ofestimateSize()
for this and the returned Spliterator after splitting.
This method may return null
for any reason,
including emptiness, inability to split after traversal has
commenced, data structure constraints, and efficiency
considerations.
API Note:
- An ideal
trySplit
method efficiently (without traversal) divides its elements exactly in half, allowing balanced parallel computation. Many departures from this ideal remain highly effective; for example, only approximately splitting an approximately balanced tree, or for a tree in which leaf nodes may contain either one or two elements, failing to further split these nodes. However, large deviations in balance and/or overly inefficienttrySplit
mechanics typically result in poor parallel performance.
Returns | |
---|---|
Spliterator<T> |
a Spliterator covering some portion of the
elements, or null if this spliterator cannot be split |
Content and code samples on this page are subject to the licenses described in the Content License. Java and OpenJDK are trademarks or registered trademarks of Oracle and/or its affiliates.
Last updated 2023-06-07 UTC.