Interface Spliterator<T>

Type Parameters:

T - the type of elements returned by this Spliterator

All Known Subinterfaces:

Spliterator.OfDouble, Spliterator.OfInt, Spliterator.OfLong, Spliterator.OfPrimitive<T,T_CONS,T_SPLITR>

All Known Implementing Classes:

Spliterators.AbstractDoubleSpliterator, Spliterators.AbstractIntSpliterator, Spliterators.AbstractLongSpliterator, Spliterators.AbstractSpliterator

public interface Spliterator<T>

API Note:

Spliterators, like Iterators, 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):

• The source cannot be structurally interfered with.
  For example, an instance of CopyOnWriteArrayList is an immutable source. A Spliterator created from the source reports a characteristic of IMMUTABLE.
• The source manages concurrent modifications.
  For example, a key set of a ConcurrentHashMap is a concurrent source. A Spliterator created from the source reports a characteristic of CONCURRENT.
• The mutable source provides a late-binding and fail-fast Spliterator.
  Late binding narrows the window during which interference can affect the calculation; fail-fast detects, on a best-effort basis, that structural interference has occurred after traversal has commenced and throws ConcurrentModificationException. For example, ArrayList, and many other non-concurrent Collection classes in the JDK, provide a late-binding, fail-fast spliterator.
• The mutable source provides a non-late-binding but fail-fast Spliterator.
  The source increases the likelihood of throwing ConcurrentModificationException since the window of potential interference is larger.
• The mutable source provides a late-binding and non-fail-fast Spliterator.
  The source risks arbitrary, non-deterministic behavior after traversal has commenced since interference is not detected.
• The mutable source provides a non-late-binding and non-fail-fast Spliterator.
  The source increases the risk of arbitrary, non-deterministic behavior since non-detected interference may occur after construction.

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();
   }
 }

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.

Since:

1.8

See Also:

Collection

Nested Classes

Nested Classes

Modifier and Type	Interface and 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,T_CONS,T_SPLITR extends Spliterator.OfPrimitive<T,T_CONS,T_SPLITR>> A Spliterator specialized for primitive values.

Fields

ORDERED

static final int ORDERED

API Note:

Encounter order is guaranteed to be ascending index order for any List. But no order is guaranteed for hash-based collections such as HashSet. Clients of a Spliterator that reports ORDERED are expected to preserve ordering constraints in non-commutative parallel computations.

DISTINCT

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.

SORTED

static final int SORTED

API Note:

The spliterators for Collection classes in the JDK that implement NavigableSet or SortedSet report SORTED.

SIZED

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.

API Note:

Most Spliterators for Collections, that cover all elements of a 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.

NONNULL

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.)

IMMUTABLE

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.

CONCURRENT

static final int CONCURRENT

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.

SUBSIZED

static final int SUBSIZED

API Note:

Some spliterators, such as the top-level spliterator for an approximately balanced binary tree, will report SIZED but not SUBSIZED, since it is common to know the size of the entire tree but not the exact sizes of subtrees.

Methods

tryAdvance

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.

Parameters:

action - The action

Returns:

false if no remaining elements existed upon entry to this method, else true.

Throws:

NullPointerException - if the specified action is null

forEachRemaining

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 ORDERED, actions are performed in encounter order. Exceptions thrown by the action are relayed to the caller.

Implementation Requirements:

The default implementation repeatedly invokes tryAdvance(java.util.function.Consumer<? super T>) until it returns false. It should be overridden whenever possible.

Parameters:

action - The action

Throws:

NullPointerException - if the specified action is null

trySplit

Spliterator<T> trySplit()

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 inefficient trySplit mechanics typically result in poor parallel performance.

Returns:

a Spliterator covering some portion of the elements, or null if this spliterator cannot be split

estimateSize

long estimateSize()

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:

the estimated size, or Long.MAX_VALUE if infinite, unknown, or too expensive to compute.

getExactSizeIfKnown

default 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 of SIZED, and -1 otherwise.

Returns:

the exact size, if known, else -1.

characteristics

int characteristics()

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 and CONCURRENT.

Returns:

a representation of characteristics

hasCharacteristics

default 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 - the characteristics to check for

Returns:

true if all the specified characteristics are present, else false

getComparator

default 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:

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.