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 interfaceSpliterator<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, aCollection, 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 (usingtrySplit()) 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 ofcharacteristics() of its structure, source, and elements from amongORDERED,DISTINCT,SORTED,SIZED,NONNULL,IMMUTABLE,CONCURRENT, andSUBSIZED. These may be employed by Spliterator clients to control, specialize or simplify computation. For example, a Spliterator for aCollection would reportSIZED, a Spliterator for aSet would reportDISTINCT, and a Spliterator for aSortedSet would also reportSORTED. Characteristics are reported as a simple unioned bit set. Some characteristics additionally constrain method behavior; for example ifORDERED, 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 reportIMMUTABLE orCONCURRENT is expected to have a documented policy concerning: when the spliteratorbinds to the element source; and detection of structural interference of the element source detected after binding. Alate-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 notlate-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, throwConcurrentModificationException if structural interference is detected. Spliterators that do this are calledfail-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 theestimateSize() method. Ideally, as reflected in characteristicSIZED, 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 viaserial thread-confinement, which often is a natural consequence of typical parallel algorithms that work by recursive decomposition. A thread callingtrySplit() 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 withtryAdvance(), as certain guarantees (such as the accuracy ofestimateSize() forSIZED spliterators) are only valid before traversal has begun.

Primitive subtype specializations ofSpliterator are provided forint,long, anddouble values. The subtype default implementations oftryAdvance(java.util.function.Consumer) andforEachRemaining(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) andSpliterator.OfPrimitive.forEachRemaining(java.util.function.IntConsumer) should be used in preference toSpliterator.OfInt.tryAdvance(java.util.function.Consumer) andSpliterator.OfInt.forEachRemaining(java.util.function.Consumer). Traversal of primitive values using boxing-based methodstryAdvance() andforEachRemaining() does not affect the order in which the values, transformed to boxed values, are encountered.

API Note:

Spliterators, likeIterators, are for traversing the elements of a source. TheSpliterator 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 thanIterator, and to avoid the inherent race involved in having separate methods forhasNext() andnext().

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 thejava.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 ofCopyOnWriteArrayList is an immutable source. A Spliterator created from the source reports a characteristic ofIMMUTABLE.
  • The source manages concurrent modifications.
    For example, a key set of aConcurrentHashMap is a concurrent source. A Spliterator created from the source reports a characteristic ofCONCURRENT.
  • 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 throwsConcurrentModificationException. For example,ArrayList, and many other non-concurrentCollection 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 throwingConcurrentModificationException 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 thejava.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 aCountedCompleter; 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 propertyorg.openjdk.java.util.stream.tripwire is set totrue then diagnostic warnings are reported if boxing of primitive values occur when operating on primitive subtype specializations.
