View Javadoc
1   /*
2    * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  package java.util;
26  
27  import java.util.function.Consumer;
28  import java.util.function.DoubleConsumer;
29  import java.util.function.IntConsumer;
30  import java.util.function.LongConsumer;
31  
32  /**
33   * An object for traversing and partitioning elements of a source.  The source
34   * of elements covered by a Spliterator could be, for example, an array, a
35   * {@link Collection}, an IO channel, or a generator function.
36   *
37   * <p>A Spliterator may traverse elements individually ({@link
38   * #tryAdvance tryAdvance()}) or sequentially in bulk
39   * ({@link #forEachRemaining forEachRemaining()}).
40   *
41   * <p>A Spliterator may also partition off some of its elements (using
42   * {@link #trySplit}) as another Spliterator, to be used in
43   * possibly-parallel operations.  Operations using a Spliterator that
44   * cannot split, or does so in a highly imbalanced or inefficient
45   * manner, are unlikely to benefit from parallelism.  Traversal
46   * and splitting exhaust elements; each Spliterator is useful for only a single
47   * bulk computation.
48   *
49   * <p>A Spliterator also reports a set of {@link #characteristics()} of its
50   * structure, source, and elements from among {@link #ORDERED},
51   * {@link #DISTINCT}, {@link #SORTED}, {@link #SIZED}, {@link #NONNULL},
52   * {@link #IMMUTABLE}, {@link #CONCURRENT}, and {@link #SUBSIZED}. These may
53   * be employed by Spliterator clients to control, specialize or simplify
54   * computation.  For example, a Spliterator for a {@link Collection} would
55   * report {@code SIZED}, a Spliterator for a {@link Set} would report
56   * {@code DISTINCT}, and a Spliterator for a {@link SortedSet} would also
57   * report {@code SORTED}.  Characteristics are reported as a simple unioned bit
58   * set.
59   *
60   * Some characteristics additionally constrain method behavior; for example if
61   * {@code ORDERED}, traversal methods must conform to their documented ordering.
62   * New characteristics may be defined in the future, so implementors should not
63   * assign meanings to unlisted values.
64   *
65   * <p><a name="binding">A Spliterator that does not report {@code IMMUTABLE} or
66   * {@code CONCURRENT} is expected to have a documented policy concerning:
67   * when the spliterator <em>binds</em> to the element source; and detection of
68   * structural interference of the element source detected after binding.</a>  A
69   * <em>late-binding</em> Spliterator binds to the source of elements at the
70   * point of first traversal, first split, or first query for estimated size,
71   * rather than at the time the Spliterator is created.  A Spliterator that is
72   * not <em>late-binding</em> binds to the source of elements at the point of
73   * construction or first invocation of any method.  Modifications made to the
74   * source prior to binding are reflected when the Spliterator is traversed.
75   * After binding a Spliterator should, on a best-effort basis, throw
76   * {@link ConcurrentModificationException} if structural interference is
77   * detected.  Spliterators that do this are called <em>fail-fast</em>.  The
78   * bulk traversal method ({@link #forEachRemaining forEachRemaining()}) of a
79   * Spliterator may optimize traversal and check for structural interference
80   * after all elements have been traversed, rather than checking per-element and
81   * failing immediately.
82   *
83   * <p>Spliterators can provide an estimate of the number of remaining elements
84   * via the {@link #estimateSize} method.  Ideally, as reflected in characteristic
85   * {@link #SIZED}, this value corresponds exactly to the number of elements
86   * that would be encountered in a successful traversal.  However, even when not
87   * exactly known, an estimated value value may still be useful to operations
88   * being performed on the source, such as helping to determine whether it is
89   * preferable to split further or traverse the remaining elements sequentially.
90   *
91   * <p>Despite their obvious utility in parallel algorithms, spliterators are not
92   * expected to be thread-safe; instead, implementations of parallel algorithms
93   * using spliterators should ensure that the spliterator is only used by one
94   * thread at a time.  This is generally easy to attain via <em>serial
95   * thread-confinement</em>, which often is a natural consequence of typical
96   * parallel algorithms that work by recursive decomposition.  A thread calling
97   * {@link #trySplit()} may hand over the returned Spliterator to another thread,
98   * which in turn may traverse or further split that Spliterator.  The behaviour
99   * of splitting and traversal is undefined if two or more threads operate
100  * concurrently on the same spliterator.  If the original thread hands a
101  * spliterator off to another thread for processing, it is best if that handoff
102  * occurs before any elements are consumed with {@link #tryAdvance(Consumer)
103  * tryAdvance()}, as certain guarantees (such as the accuracy of
104  * {@link #estimateSize()} for {@code SIZED} spliterators) are only valid before
105  * traversal has begun.
106  *
107  * <p>Primitive subtype specializations of {@code Spliterator} are provided for
108  * {@link OfInt int}, {@link OfLong long}, and {@link OfDouble double} values.
109  * The subtype default implementations of
110  * {@link Spliterator#tryAdvance(java.util.function.Consumer)}
111  * and {@link Spliterator#forEachRemaining(java.util.function.Consumer)} box
112  * primitive values to instances of their corresponding wrapper class.  Such
113  * boxing may undermine any performance advantages gained by using the primitive
114  * specializations.  To avoid boxing, the corresponding primitive-based methods
115  * should be used.  For example,
116  * {@link Spliterator.OfInt#tryAdvance(java.util.function.IntConsumer)}
117  * and {@link Spliterator.OfInt#forEachRemaining(java.util.function.IntConsumer)}
118  * should be used in preference to
119  * {@link Spliterator.OfInt#tryAdvance(java.util.function.Consumer)} and
120  * {@link Spliterator.OfInt#forEachRemaining(java.util.function.Consumer)}.
121  * Traversal of primitive values using boxing-based methods
122  * {@link #tryAdvance tryAdvance()} and
123  * {@link #forEachRemaining(java.util.function.Consumer) forEachRemaining()}
124  * does not affect the order in which the values, transformed to boxed values,
125  * are encountered.
126  *
127  * @apiNote
128  * <p>Spliterators, like {@code Iterators}s, are for traversing the elements of
129  * a source.  The {@code Spliterator} API was designed to support efficient
130  * parallel traversal in addition to sequential traversal, by supporting
131  * decomposition as well as single-element iteration.  In addition, the
132  * protocol for accessing elements via a Spliterator is designed to impose
133  * smaller per-element overhead than {@code Iterator}, and to avoid the inherent
134  * race involved in having separate methods for {@code hasNext()} and
135  * {@code next()}.
136  *
137  * <p>For mutable sources, arbitrary and non-deterministic behavior may occur if
138  * the source is structurally interfered with (elements added, replaced, or
139  * removed) between the time that the Spliterator binds to its data source and
140  * the end of traversal.  For example, such interference will produce arbitrary,
141  * non-deterministic results when using the {@code java.util.stream} framework.
142  *
143  * <p>Structural interference of a source can be managed in the following ways
144  * (in approximate order of decreasing desirability):
145  * <ul>
146  * <li>The source cannot be structurally interfered with.
147  * <br>For example, an instance of
148  * {@link java.util.concurrent.CopyOnWriteArrayList} is an immutable source.
149  * A Spliterator created from the source reports a characteristic of
150  * {@code IMMUTABLE}.</li>
151  * <li>The source manages concurrent modifications.
152  * <br>For example, a key set of a {@link java.util.concurrent.ConcurrentHashMap}
153  * is a concurrent source.  A Spliterator created from the source reports a
154  * characteristic of {@code CONCURRENT}.</li>
155  * <li>The mutable source provides a late-binding and fail-fast Spliterator.
156  * <br>Late binding narrows the window during which interference can affect
157  * the calculation; fail-fast detects, on a best-effort basis, that structural
158  * interference has occurred after traversal has commenced and throws
159  * {@link ConcurrentModificationException}.  For example, {@link ArrayList},
160  * and many other non-concurrent {@code Collection} classes in the JDK, provide
161  * a late-binding, fail-fast spliterator.</li>
162  * <li>The mutable source provides a non-late-binding but fail-fast Spliterator.
163  * <br>The source increases the likelihood of throwing
164  * {@code ConcurrentModificationException} since the window of potential
165  * interference is larger.</li>
166  * <li>The mutable source provides a late-binding and non-fail-fast Spliterator.
167  * <br>The source risks arbitrary, non-deterministic behavior after traversal
168  * has commenced since interference is not detected.
169  * </li>
170  * <li>The mutable source provides a non-late-binding and non-fail-fast
171  * Spliterator.
172  * <br>The source increases the risk of arbitrary, non-deterministic behavior
173  * since non-detected interference may occur after construction.
174  * </li>
175  * </ul>
176  *
177  * <p><b>Example.</b> Here is a class (not a very useful one, except
178  * for illustration) that maintains an array in which the actual data
179  * are held in even locations, and unrelated tag data are held in odd
180  * locations. Its Spliterator ignores the tags.
181  *
182  * <pre> {@code
183  * class TaggedArray<T> {
184  *   private final Object[] elements; // immutable after construction
185  *   TaggedArray(T[] data, Object[] tags) {
186  *     int size = data.length;
187  *     if (tags.length != size) throw new IllegalArgumentException();
188  *     this.elements = new Object[2 * size];
189  *     for (int i = 0, j = 0; i < size; ++i) {
190  *       elements[j++] = data[i];
191  *       elements[j++] = tags[i];
192  *     }
193  *   }
194  *
195  *   public Spliterator<T> spliterator() {
196  *     return new TaggedArraySpliterator<>(elements, 0, elements.length);
197  *   }
198  *
199  *   static class TaggedArraySpliterator<T> implements Spliterator<T> {
200  *     private final Object[] array;
201  *     private int origin; // current index, advanced on split or traversal
202  *     private final int fence; // one past the greatest index
203  *
204  *     TaggedArraySpliterator(Object[] array, int origin, int fence) {
205  *       this.array = array; this.origin = origin; this.fence = fence;
206  *     }
207  *
208  *     public void forEachRemaining(Consumer<? super T> action) {
209  *       for (; origin < fence; origin += 2)
210  *         action.accept((T) array[origin]);
211  *     }
212  *
213  *     public boolean tryAdvance(Consumer<? super T> action) {
214  *       if (origin < fence) {
215  *         action.accept((T) array[origin]);
216  *         origin += 2;
217  *         return true;
218  *       }
219  *       else // cannot advance
220  *         return false;
221  *     }
222  *
223  *     public Spliterator<T> trySplit() {
224  *       int lo = origin; // divide range in half
225  *       int mid = ((lo + fence) >>> 1) & ~1; // force midpoint to be even
226  *       if (lo < mid) { // split out left half
227  *         origin = mid; // reset this Spliterator's origin
228  *         return new TaggedArraySpliterator<>(array, lo, mid);
229  *       }
230  *       else       // too small to split
231  *         return null;
232  *     }
233  *
234  *     public long estimateSize() {
235  *       return (long)((fence - origin) / 2);
236  *     }
237  *
238  *     public int characteristics() {
239  *       return ORDERED | SIZED | IMMUTABLE | SUBSIZED;
240  *     }
241  *   }
242  * }}</pre>
243  *
244  * <p>As an example how a parallel computation framework, such as the
245  * {@code java.util.stream} package, would use Spliterator in a parallel
246  * computation, here is one way to implement an associated parallel forEach,
247  * that illustrates the primary usage idiom of splitting off subtasks until
248  * the estimated amount of work is small enough to perform
249  * sequentially. Here we assume that the order of processing across
250  * subtasks doesn't matter; different (forked) tasks may further split
251  * and process elements concurrently in undetermined order.  This
252  * example uses a {@link java.util.concurrent.CountedCompleter};
253  * similar usages apply to other parallel task constructions.
254  *
255  * <pre>{@code
256  * static <T> void parEach(TaggedArray<T> a, Consumer<T> action) {
257  *   Spliterator<T> s = a.spliterator();
258  *   long targetBatchSize = s.estimateSize() / (ForkJoinPool.getCommonPoolParallelism() * 8);
259  *   new ParEach(null, s, action, targetBatchSize).invoke();
260  * }
261  *
262  * static class ParEach<T> extends CountedCompleter<Void> {
263  *   final Spliterator<T> spliterator;
264  *   final Consumer<T> action;
265  *   final long targetBatchSize;
266  *
267  *   ParEach(ParEach<T> parent, Spliterator<T> spliterator,
268  *           Consumer<T> action, long targetBatchSize) {
269  *     super(parent);
270  *     this.spliterator = spliterator; this.action = action;
271  *     this.targetBatchSize = targetBatchSize;
272  *   }
273  *
274  *   public void compute() {
275  *     Spliterator<T> sub;
276  *     while (spliterator.estimateSize() > targetBatchSize &&
277  *            (sub = spliterator.trySplit()) != null) {
278  *       addToPendingCount(1);
279  *       new ParEach<>(this, sub, action, targetBatchSize).fork();
280  *     }
281  *     spliterator.forEachRemaining(action);
282  *     propagateCompletion();
283  *   }
284  * }}</pre>
285  *
286  * @implNote
287  * If the boolean system property {@code org.openjdk.java.util.stream.tripwire}
288  * is set to {@code true} then diagnostic warnings are reported if boxing of
289  * primitive values occur when operating on primitive subtype specializations.
290  *
291  * @param <T> the type of elements returned by this Spliterator
292  *
293  * @see Collection
294  * @since 1.8
295  */
296 public interface Spliterator<T> {
297     /**
298      * If a remaining element exists, performs the given action on it,
299      * returning {@code true}; else returns {@code false}.  If this
300      * Spliterator is {@link #ORDERED} the action is performed on the
301      * next element in encounter order.  Exceptions thrown by the
302      * action are relayed to the caller.
303      *
304      * @param action The action
305      * @return {@code false} if no remaining elements existed
306      * upon entry to this method, else {@code true}.
307      * @throws NullPointerException if the specified action is null
308      */
309     boolean tryAdvance(Consumer<? super T> action);
310 
311     /**
312      * Performs the given action for each remaining element, sequentially in
313      * the current thread, until all elements have been processed or the action
314      * throws an exception.  If this Spliterator is {@link #ORDERED}, actions
315      * are performed in encounter order.  Exceptions thrown by the action
316      * are relayed to the caller.
317      *
318      * @implSpec
319      * The default implementation repeatedly invokes {@link #tryAdvance} until
320      * it returns {@code false}.  It should be overridden whenever possible.
321      *
322      * @param action The action
323      * @throws NullPointerException if the specified action is null
324      */
325     default void forEachRemaining(Consumer<? super T> action) {
326         do { } while (tryAdvance(action));
327     }
328 
329     /**
330      * If this spliterator can be partitioned, returns a Spliterator
331      * covering elements, that will, upon return from this method, not
332      * be covered by this Spliterator.
333      *
334      * <p>If this Spliterator is {@link #ORDERED}, the returned Spliterator
335      * must cover a strict prefix of the elements.
336      *
337      * <p>Unless this Spliterator covers an infinite number of elements,
338      * repeated calls to {@code trySplit()} must eventually return {@code null}.
339      * Upon non-null return:
340      * <ul>
341      * <li>the value reported for {@code estimateSize()} before splitting,
342      * must, after splitting, be greater than or equal to {@code estimateSize()}
343      * for this and the returned Spliterator; and</li>
344      * <li>if this Spliterator is {@code SUBSIZED}, then {@code estimateSize()}
345      * for this spliterator before splitting must be equal to the sum of
346      * {@code estimateSize()} for this and the returned Spliterator after
347      * splitting.</li>
348      * </ul>
349      *
350      * <p>This method may return {@code null} for any reason,
351      * including emptiness, inability to split after traversal has
352      * commenced, data structure constraints, and efficiency
353      * considerations.
354      *
355      * @apiNote
356      * An ideal {@code trySplit} method efficiently (without
357      * traversal) divides its elements exactly in half, allowing
358      * balanced parallel computation.  Many departures from this ideal
359      * remain highly effective; for example, only approximately
360      * splitting an approximately balanced tree, or for a tree in
361      * which leaf nodes may contain either one or two elements,
362      * failing to further split these nodes.  However, large
363      * deviations in balance and/or overly inefficient {@code
364      * trySplit} mechanics typically result in poor parallel
365      * performance.
366      *
367      * @return a {@code Spliterator} covering some portion of the
368      * elements, or {@code null} if this spliterator cannot be split
369      */
370     Spliterator<T> trySplit();
371 
372     /**
373      * Returns an estimate of the number of elements that would be
374      * encountered by a {@link #forEachRemaining} traversal, or returns {@link
375      * Long#MAX_VALUE} if infinite, unknown, or too expensive to compute.
376      *
377      * <p>If this Spliterator is {@link #SIZED} and has not yet been partially
378      * traversed or split, or this Spliterator is {@link #SUBSIZED} and has
379      * not yet been partially traversed, this estimate must be an accurate
380      * count of elements that would be encountered by a complete traversal.
381      * Otherwise, this estimate may be arbitrarily inaccurate, but must decrease
382      * as specified across invocations of {@link #trySplit}.
383      *
384      * @apiNote
385      * Even an inexact estimate is often useful and inexpensive to compute.
386      * For example, a sub-spliterator of an approximately balanced binary tree
387      * may return a value that estimates the number of elements to be half of
388      * that of its parent; if the root Spliterator does not maintain an
389      * accurate count, it could estimate size to be the power of two
390      * corresponding to its maximum depth.
391      *
392      * @return the estimated size, or {@code Long.MAX_VALUE} if infinite,
393      *         unknown, or too expensive to compute.
394      */
395     long estimateSize();
396 
397     /**
398      * Convenience method that returns {@link #estimateSize()} if this
399      * Spliterator is {@link #SIZED}, else {@code -1}.
400      * @implSpec
401      * The default implementation returns the result of {@code estimateSize()}
402      * if the Spliterator reports a characteristic of {@code SIZED}, and
403      * {@code -1} otherwise.
404      *
405      * @return the exact size, if known, else {@code -1}.
406      */
407     default long getExactSizeIfKnown() {
408         return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
409     }
410 
411     /**
412      * Returns a set of characteristics of this Spliterator and its
413      * elements. The result is represented as ORed values from {@link
414      * #ORDERED}, {@link #DISTINCT}, {@link #SORTED}, {@link #SIZED},
415      * {@link #NONNULL}, {@link #IMMUTABLE}, {@link #CONCURRENT},
416      * {@link #SUBSIZED}.  Repeated calls to {@code characteristics()} on
417      * a given spliterator, prior to or in-between calls to {@code trySplit},
418      * should always return the same result.
419      *
420      * <p>If a Spliterator reports an inconsistent set of
421      * characteristics (either those returned from a single invocation
422      * or across multiple invocations), no guarantees can be made
423      * about any computation using this Spliterator.
424      *
425      * @apiNote The characteristics of a given spliterator before splitting
426      * may differ from the characteristics after splitting.  For specific
427      * examples see the characteristic values {@link #SIZED}, {@link #SUBSIZED}
428      * and {@link #CONCURRENT}.
429      *
430      * @return a representation of characteristics
431      */
432     int characteristics();
433 
434     /**
435      * Returns {@code true} if this Spliterator's {@link
436      * #characteristics} contain all of the given characteristics.
437      *
438      * @implSpec
439      * The default implementation returns true if the corresponding bits
440      * of the given characteristics are set.
441      *
442      * @param characteristics the characteristics to check for
443      * @return {@code true} if all the specified characteristics are present,
444      * else {@code false}
445      */
446     default boolean hasCharacteristics(int characteristics) {
447         return (characteristics() & characteristics) == characteristics;
448     }
449 
450     /**
451      * If this Spliterator's source is {@link #SORTED} by a {@link Comparator},
452      * returns that {@code Comparator}. If the source is {@code SORTED} in
453      * {@linkplain Comparable natural order}, returns {@code null}.  Otherwise,
454      * if the source is not {@code SORTED}, throws {@link IllegalStateException}.
455      *
456      * @implSpec
457      * The default implementation always throws {@link IllegalStateException}.
458      *
459      * @return a Comparator, or {@code null} if the elements are sorted in the
460      * natural order.
461      * @throws IllegalStateException if the spliterator does not report
462      *         a characteristic of {@code SORTED}.
463      */
464     default Comparator<? super T> getComparator() {
465         throw new IllegalStateException();
466     }
467 
468     /**
469      * Characteristic value signifying that an encounter order is defined for
470      * elements. If so, this Spliterator guarantees that method
471      * {@link #trySplit} splits a strict prefix of elements, that method
472      * {@link #tryAdvance} steps by one element in prefix order, and that
473      * {@link #forEachRemaining} performs actions in encounter order.
474      *
475      * <p>A {@link Collection} has an encounter order if the corresponding
476      * {@link Collection#iterator} documents an order. If so, the encounter
477      * order is the same as the documented order. Otherwise, a collection does
478      * not have an encounter order.
479      *
480      * @apiNote Encounter order is guaranteed to be ascending index order for
481      * any {@link List}. But no order is guaranteed for hash-based collections
482      * such as {@link HashSet}. Clients of a Spliterator that reports
483      * {@code ORDERED} are expected to preserve ordering constraints in
484      * non-commutative parallel computations.
485      */
486     public static final int ORDERED    = 0x00000010;
487 
488     /**
489      * Characteristic value signifying that, for each pair of
490      * encountered elements {@code x, y}, {@code !x.equals(y)}. This
491      * applies for example, to a Spliterator based on a {@link Set}.
492      */
493     public static final int DISTINCT   = 0x00000001;
494 
495     /**
496      * Characteristic value signifying that encounter order follows a defined
497      * sort order. If so, method {@link #getComparator()} returns the associated
498      * Comparator, or {@code null} if all elements are {@link Comparable} and
499      * are sorted by their natural ordering.
500      *
501      * <p>A Spliterator that reports {@code SORTED} must also report
502      * {@code ORDERED}.
503      *
504      * @apiNote The spliterators for {@code Collection} classes in the JDK that
505      * implement {@link NavigableSet} or {@link SortedSet} report {@code SORTED}.
506      */
507     public static final int SORTED     = 0x00000004;
508 
509     /**
510      * Characteristic value signifying that the value returned from
511      * {@code estimateSize()} prior to traversal or splitting represents a
512      * finite size that, in the absence of structural source modification,
513      * represents an exact count of the number of elements that would be
514      * encountered by a complete traversal.
515      *
516      * @apiNote Most Spliterators for Collections, that cover all elements of a
517      * {@code Collection} report this characteristic. Sub-spliterators, such as
518      * those for {@link HashSet}, that cover a sub-set of elements and
519      * approximate their reported size do not.
520      */
521     public static final int SIZED      = 0x00000040;
522 
523     /**
524      * Characteristic value signifying that the source guarantees that
525      * encountered elements will not be {@code null}. (This applies,
526      * for example, to most concurrent collections, queues, and maps.)
527      */
528     public static final int NONNULL    = 0x00000100;
529 
530     /**
531      * Characteristic value signifying that the element source cannot be
532      * structurally modified; that is, elements cannot be added, replaced, or
533      * removed, so such changes cannot occur during traversal. A Spliterator
534      * that does not report {@code IMMUTABLE} or {@code CONCURRENT} is expected
535      * to have a documented policy (for example throwing
536      * {@link ConcurrentModificationException}) concerning structural
537      * interference detected during traversal.
538      */
539     public static final int IMMUTABLE  = 0x00000400;
540 
541     /**
542      * Characteristic value signifying that the element source may be safely
543      * concurrently modified (allowing additions, replacements, and/or removals)
544      * by multiple threads without external synchronization. If so, the
545      * Spliterator is expected to have a documented policy concerning the impact
546      * of modifications during traversal.
547      *
548      * <p>A top-level Spliterator should not report both {@code CONCURRENT} and
549      * {@code SIZED}, since the finite size, if known, may change if the source
550      * is concurrently modified during traversal. Such a Spliterator is
551      * inconsistent and no guarantees can be made about any computation using
552      * that Spliterator. Sub-spliterators may report {@code SIZED} if the
553      * sub-split size is known and additions or removals to the source are not
554      * reflected when traversing.
555      *
556      * @apiNote Most concurrent collections maintain a consistency policy
557      * guaranteeing accuracy with respect to elements present at the point of
558      * Spliterator construction, but possibly not reflecting subsequent
559      * additions or removals.
560      */
561     public static final int CONCURRENT = 0x00001000;
562 
563     /**
564      * Characteristic value signifying that all Spliterators resulting from
565      * {@code trySplit()} will be both {@link #SIZED} and {@link #SUBSIZED}.
566      * (This means that all child Spliterators, whether direct or indirect, will
567      * be {@code SIZED}.)
568      *
569      * <p>A Spliterator that does not report {@code SIZED} as required by
570      * {@code SUBSIZED} is inconsistent and no guarantees can be made about any
571      * computation using that Spliterator.
572      *
573      * @apiNote Some spliterators, such as the top-level spliterator for an
574      * approximately balanced binary tree, will report {@code SIZED} but not
575      * {@code SUBSIZED}, since it is common to know the size of the entire tree
576      * but not the exact sizes of subtrees.
577      */
578     public static final int SUBSIZED = 0x00004000;
579 
580     /**
581      * A Spliterator specialized for primitive values.
582      *
583      * @param <T> the type of elements returned by this Spliterator.  The
584      * type must be a wrapper type for a primitive type, such as {@code Integer}
585      * for the primitive {@code int} type.
586      * @param <T_CONS> the type of primitive consumer.  The type must be a
587      * primitive specialization of {@link java.util.function.Consumer} for
588      * {@code T}, such as {@link java.util.function.IntConsumer} for
589      * {@code Integer}.
590      * @param <T_SPLITR> the type of primitive Spliterator.  The type must be
591      * a primitive specialization of Spliterator for {@code T}, such as
592      * {@link Spliterator.OfInt} for {@code Integer}.
593      *
594      * @see Spliterator.OfInt
595      * @see Spliterator.OfLong
596      * @see Spliterator.OfDouble
597      * @since 1.8
598      */
599     public interface OfPrimitive<T, T_CONS, T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>>
600             extends Spliterator<T> {
601         @Override
602         T_SPLITR trySplit();
603 
604         /**
605          * If a remaining element exists, performs the given action on it,
606          * returning {@code true}; else returns {@code false}.  If this
607          * Spliterator is {@link #ORDERED} the action is performed on the
608          * next element in encounter order.  Exceptions thrown by the
609          * action are relayed to the caller.
610          *
611          * @param action The action
612          * @return {@code false} if no remaining elements existed
613          * upon entry to this method, else {@code true}.
614          * @throws NullPointerException if the specified action is null
615          */
616         @SuppressWarnings("overloads")
617         boolean tryAdvance(T_CONS action);
618 
619         /**
620          * Performs the given action for each remaining element, sequentially in
621          * the current thread, until all elements have been processed or the
622          * action throws an exception.  If this Spliterator is {@link #ORDERED},
623          * actions are performed in encounter order.  Exceptions thrown by the
624          * action are relayed to the caller.
625          *
626          * @implSpec
627          * The default implementation repeatedly invokes {@link #tryAdvance}
628          * until it returns {@code false}.  It should be overridden whenever
629          * possible.
630          *
631          * @param action The action
632          * @throws NullPointerException if the specified action is null
633          */
634         @SuppressWarnings("overloads")
635         default void forEachRemaining(T_CONS action) {
636             do { } while (tryAdvance(action));
637         }
638     }
639 
640     /**
641      * A Spliterator specialized for {@code int} values.
642      * @since 1.8
643      */
644     public interface OfInt extends OfPrimitive<Integer, IntConsumer, OfInt> {
645 
646         @Override
647         OfInt trySplit();
648 
649         @Override
650         boolean tryAdvance(IntConsumer action);
651 
652         @Override
653         default void forEachRemaining(IntConsumer action) {
654             do { } while (tryAdvance(action));
655         }
656 
657         /**
658          * {@inheritDoc}
659          * @implSpec
660          * If the action is an instance of {@code IntConsumer} then it is cast
661          * to {@code IntConsumer} and passed to
662          * {@link #tryAdvance(java.util.function.IntConsumer)}; otherwise
663          * the action is adapted to an instance of {@code IntConsumer}, by
664          * boxing the argument of {@code IntConsumer}, and then passed to
665          * {@link #tryAdvance(java.util.function.IntConsumer)}.
666          */
667         @Override
668         default boolean tryAdvance(Consumer<? super Integer> action) {
669             if (action instanceof IntConsumer) {
670                 return tryAdvance((IntConsumer) action);
671             }
672             else {
673                 if (Tripwire.ENABLED)
674                     Tripwire.trip(getClass(),
675                                   "{0} calling Spliterator.OfInt.tryAdvance((IntConsumer) action::accept)");
676                 return tryAdvance((IntConsumer) action::accept);
677             }
678         }
679 
680         /**
681          * {@inheritDoc}
682          * @implSpec
683          * If the action is an instance of {@code IntConsumer} then it is cast
684          * to {@code IntConsumer} and passed to
685          * {@link #forEachRemaining(java.util.function.IntConsumer)}; otherwise
686          * the action is adapted to an instance of {@code IntConsumer}, by
687          * boxing the argument of {@code IntConsumer}, and then passed to
688          * {@link #forEachRemaining(java.util.function.IntConsumer)}.
689          */
690         @Override
691         default void forEachRemaining(Consumer<? super Integer> action) {
692             if (action instanceof IntConsumer) {
693                 forEachRemaining((IntConsumer) action);
694             }
695             else {
696                 if (Tripwire.ENABLED)
697                     Tripwire.trip(getClass(),
698                                   "{0} calling Spliterator.OfInt.forEachRemaining((IntConsumer) action::accept)");
699                 forEachRemaining((IntConsumer) action::accept);
700             }
701         }
702     }
703 
704     /**
705      * A Spliterator specialized for {@code long} values.
706      * @since 1.8
707      */
708     public interface OfLong extends OfPrimitive<Long, LongConsumer, OfLong> {
709 
710         @Override
711         OfLong trySplit();
712 
713         @Override
714         boolean tryAdvance(LongConsumer action);
715 
716         @Override
717         default void forEachRemaining(LongConsumer action) {
718             do { } while (tryAdvance(action));
719         }
720 
721         /**
722          * {@inheritDoc}
723          * @implSpec
724          * If the action is an instance of {@code LongConsumer} then it is cast
725          * to {@code LongConsumer} and passed to
726          * {@link #tryAdvance(java.util.function.LongConsumer)}; otherwise
727          * the action is adapted to an instance of {@code LongConsumer}, by
728          * boxing the argument of {@code LongConsumer}, and then passed to
729          * {@link #tryAdvance(java.util.function.LongConsumer)}.
730          */
731         @Override
732         default boolean tryAdvance(Consumer<? super Long> action) {
733             if (action instanceof LongConsumer) {
734                 return tryAdvance((LongConsumer) action);
735             }
736             else {
737                 if (Tripwire.ENABLED)
738                     Tripwire.trip(getClass(),
739                                   "{0} calling Spliterator.OfLong.tryAdvance((LongConsumer) action::accept)");
740                 return tryAdvance((LongConsumer) action::accept);
741             }
742         }
743 
744         /**
745          * {@inheritDoc}
746          * @implSpec
747          * If the action is an instance of {@code LongConsumer} then it is cast
748          * to {@code LongConsumer} and passed to
749          * {@link #forEachRemaining(java.util.function.LongConsumer)}; otherwise
750          * the action is adapted to an instance of {@code LongConsumer}, by
751          * boxing the argument of {@code LongConsumer}, and then passed to
752          * {@link #forEachRemaining(java.util.function.LongConsumer)}.
753          */
754         @Override
755         default void forEachRemaining(Consumer<? super Long> action) {
756             if (action instanceof LongConsumer) {
757                 forEachRemaining((LongConsumer) action);
758             }
759             else {
760                 if (Tripwire.ENABLED)
761                     Tripwire.trip(getClass(),
762                                   "{0} calling Spliterator.OfLong.forEachRemaining((LongConsumer) action::accept)");
763                 forEachRemaining((LongConsumer) action::accept);
764             }
765         }
766     }
767 
768     /**
769      * A Spliterator specialized for {@code double} values.
770      * @since 1.8
771      */
772     public interface OfDouble extends OfPrimitive<Double, DoubleConsumer, OfDouble> {
773 
774         @Override
775         OfDouble trySplit();
776 
777         @Override
778         boolean tryAdvance(DoubleConsumer action);
779 
780         @Override
781         default void forEachRemaining(DoubleConsumer action) {
782             do { } while (tryAdvance(action));
783         }
784 
785         /**
786          * {@inheritDoc}
787          * @implSpec
788          * If the action is an instance of {@code DoubleConsumer} then it is
789          * cast to {@code DoubleConsumer} and passed to
790          * {@link #tryAdvance(java.util.function.DoubleConsumer)}; otherwise
791          * the action is adapted to an instance of {@code DoubleConsumer}, by
792          * boxing the argument of {@code DoubleConsumer}, and then passed to
793          * {@link #tryAdvance(java.util.function.DoubleConsumer)}.
794          */
795         @Override
796         default boolean tryAdvance(Consumer<? super Double> action) {
797             if (action instanceof DoubleConsumer) {
798                 return tryAdvance((DoubleConsumer) action);
799             }
800             else {
801                 if (Tripwire.ENABLED)
802                     Tripwire.trip(getClass(),
803                                   "{0} calling Spliterator.OfDouble.tryAdvance((DoubleConsumer) action::accept)");
804                 return tryAdvance((DoubleConsumer) action::accept);
805             }
806         }
807 
808         /**
809          * {@inheritDoc}
810          * @implSpec
811          * If the action is an instance of {@code DoubleConsumer} then it is
812          * cast to {@code DoubleConsumer} and passed to
813          * {@link #forEachRemaining(java.util.function.DoubleConsumer)};
814          * otherwise the action is adapted to an instance of
815          * {@code DoubleConsumer}, by boxing the argument of
816          * {@code DoubleConsumer}, and then passed to
817          * {@link #forEachRemaining(java.util.function.DoubleConsumer)}.
818          */
819         @Override
820         default void forEachRemaining(Consumer<? super Double> action) {
821             if (action instanceof DoubleConsumer) {
822                 forEachRemaining((DoubleConsumer) action);
823             }
824             else {
825                 if (Tripwire.ENABLED)
826                     Tripwire.trip(getClass(),
827                                   "{0} calling Spliterator.OfDouble.forEachRemaining((DoubleConsumer) action::accept)");
828                 forEachRemaining((DoubleConsumer) action::accept);
829             }
830         }
831     }
832 }