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