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