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 interface OfInt extends OfPrimitive<Integer, IntConsumer, int[], Spliterator.OfInt, OfInt> { 320 321 /** 322 * {@inheritDoc} 323 * 324 * @param consumer a {@code Consumer} that is to be invoked with each 325 * element in this {@code Node}. If this is an 326 * {@code IntConsumer}, it is cast to {@code IntConsumer} so the 327 * elements may be processed without boxing. 328 */ 329 @Override forEach(Consumer<? super Integer> consumer)330 default void forEach(Consumer<? super Integer> consumer) { 331 if (consumer instanceof IntConsumer) { 332 forEach((IntConsumer) consumer); 333 } 334 else { 335 if (Tripwire.ENABLED) 336 Tripwire.trip(getClass(), "{0} calling Node.OfInt.forEachRemaining(Consumer)"); 337 spliterator().forEachRemaining(consumer); 338 } 339 } 340 341 /** 342 * {@inheritDoc} 343 * 344 * @implSpec the default implementation invokes {@link #asPrimitiveArray()} to 345 * obtain an int[] array then and copies the elements from that int[] 346 * array into the boxed Integer[] array. This is not efficient and it 347 * is recommended to invoke {@link #copyInto(Object, int)}. 348 */ 349 @Override copyInto(Integer[] boxed, int offset)350 default void copyInto(Integer[] boxed, int offset) { 351 if (Tripwire.ENABLED) 352 Tripwire.trip(getClass(), "{0} calling Node.OfInt.copyInto(Integer[], int)"); 353 354 int[] array = asPrimitiveArray(); 355 for (int i = 0; i < array.length; i++) { 356 boxed[offset + i] = array[i]; 357 } 358 } 359 360 @Override truncate(long from, long to, IntFunction<Integer[]> generator)361 default Node.OfInt truncate(long from, long to, IntFunction<Integer[]> generator) { 362 if (from == 0 && to == count()) 363 return this; 364 long size = to - from; 365 Spliterator.OfInt spliterator = spliterator(); 366 Node.Builder.OfInt nodeBuilder = Nodes.intBuilder(size); 367 nodeBuilder.begin(size); 368 for (int i = 0; i < from && spliterator.tryAdvance((IntConsumer) e -> { }); i++) { } 369 if (to == count()) { 370 spliterator.forEachRemaining((IntConsumer) nodeBuilder); 371 } else { 372 for (int i = 0; i < size && spliterator.tryAdvance((IntConsumer) nodeBuilder); i++) { } 373 } 374 nodeBuilder.end(); 375 return nodeBuilder.build(); 376 } 377 378 @Override newArray(int count)379 default int[] newArray(int count) { 380 return new int[count]; 381 } 382 383 /** 384 * {@inheritDoc} 385 * @implSpec The default in {@code Node.OfInt} returns 386 * {@code StreamShape.INT_VALUE} 387 */ getShape()388 default StreamShape getShape() { 389 return StreamShape.INT_VALUE; 390 } 391 } 392 393 /** 394 * Specialized {@code Node} for long elements 395 */ 396 interface OfLong extends OfPrimitive<Long, LongConsumer, long[], Spliterator.OfLong, OfLong> { 397 398 /** 399 * {@inheritDoc} 400 * 401 * @param consumer A {@code Consumer} that is to be invoked with each 402 * element in this {@code Node}. If this is an 403 * {@code LongConsumer}, it is cast to {@code LongConsumer} so 404 * the elements may be processed without boxing. 405 */ 406 @Override forEach(Consumer<? super Long> consumer)407 default void forEach(Consumer<? super Long> consumer) { 408 if (consumer instanceof LongConsumer) { 409 forEach((LongConsumer) consumer); 410 } 411 else { 412 if (Tripwire.ENABLED) 413 Tripwire.trip(getClass(), "{0} calling Node.OfLong.forEachRemaining(Consumer)"); 414 spliterator().forEachRemaining(consumer); 415 } 416 } 417 418 /** 419 * {@inheritDoc} 420 * 421 * @implSpec the default implementation invokes {@link #asPrimitiveArray()} 422 * to obtain a long[] array then and copies the elements from that 423 * long[] array into the boxed Long[] array. This is not efficient and 424 * it is recommended to invoke {@link #copyInto(Object, int)}. 425 */ 426 @Override copyInto(Long[] boxed, int offset)427 default void copyInto(Long[] boxed, int offset) { 428 if (Tripwire.ENABLED) 429 Tripwire.trip(getClass(), "{0} calling Node.OfInt.copyInto(Long[], int)"); 430 431 long[] array = asPrimitiveArray(); 432 for (int i = 0; i < array.length; i++) { 433 boxed[offset + i] = array[i]; 434 } 435 } 436 437 @Override truncate(long from, long to, IntFunction<Long[]> generator)438 default Node.OfLong truncate(long from, long to, IntFunction<Long[]> generator) { 439 if (from == 0 && to == count()) 440 return this; 441 long size = to - from; 442 Spliterator.OfLong spliterator = spliterator(); 443 Node.Builder.OfLong nodeBuilder = Nodes.longBuilder(size); 444 nodeBuilder.begin(size); 445 for (int i = 0; i < from && spliterator.tryAdvance((LongConsumer) e -> { }); i++) { } 446 if (to == count()) { 447 spliterator.forEachRemaining((LongConsumer) nodeBuilder); 448 } else { 449 for (int i = 0; i < size && spliterator.tryAdvance((LongConsumer) nodeBuilder); i++) { } 450 } 451 nodeBuilder.end(); 452 return nodeBuilder.build(); 453 } 454 455 @Override newArray(int count)456 default long[] newArray(int count) { 457 return new long[count]; 458 } 459 460 /** 461 * {@inheritDoc} 462 * @implSpec The default in {@code Node.OfLong} returns 463 * {@code StreamShape.LONG_VALUE} 464 */ getShape()465 default StreamShape getShape() { 466 return StreamShape.LONG_VALUE; 467 } 468 } 469 470 /** 471 * Specialized {@code Node} for double elements 472 */ 473 interface OfDouble extends OfPrimitive<Double, DoubleConsumer, double[], Spliterator.OfDouble, OfDouble> { 474 475 /** 476 * {@inheritDoc} 477 * 478 * @param consumer A {@code Consumer} that is to be invoked with each 479 * element in this {@code Node}. If this is an 480 * {@code DoubleConsumer}, it is cast to {@code DoubleConsumer} 481 * so the elements may be processed without boxing. 482 */ 483 @Override forEach(Consumer<? super Double> consumer)484 default void forEach(Consumer<? super Double> consumer) { 485 if (consumer instanceof DoubleConsumer) { 486 forEach((DoubleConsumer) consumer); 487 } 488 else { 489 if (Tripwire.ENABLED) 490 Tripwire.trip(getClass(), "{0} calling Node.OfLong.forEachRemaining(Consumer)"); 491 spliterator().forEachRemaining(consumer); 492 } 493 } 494 495 // 496 497 /** 498 * {@inheritDoc} 499 * 500 * @implSpec the default implementation invokes {@link #asPrimitiveArray()} 501 * to obtain a double[] array then and copies the elements from that 502 * double[] array into the boxed Double[] array. This is not efficient 503 * and it is recommended to invoke {@link #copyInto(Object, int)}. 504 */ 505 @Override copyInto(Double[] boxed, int offset)506 default void copyInto(Double[] boxed, int offset) { 507 if (Tripwire.ENABLED) 508 Tripwire.trip(getClass(), "{0} calling Node.OfDouble.copyInto(Double[], int)"); 509 510 double[] array = asPrimitiveArray(); 511 for (int i = 0; i < array.length; i++) { 512 boxed[offset + i] = array[i]; 513 } 514 } 515 516 @Override truncate(long from, long to, IntFunction<Double[]> generator)517 default Node.OfDouble truncate(long from, long to, IntFunction<Double[]> generator) { 518 if (from == 0 && to == count()) 519 return this; 520 long size = to - from; 521 Spliterator.OfDouble spliterator = spliterator(); 522 Node.Builder.OfDouble nodeBuilder = Nodes.doubleBuilder(size); 523 nodeBuilder.begin(size); 524 for (int i = 0; i < from && spliterator.tryAdvance((DoubleConsumer) e -> { }); i++) { } 525 if (to == count()) { 526 spliterator.forEachRemaining((DoubleConsumer) nodeBuilder); 527 } else { 528 for (int i = 0; i < size && spliterator.tryAdvance((DoubleConsumer) nodeBuilder); i++) { } 529 } 530 nodeBuilder.end(); 531 return nodeBuilder.build(); 532 } 533 534 @Override newArray(int count)535 default double[] newArray(int count) { 536 return new double[count]; 537 } 538 539 /** 540 * {@inheritDoc} 541 * 542 * @implSpec The default in {@code Node.OfDouble} returns 543 * {@code StreamShape.DOUBLE_VALUE} 544 */ getShape()545 default StreamShape getShape() { 546 return StreamShape.DOUBLE_VALUE; 547 } 548 } 549 } 550