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