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 id="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 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 Iterator}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 {@systemProperty 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 * <p> 304 * Subsequent behavior of a spliterator is unspecified if the action throws 305 * an exception. 306 * 307 * @param action The action 308 * @return {@code false} if no remaining elements existed 309 * upon entry to this method, else {@code true}. 310 * @throws NullPointerException if the specified action is null 311 */ tryAdvance(Consumer<? super T> action)312 boolean tryAdvance(Consumer<? super T> action); 313 314 /** 315 * Performs the given action for each remaining element, sequentially in 316 * the current thread, until all elements have been processed or the action 317 * throws an exception. If this Spliterator is {@link #ORDERED}, actions 318 * are performed in encounter order. Exceptions thrown by the action 319 * are relayed to the caller. 320 * <p> 321 * Subsequent behavior of a spliterator is unspecified if the action throws 322 * an exception. 323 * 324 * @implSpec 325 * The default implementation repeatedly invokes {@link #tryAdvance} until 326 * it returns {@code false}. It should be overridden whenever possible. 327 * 328 * @param action The action 329 * @throws NullPointerException if the specified action is null 330 */ forEachRemaining(Consumer<? super T> action)331 default void forEachRemaining(Consumer<? super T> action) { 332 do { } while (tryAdvance(action)); 333 } 334 335 /** 336 * If this spliterator can be partitioned, returns a Spliterator 337 * covering elements, that will, upon return from this method, not 338 * be covered by this Spliterator. 339 * 340 * <p>If this Spliterator is {@link #ORDERED}, the returned Spliterator 341 * must cover a strict prefix of the elements. 342 * 343 * <p>Unless this Spliterator covers an infinite number of elements, 344 * repeated calls to {@code trySplit()} must eventually return {@code null}. 345 * Upon non-null return: 346 * <ul> 347 * <li>the value reported for {@code estimateSize()} before splitting, 348 * must, after splitting, be greater than or equal to {@code estimateSize()} 349 * for this and the returned Spliterator; and</li> 350 * <li>if this Spliterator is {@code SUBSIZED}, then {@code estimateSize()} 351 * for this spliterator before splitting must be equal to the sum of 352 * {@code estimateSize()} for this and the returned Spliterator after 353 * splitting.</li> 354 * </ul> 355 * 356 * <p>This method may return {@code null} for any reason, 357 * including emptiness, inability to split after traversal has 358 * commenced, data structure constraints, and efficiency 359 * considerations. 360 * 361 * @apiNote 362 * An ideal {@code trySplit} method efficiently (without 363 * traversal) divides its elements exactly in half, allowing 364 * balanced parallel computation. Many departures from this ideal 365 * remain highly effective; for example, only approximately 366 * splitting an approximately balanced tree, or for a tree in 367 * which leaf nodes may contain either one or two elements, 368 * failing to further split these nodes. However, large 369 * deviations in balance and/or overly inefficient {@code 370 * trySplit} mechanics typically result in poor parallel 371 * performance. 372 * 373 * @return a {@code Spliterator} covering some portion of the 374 * elements, or {@code null} if this spliterator cannot be split 375 */ trySplit()376 Spliterator<T> trySplit(); 377 378 /** 379 * Returns an estimate of the number of elements that would be 380 * encountered by a {@link #forEachRemaining} traversal, or returns {@link 381 * Long#MAX_VALUE} if infinite, unknown, or too expensive to compute. 382 * 383 * <p>If this Spliterator is {@link #SIZED} and has not yet been partially 384 * traversed or split, or this Spliterator is {@link #SUBSIZED} and has 385 * not yet been partially traversed, this estimate must be an accurate 386 * count of elements that would be encountered by a complete traversal. 387 * Otherwise, this estimate may be arbitrarily inaccurate, but must decrease 388 * as specified across invocations of {@link #trySplit}. 389 * 390 * @apiNote 391 * Even an inexact estimate is often useful and inexpensive to compute. 392 * For example, a sub-spliterator of an approximately balanced binary tree 393 * may return a value that estimates the number of elements to be half of 394 * that of its parent; if the root Spliterator does not maintain an 395 * accurate count, it could estimate size to be the power of two 396 * corresponding to its maximum depth. 397 * 398 * @return the estimated size, or {@code Long.MAX_VALUE} if infinite, 399 * unknown, or too expensive to compute. 400 */ estimateSize()401 long estimateSize(); 402 403 /** 404 * Convenience method that returns {@link #estimateSize()} if this 405 * Spliterator is {@link #SIZED}, else {@code -1}. 406 * @implSpec 407 * The default implementation returns the result of {@code estimateSize()} 408 * if the Spliterator reports a characteristic of {@code SIZED}, and 409 * {@code -1} otherwise. 410 * 411 * @return the exact size, if known, else {@code -1}. 412 */ getExactSizeIfKnown()413 default long getExactSizeIfKnown() { 414 return (characteristics() & SIZED) == 0 ? -1L : estimateSize(); 415 } 416 417 /** 418 * Returns a set of characteristics of this Spliterator and its 419 * elements. The result is represented as ORed values from {@link 420 * #ORDERED}, {@link #DISTINCT}, {@link #SORTED}, {@link #SIZED}, 421 * {@link #NONNULL}, {@link #IMMUTABLE}, {@link #CONCURRENT}, 422 * {@link #SUBSIZED}. Repeated calls to {@code characteristics()} on 423 * a given spliterator, prior to or in-between calls to {@code trySplit}, 424 * should always return the same result. 425 * 426 * <p>If a Spliterator reports an inconsistent set of 427 * characteristics (either those returned from a single invocation 428 * or across multiple invocations), no guarantees can be made 429 * about any computation using this Spliterator. 430 * 431 * @apiNote The characteristics of a given spliterator before splitting 432 * may differ from the characteristics after splitting. For specific 433 * examples see the characteristic values {@link #SIZED}, {@link #SUBSIZED} 434 * and {@link #CONCURRENT}. 435 * 436 * @return a representation of characteristics 437 */ characteristics()438 int characteristics(); 439 440 /** 441 * Returns {@code true} if this Spliterator's {@link 442 * #characteristics} contain all of the given characteristics. 443 * 444 * @implSpec 445 * The default implementation returns true if the corresponding bits 446 * of the given characteristics are set. 447 * 448 * @param characteristics the characteristics to check for 449 * @return {@code true} if all the specified characteristics are present, 450 * else {@code false} 451 */ hasCharacteristics(int characteristics)452 default boolean hasCharacteristics(int characteristics) { 453 return (characteristics() & characteristics) == characteristics; 454 } 455 456 /** 457 * If this Spliterator's source is {@link #SORTED} by a {@link Comparator}, 458 * returns that {@code Comparator}. If the source is {@code SORTED} in 459 * {@linkplain Comparable natural order}, returns {@code null}. Otherwise, 460 * if the source is not {@code SORTED}, throws {@link IllegalStateException}. 461 * 462 * @implSpec 463 * The default implementation always throws {@link IllegalStateException}. 464 * 465 * @return a Comparator, or {@code null} if the elements are sorted in the 466 * natural order. 467 * @throws IllegalStateException if the spliterator does not report 468 * a characteristic of {@code SORTED}. 469 */ getComparator()470 default Comparator<? super T> getComparator() { 471 throw new IllegalStateException(); 472 } 473 474 /** 475 * Characteristic value signifying that an encounter order is defined for 476 * elements. If so, this Spliterator guarantees that method 477 * {@link #trySplit} splits a strict prefix of elements, that method 478 * {@link #tryAdvance} steps by one element in prefix order, and that 479 * {@link #forEachRemaining} performs actions in encounter order. 480 * 481 * <p>A {@link Collection} has an encounter order if the corresponding 482 * {@link Collection#iterator} documents an order. If so, the encounter 483 * order is the same as the documented order. Otherwise, a collection does 484 * not have an encounter order. 485 * 486 * @apiNote Encounter order is guaranteed to be ascending index order for 487 * any {@link List}. But no order is guaranteed for hash-based collections 488 * such as {@link HashSet}. Clients of a Spliterator that reports 489 * {@code ORDERED} are expected to preserve ordering constraints in 490 * non-commutative parallel computations. 491 */ 492 public static final int ORDERED = 0x00000010; 493 494 /** 495 * Characteristic value signifying that, for each pair of 496 * encountered elements {@code x, y}, {@code !x.equals(y)}. This 497 * applies for example, to a Spliterator based on a {@link Set}. 498 */ 499 public static final int DISTINCT = 0x00000001; 500 501 /** 502 * Characteristic value signifying that encounter order follows a defined 503 * sort order. If so, method {@link #getComparator()} returns the associated 504 * Comparator, or {@code null} if all elements are {@link Comparable} and 505 * are sorted by their natural ordering. 506 * 507 * <p>A Spliterator that reports {@code SORTED} must also report 508 * {@code ORDERED}. 509 * 510 * @apiNote The spliterators for {@code Collection} classes in the JDK that 511 * implement {@link NavigableSet} or {@link SortedSet} report {@code SORTED}. 512 */ 513 public static final int SORTED = 0x00000004; 514 515 /** 516 * Characteristic value signifying that the value returned from 517 * {@code estimateSize()} prior to traversal or splitting represents a 518 * finite size that, in the absence of structural source modification, 519 * represents an exact count of the number of elements that would be 520 * encountered by a complete traversal. 521 * 522 * @apiNote Most Spliterators for Collections, that cover all elements of a 523 * {@code Collection} report this characteristic. Sub-spliterators, such as 524 * those for {@link HashSet}, that cover a sub-set of elements and 525 * approximate their reported size do not. 526 */ 527 public static final int SIZED = 0x00000040; 528 529 /** 530 * Characteristic value signifying that the source guarantees that 531 * encountered elements will not be {@code null}. (This applies, 532 * for example, to most concurrent collections, queues, and maps.) 533 */ 534 public static final int NONNULL = 0x00000100; 535 536 /** 537 * Characteristic value signifying that the element source cannot be 538 * structurally modified; that is, elements cannot be added, replaced, or 539 * removed, so such changes cannot occur during traversal. A Spliterator 540 * that does not report {@code IMMUTABLE} or {@code CONCURRENT} is expected 541 * to have a documented policy (for example throwing 542 * {@link ConcurrentModificationException}) concerning structural 543 * interference detected during traversal. 544 */ 545 public static final int IMMUTABLE = 0x00000400; 546 547 /** 548 * Characteristic value signifying that the element source may be safely 549 * concurrently modified (allowing additions, replacements, and/or removals) 550 * by multiple threads without external synchronization. If so, the 551 * Spliterator is expected to have a documented policy concerning the impact 552 * of modifications during traversal. 553 * 554 * <p>A top-level Spliterator should not report both {@code CONCURRENT} and 555 * {@code SIZED}, since the finite size, if known, may change if the source 556 * is concurrently modified during traversal. Such a Spliterator is 557 * inconsistent and no guarantees can be made about any computation using 558 * that Spliterator. Sub-spliterators may report {@code SIZED} if the 559 * sub-split size is known and additions or removals to the source are not 560 * reflected when traversing. 561 * 562 * <p>A top-level Spliterator should not report both {@code CONCURRENT} and 563 * {@code IMMUTABLE}, since they are mutually exclusive. Such a Spliterator 564 * is inconsistent and no guarantees can be made about any computation using 565 * that Spliterator. Sub-spliterators may report {@code IMMUTABLE} if 566 * additions or removals to the source are not reflected when traversing. 567 * 568 * @apiNote Most concurrent collections maintain a consistency policy 569 * guaranteeing accuracy with respect to elements present at the point of 570 * Spliterator construction, but possibly not reflecting subsequent 571 * additions or removals. 572 */ 573 public static final int CONCURRENT = 0x00001000; 574 575 /** 576 * Characteristic value signifying that all Spliterators resulting from 577 * {@code trySplit()} will be both {@link #SIZED} and {@link #SUBSIZED}. 578 * (This means that all child Spliterators, whether direct or indirect, will 579 * be {@code SIZED}.) 580 * 581 * <p>A Spliterator that does not report {@code SIZED} as required by 582 * {@code SUBSIZED} is inconsistent and no guarantees can be made about any 583 * computation using that Spliterator. 584 * 585 * @apiNote Some spliterators, such as the top-level spliterator for an 586 * approximately balanced binary tree, will report {@code SIZED} but not 587 * {@code SUBSIZED}, since it is common to know the size of the entire tree 588 * but not the exact sizes of subtrees. 589 */ 590 public static final int SUBSIZED = 0x00004000; 591 592 /** 593 * A Spliterator specialized for primitive values. 594 * 595 * @param <T> the type of elements returned by this Spliterator. The 596 * type must be a wrapper type for a primitive type, such as {@code Integer} 597 * for the primitive {@code int} type. 598 * @param <T_CONS> the type of primitive consumer. The type must be a 599 * primitive specialization of {@link java.util.function.Consumer} for 600 * {@code T}, such as {@link java.util.function.IntConsumer} for 601 * {@code Integer}. 602 * @param <T_SPLITR> the type of primitive Spliterator. The type must be 603 * a primitive specialization of Spliterator for {@code T}, such as 604 * {@link Spliterator.OfInt} for {@code Integer}. 605 * 606 * @see Spliterator.OfInt 607 * @see Spliterator.OfLong 608 * @see Spliterator.OfDouble 609 * @since 1.8 610 */ 611 public interface OfPrimitive<T, T_CONS, T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>> 612 extends Spliterator<T> { 613 @Override trySplit()614 T_SPLITR trySplit(); 615 616 /** 617 * If a remaining element exists, performs the given action on it, 618 * returning {@code true}; else returns {@code false}. If this 619 * Spliterator is {@link #ORDERED} the action is performed on the 620 * next element in encounter order. Exceptions thrown by the 621 * action are relayed to the caller. 622 * <p> 623 * Subsequent behavior of a spliterator is unspecified if the action throws 624 * an exception. 625 * 626 * @param action The action 627 * @return {@code false} if no remaining elements existed 628 * upon entry to this method, else {@code true}. 629 * @throws NullPointerException if the specified action is null 630 */ 631 @SuppressWarnings("overloads") tryAdvance(T_CONS action)632 boolean tryAdvance(T_CONS action); 633 634 /** 635 * Performs the given action for each remaining element, sequentially in 636 * the current thread, until all elements have been processed or the 637 * action throws an exception. If this Spliterator is {@link #ORDERED}, 638 * actions are performed in encounter order. Exceptions thrown by the 639 * action are relayed to the caller. 640 * <p> 641 * Subsequent behavior of a spliterator is unspecified if the action throws 642 * an exception. 643 * 644 * @implSpec 645 * The default implementation repeatedly invokes {@link #tryAdvance} 646 * until it returns {@code false}. It should be overridden whenever 647 * possible. 648 * 649 * @param action The action 650 * @throws NullPointerException if the specified action is null 651 */ 652 @SuppressWarnings("overloads") forEachRemaining(T_CONS action)653 default void forEachRemaining(T_CONS action) { 654 do { } while (tryAdvance(action)); 655 } 656 } 657 658 /** 659 * A Spliterator specialized for {@code int} values. 660 * @since 1.8 661 */ 662 public interface OfInt extends OfPrimitive<Integer, IntConsumer, OfInt> { 663 664 @Override trySplit()665 OfInt trySplit(); 666 667 @Override tryAdvance(IntConsumer action)668 boolean tryAdvance(IntConsumer action); 669 670 @Override forEachRemaining(IntConsumer action)671 default void forEachRemaining(IntConsumer action) { 672 do { } while (tryAdvance(action)); 673 } 674 675 /** 676 * {@inheritDoc} 677 * @implSpec 678 * If the action is an instance of {@code IntConsumer} then it is cast 679 * to {@code IntConsumer} and passed to 680 * {@link #tryAdvance(java.util.function.IntConsumer)}; otherwise 681 * the action is adapted to an instance of {@code IntConsumer}, by 682 * boxing the argument of {@code IntConsumer}, and then passed to 683 * {@link #tryAdvance(java.util.function.IntConsumer)}. 684 */ 685 @Override tryAdvance(Consumer<? super Integer> action)686 default boolean tryAdvance(Consumer<? super Integer> action) { 687 if (action instanceof IntConsumer) { 688 return tryAdvance((IntConsumer) action); 689 } 690 else { 691 if (Tripwire.ENABLED) 692 Tripwire.trip(getClass(), 693 "{0} calling Spliterator.OfInt.tryAdvance((IntConsumer) action::accept)"); 694 return tryAdvance((IntConsumer) action::accept); 695 } 696 } 697 698 /** 699 * {@inheritDoc} 700 * @implSpec 701 * If the action is an instance of {@code IntConsumer} then it is cast 702 * to {@code IntConsumer} and passed to 703 * {@link #forEachRemaining(java.util.function.IntConsumer)}; otherwise 704 * the action is adapted to an instance of {@code IntConsumer}, by 705 * boxing the argument of {@code IntConsumer}, and then passed to 706 * {@link #forEachRemaining(java.util.function.IntConsumer)}. 707 */ 708 @Override forEachRemaining(Consumer<? super Integer> action)709 default void forEachRemaining(Consumer<? super Integer> action) { 710 if (action instanceof IntConsumer) { 711 forEachRemaining((IntConsumer) action); 712 } 713 else { 714 if (Tripwire.ENABLED) 715 Tripwire.trip(getClass(), 716 "{0} calling Spliterator.OfInt.forEachRemaining((IntConsumer) action::accept)"); 717 forEachRemaining((IntConsumer) action::accept); 718 } 719 } 720 } 721 722 /** 723 * A Spliterator specialized for {@code long} values. 724 * @since 1.8 725 */ 726 public interface OfLong extends OfPrimitive<Long, LongConsumer, OfLong> { 727 728 @Override trySplit()729 OfLong trySplit(); 730 731 @Override tryAdvance(LongConsumer action)732 boolean tryAdvance(LongConsumer action); 733 734 @Override forEachRemaining(LongConsumer action)735 default void forEachRemaining(LongConsumer action) { 736 do { } while (tryAdvance(action)); 737 } 738 739 /** 740 * {@inheritDoc} 741 * @implSpec 742 * If the action is an instance of {@code LongConsumer} then it is cast 743 * to {@code LongConsumer} and passed to 744 * {@link #tryAdvance(java.util.function.LongConsumer)}; otherwise 745 * the action is adapted to an instance of {@code LongConsumer}, by 746 * boxing the argument of {@code LongConsumer}, and then passed to 747 * {@link #tryAdvance(java.util.function.LongConsumer)}. 748 */ 749 @Override tryAdvance(Consumer<? super Long> action)750 default boolean tryAdvance(Consumer<? super Long> action) { 751 if (action instanceof LongConsumer) { 752 return tryAdvance((LongConsumer) action); 753 } 754 else { 755 if (Tripwire.ENABLED) 756 Tripwire.trip(getClass(), 757 "{0} calling Spliterator.OfLong.tryAdvance((LongConsumer) action::accept)"); 758 return tryAdvance((LongConsumer) action::accept); 759 } 760 } 761 762 /** 763 * {@inheritDoc} 764 * @implSpec 765 * If the action is an instance of {@code LongConsumer} then it is cast 766 * to {@code LongConsumer} and passed to 767 * {@link #forEachRemaining(java.util.function.LongConsumer)}; otherwise 768 * the action is adapted to an instance of {@code LongConsumer}, by 769 * boxing the argument of {@code LongConsumer}, and then passed to 770 * {@link #forEachRemaining(java.util.function.LongConsumer)}. 771 */ 772 @Override forEachRemaining(Consumer<? super Long> action)773 default void forEachRemaining(Consumer<? super Long> action) { 774 if (action instanceof LongConsumer) { 775 forEachRemaining((LongConsumer) action); 776 } 777 else { 778 if (Tripwire.ENABLED) 779 Tripwire.trip(getClass(), 780 "{0} calling Spliterator.OfLong.forEachRemaining((LongConsumer) action::accept)"); 781 forEachRemaining((LongConsumer) action::accept); 782 } 783 } 784 } 785 786 /** 787 * A Spliterator specialized for {@code double} values. 788 * @since 1.8 789 */ 790 public interface OfDouble extends OfPrimitive<Double, DoubleConsumer, OfDouble> { 791 792 @Override trySplit()793 OfDouble trySplit(); 794 795 @Override tryAdvance(DoubleConsumer action)796 boolean tryAdvance(DoubleConsumer action); 797 798 @Override forEachRemaining(DoubleConsumer action)799 default void forEachRemaining(DoubleConsumer action) { 800 do { } while (tryAdvance(action)); 801 } 802 803 /** 804 * {@inheritDoc} 805 * @implSpec 806 * If the action is an instance of {@code DoubleConsumer} then it is 807 * cast to {@code DoubleConsumer} and passed to 808 * {@link #tryAdvance(java.util.function.DoubleConsumer)}; otherwise 809 * the action is adapted to an instance of {@code DoubleConsumer}, by 810 * boxing the argument of {@code DoubleConsumer}, and then passed to 811 * {@link #tryAdvance(java.util.function.DoubleConsumer)}. 812 */ 813 @Override tryAdvance(Consumer<? super Double> action)814 default boolean tryAdvance(Consumer<? super Double> action) { 815 if (action instanceof DoubleConsumer) { 816 return tryAdvance((DoubleConsumer) action); 817 } 818 else { 819 if (Tripwire.ENABLED) 820 Tripwire.trip(getClass(), 821 "{0} calling Spliterator.OfDouble.tryAdvance((DoubleConsumer) action::accept)"); 822 return tryAdvance((DoubleConsumer) action::accept); 823 } 824 } 825 826 /** 827 * {@inheritDoc} 828 * @implSpec 829 * If the action is an instance of {@code DoubleConsumer} then it is 830 * cast to {@code DoubleConsumer} and passed to 831 * {@link #forEachRemaining(java.util.function.DoubleConsumer)}; 832 * otherwise the action is adapted to an instance of 833 * {@code DoubleConsumer}, by boxing the argument of 834 * {@code DoubleConsumer}, and then passed to 835 * {@link #forEachRemaining(java.util.function.DoubleConsumer)}. 836 */ 837 @Override forEachRemaining(Consumer<? super Double> action)838 default void forEachRemaining(Consumer<? super Double> action) { 839 if (action instanceof DoubleConsumer) { 840 forEachRemaining((DoubleConsumer) action); 841 } 842 else { 843 if (Tripwire.ENABLED) 844 Tripwire.trip(getClass(), 845 "{0} calling Spliterator.OfDouble.forEachRemaining((DoubleConsumer) action::accept)"); 846 forEachRemaining((DoubleConsumer) action::accept); 847 } 848 } 849 } 850 } 851