T
- the type of elements returned by this SpliteratorSpliterator.OfDouble
, Spliterator.OfInt
, Spliterator.OfLong
, Spliterator.OfPrimitive<T,T_CONS,T_SPLITR>
Spliterators.AbstractDoubleSpliterator
, Spliterators.AbstractIntSpliterator
, Spliterators.AbstractLongSpliterator
, Spliterators.AbstractSpliterator
public interface Spliterator<T>
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 tryAdvance(java.util.function.Consumer)
and 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.OfPrimitive.tryAdvance(java.util.function.IntConsumer)
and Spliterator.OfPrimitive.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.
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):
CopyOnWriteArrayList
is an immutable source. A Spliterator created from the source reports a characteristic of IMMUTABLE
.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 CountedCompleter
; 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();
}
}
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.Modifier and Type | Interface | Description |
---|---|---|
static interface |
Spliterator.OfDouble |
A Spliterator specialized for double values. |
static interface |
Spliterator.OfInt |
A Spliterator specialized for int values. |
static interface |
Spliterator.OfLong |
A Spliterator specialized for long values. |
static interface |
Spliterator.OfPrimitive<T, |
A Spliterator specialized for primitive values. |
Modifier and Type | Field | Description |
---|---|---|
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. |
static final int |
DISTINCT |
Characteristic value signifying that, for each pair of encountered elements x, y , !x.equals(y) . |
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. |
static final int |
NONNULL |
Characteristic value signifying that the source guarantees that encountered elements will not be null . |
static final int |
ORDERED |
Characteristic value signifying that an encounter order is defined for elements. |
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. |
static final int |
SORTED |
Characteristic value signifying that encounter order follows a defined sort order. |
static final int |
SUBSIZED |
Modifier and Type | Method | Description |
---|---|---|
int |
characteristics() |
Returns a set of characteristics of this Spliterator and its elements. |
long |
estimateSize() |
Returns an estimate of the number of elements that would be encountered by a forEachRemaining(java.util.function.Consumer<? super T>) traversal, or returns Long.MAX_VALUE if infinite, unknown, or too expensive to compute. |
default void |
forEachRemaining |
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 |
getComparator() |
|
default long |
getExactSizeIfKnown() |
|
default boolean |
hasCharacteristics |
Returns true if this Spliterator's characteristics() contain all of the given characteristics. |
boolean |
tryAdvance |
If a remaining element exists: performs the given action on it, returning true ; else returns false . |
Spliterator |
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. |
static final int ORDERED
trySplit()
splits a strict prefix of elements, that method tryAdvance(java.util.function.Consumer<? super T>)
steps by one element in prefix order, and that forEachRemaining(java.util.function.Consumer<? super T>)
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.
static final int DISTINCT
x, y
, !x.equals(y)
. This applies for example, to a Spliterator based on a Set
.static final int SORTED
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
.
Collection
classes in the JDK that implement NavigableSet
or SortedSet
report SORTED
.static final int SIZED
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.Collection
report this characteristic. Sub-spliterators, such as those for HashSet
, that cover a sub-set of elements and approximate their reported size do not.static final int NONNULL
null
. (This applies, for example, to most concurrent collections, queues, and maps.)static final int IMMUTABLE
IMMUTABLE
or CONCURRENT
is expected to have a documented policy (for example throwing ConcurrentModificationException
) concerning structural interference detected during traversal.static final int CONCURRENT
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.
static final int SUBSIZED
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.
SIZED
but not SUBSIZED
, since it is common to know the size of the entire tree but not the exact sizes of subtrees.boolean tryAdvance(Consumer<? super T> action)
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.
action
- The action whose operation is performed at-most oncefalse
if no remaining elements existed upon entry to this method, else true
.NullPointerException
- if the specified action is nulldefault void forEachRemaining(Consumer<? super T> action)
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.
tryAdvance(java.util.function.Consumer<? super T>)
until it returns false
. It should be overridden whenever possible.action
- The actionNullPointerException
- if the specified action is nullSpliterator<T> trySplit()
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:
estimateSize()
before splitting, must, after splitting, be greater than or equal to estimateSize()
for this and the returned Spliterator; andSUBSIZED
, then estimateSize()
for this spliterator before splitting must be equal to the sum of estimateSize()
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.
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 inefficient
trySplit
mechanics typically result in poor parallel performance.Spliterator
covering some portion of the elements, or null
if this spliterator cannot be splitlong estimateSize()
forEachRemaining(java.util.function.Consumer<? super T>)
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()
.
Long.MAX_VALUE
if infinite, unknown, or too expensive to compute.default long getExactSizeIfKnown()
estimateSize()
if the Spliterator reports a characteristic of SIZED
, and -1
otherwise.-1
.int characteristics()
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.
SIZED
, SUBSIZED
and CONCURRENT
.default boolean hasCharacteristics(int characteristics)
true
if this Spliterator's characteristics()
contain all of the given characteristics.characteristics
- the characteristics to check fortrue
if all the specified characteristics are present, else false
default Comparator<? super T> getComparator()
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
.IllegalStateException
.null
if the elements are sorted in the natural order.IllegalStateException
- if the spliterator does not report a characteristic of SORTED
.
© 1993, 2023, Oracle and/or its affiliates. All rights reserved.
Documentation extracted from Debian's OpenJDK Development Kit package.
Licensed under the GNU General Public License, version 2, with the Classpath Exception.
Various third party code in OpenJDK is licensed under different licenses (see Debian package).
Java and OpenJDK are trademarks or registered trademarks of Oracle and/or its affiliates.
https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Spliterator.html