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