Since:
1.8
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static interface 
    A Spliterator specialized fordouble values.
    static interface 
    A Spliterator specialized forint values.
    static interface 
    A Spliterator specialized forlong values.
    static interface 
    A Spliterator specialized for primitive values.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    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
    Characteristic value signifying that, for each pair of encountered elementsx, y,!x.equals(y).
    static final int
    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
    Characteristic value signifying that the source guarantees that encountered elements will not benull.
    static final int
    Characteristic value signifying that an encounter order is defined for elements.
    static final int
    Characteristic value signifying that the value returned fromestimateSize() 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
    Characteristic value signifying that encounter order follows a defined sort order.
    static final int
    Characteristic value signifying that all Spliterators resulting fromtrySplit() will be bothSIZED andSUBSIZED.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    Returns a set of characteristics of this Spliterator and its elements.
    long
    Returns an estimate of the number of elements that would be encountered by aforEachRemaining(java.util.function.Consumer<? super T>) traversal, or returnsLong.MAX_VALUE if infinite, unknown, or too expensive to compute.
    default void
    forEachRemaining(Consumer<? superT> 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.
    defaultComparator<? superT>
    If this Spliterator's source isSORTED by aComparator, returns thatComparator.
    default long
    Convenience method that returnsestimateSize() if this Spliterator isSIZED, else-1.
    default boolean
    hasCharacteristics(int characteristics)
    Returnstrue if this Spliterator'scharacteristics() contain all of the given characteristics.
    boolean
    tryAdvance(Consumer<? superT> action)
    If a remaining element exists: performs the given action on it, returningtrue; else returnsfalse.
    If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

  • Field Details

    • ORDERED

      static final int ORDERED
      Characteristic value signifying that an encounter order is defined for elements. If so, this Spliterator guarantees that methodtrySplit() splits a strict prefix of elements, that methodtryAdvance(java.util.function.Consumer<? super T>) steps by one element in prefix order, and thatforEachRemaining(java.util.function.Consumer<? super T>) performs actions in encounter order.

      ACollection has an encounter order if the correspondingCollection.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.

      API Note:
      Encounter order is guaranteed to be ascending index order for anyList. But no order is guaranteed for hash-based collections such asHashSet. Clients of a Spliterator that reportsORDERED are expected to preserve ordering constraints in non-commutative parallel computations.
      See Also:

    • DISTINCT

      static final int DISTINCT
      Characteristic value signifying that, for each pair of encountered elementsx, y,!x.equals(y). This applies for example, to a Spliterator based on aSet.
      See Also:

    • SORTED

      static final int SORTED
      Characteristic value signifying that encounter order follows a defined sort order. If so, methodgetComparator() returns the associated Comparator, ornull if all elements areComparable and are sorted by their natural ordering.

      A Spliterator that reportsSORTED must also reportORDERED.

      API Note:
      The spliterators forCollection classes in the JDK that implementNavigableSet orSortedSet reportSORTED.
      See Also:

    • SIZED

      static final int SIZED
      Characteristic value signifying that the value returned fromestimateSize() 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 aCollection report this characteristic. Sub-spliterators, such as those forHashSet, that cover a sub-set of elements and approximate their reported size do not.
      See Also:

    • NONNULL

      static final int NONNULL
      Characteristic value signifying that the source guarantees that encountered elements will not benull. (This applies, for example, to most concurrent collections, queues, and maps.)
      See Also:

    • 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 reportIMMUTABLE orCONCURRENT is expected to have a documented policy (for example throwingConcurrentModificationException) concerning structural interference detected during traversal.
      See Also:

    • CONCURRENT

      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 bothCONCURRENT andSIZED, 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 reportSIZED 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 bothCONCURRENT andIMMUTABLE, 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 reportIMMUTABLE if additions or removals to the source are not reflected when traversing.

      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.
      See Also:

    • SUBSIZED

      static final int SUBSIZED
      Characteristic value signifying that all Spliterators resulting fromtrySplit() will be bothSIZED andSUBSIZED. (This means that all child Spliterators, whether direct or indirect, will beSIZED.)

      A Spliterator that does not reportSIZED as required bySUBSIZED is inconsistent and no guarantees can be made about any computation using that Spliterator.

      API Note:
      Some spliterators, such as the top-level spliterator for an approximately balanced binary tree, will reportSIZED but notSUBSIZED, since it is common to know the size of the entire tree but not the exact sizes of subtrees.
      See Also:

  • Method Details

    • tryAdvance

      boolean tryAdvance(Consumer<? superT> action)
      If a remaining element exists: performs the given action on it, returningtrue; else returnsfalse. If this Spliterator isORDERED 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 - The action whose operation is performed at-most once
      Returns:
      false if no remaining elements existed upon entry to this method, elsetrue.
      Throws:
      NullPointerException - if the specified action is null

    • forEachRemaining

      default void forEachRemaining(Consumer<? superT> 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 isORDERED, 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 invokestryAdvance(java.util.function.Consumer<? super T>) until it returnsfalse. It should be overridden whenever possible.
      Parameters:
      action - The action
      Throws:
      NullPointerException - if the specified action is null

    • trySplit

      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 isORDERED, the returned Spliterator must cover a strict prefix of the elements.

      Unless this Spliterator covers an infinite number of elements, repeated calls totrySplit() must eventually returnnull. Upon non-null return:

      • the value reported forestimateSize() before splitting, must, after splitting, be greater than or equal toestimateSize() for this and the returned Spliterator; and
      • if this Spliterator isSUBSIZED, thenestimateSize() for this spliterator before splitting must be equal to the sum ofestimateSize() for this and the returned Spliterator after splitting.

      This method may returnnull for any reason, including emptiness, inability to split after traversal has commenced, data structure constraints, and efficiency considerations.

      API Note:
      An idealtrySplit 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:
      aSpliterator covering some portion of the elements, ornull if this spliterator cannot be split

    • estimateSize

      long estimateSize()
      Returns an estimate of the number of elements that would be encountered by aforEachRemaining(java.util.function.Consumer<? super T>) traversal, or returnsLong.MAX_VALUE if infinite, unknown, or too expensive to compute.

      If this Spliterator isSIZED and has not yet been partially traversed or split, or this Spliterator isSUBSIZED 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 oftrySplit().

      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, orLong.MAX_VALUE if infinite, unknown, or too expensive to compute.

    • getExactSizeIfKnown

      default long getExactSizeIfKnown()
      Convenience method that returnsestimateSize() if this Spliterator isSIZED, else-1.
      Implementation Requirements:
      The default implementation returns the result ofestimateSize() if the Spliterator reports a characteristic ofSIZED, and-1 otherwise.
      Returns:
      the exact size, if known, else-1.

    • characteristics

      int characteristics()
      Returns a set of characteristics of this Spliterator and its elements. The result is represented as ORed values fromORDERED,DISTINCT,SORTED,SIZED,NONNULL,IMMUTABLE,CONCURRENT,SUBSIZED. Repeated calls tocharacteristics() on a given spliterator, prior to or in-between calls totrySplit, 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 valuesSIZED,SUBSIZED andCONCURRENT.
      Returns:
      a representation of characteristics

    • hasCharacteristics

      default boolean hasCharacteristics(int characteristics)
      Returnstrue if this Spliterator'scharacteristics() 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, elsefalse

    • getComparator

      default Comparator<? superT> getComparator()
      If this Spliterator's source isSORTED by aComparator, returns thatComparator. If the source isSORTED innatural order, returnsnull. Otherwise, if the source is notSORTED, throwsIllegalStateException.
      Implementation Requirements:
      The default implementation always throwsIllegalStateException.
      Returns:
      a Comparator, ornull if the elements are sorted in the natural order.
      Throws:
      IllegalStateException - if the spliterator does not report a characteristic ofSORTED.