1 /* 2 * Copyright (c) 2012, 2015, 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.stream; 26 27 import java.util.Spliterator; 28 import java.util.function.Consumer; 29 import java.util.function.DoubleConsumer; 30 import java.util.function.IntConsumer; 31 import java.util.function.IntFunction; 32 import java.util.function.LongConsumer; 33 34 /** 35 * An immutable container for describing an ordered sequence of elements of some 36 * type {@code T}. 37 * 38 * <p>A {@code Node} contains a fixed number of elements, which can be accessed 39 * via the {@link #count}, {@link #spliterator}, {@link #forEach}, 40 * {@link #asArray}, or {@link #copyInto} methods. A {@code Node} may have zero 41 * or more child {@code Node}s; if it has no children (accessed via 42 * {@link #getChildCount} and {@link #getChild(int)}, it is considered <em>flat 43 * </em> or a <em>leaf</em>; if it has children, it is considered an 44 * <em>internal</em> node. The size of an internal node is the sum of sizes of 45 * its children. 46 * 47 * @apiNote 48 * <p>A {@code Node} typically does not store the elements directly, but instead 49 * mediates access to one or more existing (effectively immutable) data 50 * structures such as a {@code Collection}, array, or a set of other 51 * {@code Node}s. Commonly {@code Node}s are formed into a tree whose shape 52 * corresponds to the computation tree that produced the elements that are 53 * contained in the leaf nodes. The use of {@code Node} within the stream 54 * framework is largely to avoid copying data unnecessarily during parallel 55 * operations. 56 * 57 * @param <T> the type of elements. 58 * @since 1.8 59 * @hide Visible for CTS testing only (OpenJDK8 tests). 60 */ 61 // Android-changed: Made public for CTS tests only. 62 public interface Node<T> { 63 64 /** 65 * Returns a {@link Spliterator} describing the elements contained in this 66 * {@code Node}. 67 * 68 * @return a {@code Spliterator} describing the elements contained in this 69 * {@code Node} 70 */ spliterator()71 Spliterator<T> spliterator(); 72 73 /** 74 * Traverses the elements of this node, and invoke the provided 75 * {@code Consumer} with each element. Elements are provided in encounter 76 * order if the source for the {@code Node} has a defined encounter order. 77 * 78 * @param consumer a {@code Consumer} that is to be invoked with each 79 * element in this {@code Node} 80 */ forEach(Consumer<? super T> consumer)81 void forEach(Consumer<? super T> consumer); 82 83 /** 84 * Returns the number of child nodes of this node. 85 * 86 * @implSpec The default implementation returns zero. 87 * 88 * @return the number of child nodes 89 */ getChildCount()90 default int getChildCount() { 91 return 0; 92 } 93 94 /** 95 * Retrieves the child {@code Node} at a given index. 96 * 97 * @implSpec The default implementation always throws 98 * {@code IndexOutOfBoundsException}. 99 * 100 * @param i the index to the child node 101 * @return the child node 102 * @throws IndexOutOfBoundsException if the index is less than 0 or greater 103 * than or equal to the number of child nodes 104 */ getChild(int i)105 default Node<T> getChild(int i) { 106 throw new IndexOutOfBoundsException(); 107 } 108 109 /** 110 * Return a node describing a subsequence of the elements of this node, 111 * starting at the given inclusive start offset and ending at the given 112 * exclusive end offset. 113 * 114 * @param from The (inclusive) starting offset of elements to include, must 115 * be in range 0..count(). 116 * @param to The (exclusive) end offset of elements to include, must be 117 * in range 0..count(). 118 * @param generator A function to be used to create a new array, if needed, 119 * for reference nodes. 120 * @return the truncated node 121 */ truncate(long from, long to, IntFunction<T[]> generator)122 default Node<T> truncate(long from, long to, IntFunction<T[]> generator) { 123 if (from == 0 && to == count()) 124 return this; 125 Spliterator<T> spliterator = spliterator(); 126 long size = to - from; 127 Node.Builder<T> nodeBuilder = Nodes.builder(size, generator); 128 nodeBuilder.begin(size); 129 for (int i = 0; i < from && spliterator.tryAdvance(e -> { }); i++) { } 130 if (to == count()) { 131 spliterator.forEachRemaining(nodeBuilder); 132 } else { 133 for (int i = 0; i < size && spliterator.tryAdvance(nodeBuilder); i++) { } 134 } 135 nodeBuilder.end(); 136 return nodeBuilder.build(); 137 } 138 139 /** 140 * Provides an array view of the contents of this node. 141 * 142 * <p>Depending on the underlying implementation, this may return a 143 * reference to an internal array rather than a copy. Since the returned 144 * array may be shared, the returned array should not be modified. The 145 * {@code generator} function may be consulted to create the array if a new 146 * array needs to be created. 147 * 148 * @param generator a factory function which takes an integer parameter and 149 * returns a new, empty array of that size and of the appropriate 150 * array type 151 * @return an array containing the contents of this {@code Node} 152 */ asArray(IntFunction<T[]> generator)153 T[] asArray(IntFunction<T[]> generator); 154 155 /** 156 * Copies the content of this {@code Node} into an array, starting at a 157 * given offset into the array. It is the caller's responsibility to ensure 158 * there is sufficient room in the array, otherwise unspecified behaviour 159 * will occur if the array length is less than the number of elements 160 * contained in this node. 161 * 162 * @param array the array into which to copy the contents of this 163 * {@code Node} 164 * @param offset the starting offset within the array 165 * @throws IndexOutOfBoundsException if copying would cause access of data 166 * outside array bounds 167 * @throws NullPointerException if {@code array} is {@code null} 168 */ copyInto(T[] array, int offset)169 void copyInto(T[] array, int offset); 170 171 /** 172 * Gets the {@code StreamShape} associated with this {@code Node}. 173 * 174 * @implSpec The default in {@code Node} returns 175 * {@code StreamShape.REFERENCE} 176 * 177 * @return the stream shape associated with this node 178 */ getShape()179 default StreamShape getShape() { 180 return StreamShape.REFERENCE; 181 } 182 183 /** 184 * Returns the number of elements contained in this node. 185 * 186 * @return the number of elements contained in this node 187 */ count()188 long count(); 189 190 /** 191 * A mutable builder for a {@code Node} that implements {@link Sink}, which 192 * builds a flat node containing the elements that have been pushed to it. 193 */ 194 interface Builder<T> extends Sink<T> { 195 196 /** 197 * Builds the node. Should be called after all elements have been 198 * pushed and signalled with an invocation of {@link Sink#end()}. 199 * 200 * @return the resulting {@code Node} 201 */ build()202 Node<T> build(); 203 204 /** 205 * Specialized {@code Node.Builder} for int elements 206 */ 207 interface OfInt extends Node.Builder<Integer>, Sink.OfInt { 208 @Override build()209 Node.OfInt build(); 210 } 211 212 /** 213 * Specialized {@code Node.Builder} for long elements 214 */ 215 interface OfLong extends Node.Builder<Long>, Sink.OfLong { 216 @Override build()217 Node.OfLong build(); 218 } 219 220 /** 221 * Specialized {@code Node.Builder} for double elements 222 */ 223 interface OfDouble extends Node.Builder<Double>, Sink.OfDouble { 224 @Override build()225 Node.OfDouble build(); 226 } 227 } 228 229 public interface OfPrimitive<T, T_CONS, T_ARR, 230 T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>, 231 T_NODE extends OfPrimitive<T, T_CONS, T_ARR, T_SPLITR, T_NODE>> 232 extends Node<T> { 233 234 /** 235 * {@inheritDoc} 236 * 237 * @return a {@link Spliterator.OfPrimitive} describing the elements of 238 * this node 239 */ 240 @Override spliterator()241 T_SPLITR spliterator(); 242 243 /** 244 * Traverses the elements of this node, and invoke the provided 245 * {@code action} with each element. 246 * 247 * @param action a consumer that is to be invoked with each 248 * element in this {@code Node.OfPrimitive} 249 */ 250 @SuppressWarnings("overloads") forEach(T_CONS action)251 void forEach(T_CONS action); 252 253 @Override getChild(int i)254 default T_NODE getChild(int i) { 255 throw new IndexOutOfBoundsException(); 256 } 257 truncate(long from, long to, IntFunction<T[]> generator)258 T_NODE truncate(long from, long to, IntFunction<T[]> generator); 259 260 /** 261 * {@inheritDoc} 262 * 263 * @implSpec the default implementation invokes the generator to create 264 * an instance of a boxed primitive array with a length of 265 * {@link #count()} and then invokes {@link #copyInto(T[], int)} with 266 * that array at an offset of 0. 267 */ 268 @Override asArray(IntFunction<T[]> generator)269 default T[] asArray(IntFunction<T[]> generator) { 270 if (java.util.stream.Tripwire.ENABLED) 271 java.util.stream.Tripwire.trip(getClass(), "{0} calling Node.OfPrimitive.asArray"); 272 273 long size = count(); 274 if (size >= Nodes.MAX_ARRAY_SIZE) 275 throw new IllegalArgumentException(Nodes.BAD_SIZE); 276 T[] boxed = generator.apply((int) count()); 277 copyInto(boxed, 0); 278 return boxed; 279 } 280 281 /** 282 * Views this node as a primitive array. 283 * 284 * <p>Depending on the underlying implementation this may return a 285 * reference to an internal array rather than a copy. It is the callers 286 * responsibility to decide if either this node or the array is utilized 287 * as the primary reference for the data.</p> 288 * 289 * @return an array containing the contents of this {@code Node} 290 */ asPrimitiveArray()291 T_ARR asPrimitiveArray(); 292 293 /** 294 * Creates a new primitive array. 295 * 296 * @param count the length of the primitive array. 297 * @return the new primitive array. 298 */ newArray(int count)299 T_ARR newArray(int count); 300 301 /** 302 * Copies the content of this {@code Node} into a primitive array, 303 * starting at a given offset into the array. It is the caller's 304 * responsibility to ensure there is sufficient room in the array. 305 * 306 * @param array the array into which to copy the contents of this 307 * {@code Node} 308 * @param offset the starting offset within the array 309 * @throws IndexOutOfBoundsException if copying would cause access of 310 * data outside array bounds 311 * @throws NullPointerException if {@code array} is {@code null} 312 */ copyInto(T_ARR array, int offset)313 void copyInto(T_ARR array, int offset); 314 } 315 316 /** 317 * Specialized {@code Node} for int elements 318 */ 319 @SuppressWarnings("overloads") 320 interface OfInt extends OfPrimitive<Integer, IntConsumer, int[], Spliterator.OfInt, OfInt> { 321 322 /** 323 * {@inheritDoc} 324 * 325 * @param consumer a {@code Consumer} that is to be invoked with each 326 * element in this {@code Node}. If this is an 327 * {@code IntConsumer}, it is cast to {@code IntConsumer} so the 328 * elements may be processed without boxing. 329 */ 330 @Override forEach(Consumer<? super Integer> consumer)331 default void forEach(Consumer<? super Integer> consumer) { 332 if (consumer instanceof IntConsumer) { 333 forEach((IntConsumer) consumer); 334 } 335 else { 336 if (Tripwire.ENABLED) 337 Tripwire.trip(getClass(), "{0} calling Node.OfInt.forEachRemaining(Consumer)"); 338 spliterator().forEachRemaining(consumer); 339 } 340 } 341 342 /** 343 * {@inheritDoc} 344 * 345 * @implSpec the default implementation invokes {@link #asPrimitiveArray()} to 346 * obtain an int[] array then and copies the elements from that int[] 347 * array into the boxed Integer[] array. This is not efficient and it 348 * is recommended to invoke {@link #copyInto(Object, int)}. 349 */ 350 @Override copyInto(Integer[] boxed, int offset)351 default void copyInto(Integer[] boxed, int offset) { 352 if (Tripwire.ENABLED) 353 Tripwire.trip(getClass(), "{0} calling Node.OfInt.copyInto(Integer[], int)"); 354 355 int[] array = asPrimitiveArray(); 356 for (int i = 0; i < array.length; i++) { 357 boxed[offset + i] = array[i]; 358 } 359 } 360 361 @Override truncate(long from, long to, IntFunction<Integer[]> generator)362 default Node.OfInt truncate(long from, long to, IntFunction<Integer[]> generator) { 363 if (from == 0 && to == count()) 364 return this; 365 long size = to - from; 366 Spliterator.OfInt spliterator = spliterator(); 367 Node.Builder.OfInt nodeBuilder = Nodes.intBuilder(size); 368 nodeBuilder.begin(size); 369 for (int i = 0; i < from && spliterator.tryAdvance((IntConsumer) e -> { }); i++) { } 370 if (to == count()) { 371 spliterator.forEachRemaining((IntConsumer) nodeBuilder); 372 } else { 373 for (int i = 0; i < size && spliterator.tryAdvance((IntConsumer) nodeBuilder); i++) { } 374 } 375 nodeBuilder.end(); 376 return nodeBuilder.build(); 377 } 378 379 @Override newArray(int count)380 default int[] newArray(int count) { 381 return new int[count]; 382 } 383 384 /** 385 * {@inheritDoc} 386 * @implSpec The default in {@code Node.OfInt} returns 387 * {@code StreamShape.INT_VALUE} 388 */ getShape()389 default StreamShape getShape() { 390 return StreamShape.INT_VALUE; 391 } 392 } 393 394 /** 395 * Specialized {@code Node} for long elements 396 */ 397 @SuppressWarnings("overloads") 398 interface OfLong extends OfPrimitive<Long, LongConsumer, long[], Spliterator.OfLong, OfLong> { 399 400 /** 401 * {@inheritDoc} 402 * 403 * @param consumer A {@code Consumer} that is to be invoked with each 404 * element in this {@code Node}. If this is an 405 * {@code LongConsumer}, it is cast to {@code LongConsumer} so 406 * the elements may be processed without boxing. 407 */ 408 @Override forEach(Consumer<? super Long> consumer)409 default void forEach(Consumer<? super Long> consumer) { 410 if (consumer instanceof LongConsumer) { 411 forEach((LongConsumer) consumer); 412 } 413 else { 414 if (Tripwire.ENABLED) 415 Tripwire.trip(getClass(), "{0} calling Node.OfLong.forEachRemaining(Consumer)"); 416 spliterator().forEachRemaining(consumer); 417 } 418 } 419 420 /** 421 * {@inheritDoc} 422 * 423 * @implSpec the default implementation invokes {@link #asPrimitiveArray()} 424 * to obtain a long[] array then and copies the elements from that 425 * long[] array into the boxed Long[] array. This is not efficient and 426 * it is recommended to invoke {@link #copyInto(Object, int)}. 427 */ 428 @Override copyInto(Long[] boxed, int offset)429 default void copyInto(Long[] boxed, int offset) { 430 if (Tripwire.ENABLED) 431 Tripwire.trip(getClass(), "{0} calling Node.OfInt.copyInto(Long[], int)"); 432 433 long[] array = asPrimitiveArray(); 434 for (int i = 0; i < array.length; i++) { 435 boxed[offset + i] = array[i]; 436 } 437 } 438 439 @Override truncate(long from, long to, IntFunction<Long[]> generator)440 default Node.OfLong truncate(long from, long to, IntFunction<Long[]> generator) { 441 if (from == 0 && to == count()) 442 return this; 443 long size = to - from; 444 Spliterator.OfLong spliterator = spliterator(); 445 Node.Builder.OfLong nodeBuilder = Nodes.longBuilder(size); 446 nodeBuilder.begin(size); 447 for (int i = 0; i < from && spliterator.tryAdvance((LongConsumer) e -> { }); i++) { } 448 if (to == count()) { 449 spliterator.forEachRemaining((LongConsumer) nodeBuilder); 450 } else { 451 for (int i = 0; i < size && spliterator.tryAdvance((LongConsumer) nodeBuilder); i++) { } 452 } 453 nodeBuilder.end(); 454 return nodeBuilder.build(); 455 } 456 457 @Override newArray(int count)458 default long[] newArray(int count) { 459 return new long[count]; 460 } 461 462 /** 463 * {@inheritDoc} 464 * @implSpec The default in {@code Node.OfLong} returns 465 * {@code StreamShape.LONG_VALUE} 466 */ getShape()467 default StreamShape getShape() { 468 return StreamShape.LONG_VALUE; 469 } 470 } 471 472 /** 473 * Specialized {@code Node} for double elements 474 */ 475 @SuppressWarnings("overloads") 476 interface OfDouble extends OfPrimitive<Double, DoubleConsumer, double[], Spliterator.OfDouble, OfDouble> { 477 478 /** 479 * {@inheritDoc} 480 * 481 * @param consumer A {@code Consumer} that is to be invoked with each 482 * element in this {@code Node}. If this is an 483 * {@code DoubleConsumer}, it is cast to {@code DoubleConsumer} 484 * so the elements may be processed without boxing. 485 */ 486 @Override forEach(Consumer<? super Double> consumer)487 default void forEach(Consumer<? super Double> consumer) { 488 if (consumer instanceof DoubleConsumer) { 489 forEach((DoubleConsumer) consumer); 490 } 491 else { 492 if (Tripwire.ENABLED) 493 Tripwire.trip(getClass(), "{0} calling Node.OfLong.forEachRemaining(Consumer)"); 494 spliterator().forEachRemaining(consumer); 495 } 496 } 497 498 // 499 500 /** 501 * {@inheritDoc} 502 * 503 * @implSpec the default implementation invokes {@link #asPrimitiveArray()} 504 * to obtain a double[] array then and copies the elements from that 505 * double[] array into the boxed Double[] array. This is not efficient 506 * and it is recommended to invoke {@link #copyInto(Object, int)}. 507 */ 508 @Override copyInto(Double[] boxed, int offset)509 default void copyInto(Double[] boxed, int offset) { 510 if (Tripwire.ENABLED) 511 Tripwire.trip(getClass(), "{0} calling Node.OfDouble.copyInto(Double[], int)"); 512 513 double[] array = asPrimitiveArray(); 514 for (int i = 0; i < array.length; i++) { 515 boxed[offset + i] = array[i]; 516 } 517 } 518 519 @Override truncate(long from, long to, IntFunction<Double[]> generator)520 default Node.OfDouble truncate(long from, long to, IntFunction<Double[]> generator) { 521 if (from == 0 && to == count()) 522 return this; 523 long size = to - from; 524 Spliterator.OfDouble spliterator = spliterator(); 525 Node.Builder.OfDouble nodeBuilder = Nodes.doubleBuilder(size); 526 nodeBuilder.begin(size); 527 for (int i = 0; i < from && spliterator.tryAdvance((DoubleConsumer) e -> { }); i++) { } 528 if (to == count()) { 529 spliterator.forEachRemaining((DoubleConsumer) nodeBuilder); 530 } else { 531 for (int i = 0; i < size && spliterator.tryAdvance((DoubleConsumer) nodeBuilder); i++) { } 532 } 533 nodeBuilder.end(); 534 return nodeBuilder.build(); 535 } 536 537 @Override newArray(int count)538 default double[] newArray(int count) { 539 return new double[count]; 540 } 541 542 /** 543 * {@inheritDoc} 544 * 545 * @implSpec The default in {@code Node.OfDouble} returns 546 * {@code StreamShape.DOUBLE_VALUE} 547 */ getShape()548 default StreamShape getShape() { 549 return StreamShape.DOUBLE_VALUE; 550 } 551 } 552 } 553