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