changeset 7807:68138df9be76

package-info doc updates, incorporating comments from David H
author briangoetz
date Wed, 03 Apr 2013 18:19:56 -0400
parents 2ffb91b59273
children f7345843a1d6
files src/share/classes/java/util/stream/package-info.java
diffstat 1 files changed, 365 insertions(+), 294 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/stream/package-info.java	Wed Apr 03 16:12:46 2013 -0400
+++ b/src/share/classes/java/util/stream/package-info.java	Wed Apr 03 18:19:56 2013 -0400
@@ -33,8 +33,8 @@
  * </pre>
  *
  * <p>Here we use {@code blocks}, which might be a {@code Collection}, as a source for a stream,
- * and then perform a filter-map-reduce on the stream to obtain the sum of the weights of the
- * red blocks.
+ * and then perform a filter-map-reduce ({@code sum()} is an example of a {@link #Reduction reduction}
+ * operation) on the stream to obtain the sum of the weights of the red blocks.
  *
  * <p>The key abstraction used in this approach is {@link java.util.stream.Stream}, as well as its primitive
  * specializations {@link java.util.stream.IntStream}, {@link java.util.stream.LongStream},
@@ -59,24 +59,372 @@
  *
  * <h2><a name="StreamPipelines">Stream pipelines</a></h2>
  *
- * <p>Streams are used to create <em>pipelines</em> of operations.  A complete stream pipeline has
- * several components: a source (which may be a {@code Collection}, an array, a generator function,
- * or an IO channel); zero or more <em>intermediate operations</em> such as {@code Stream#filter} or
- * {@code Stream#map}; and a <em>terminal operation</em> such as {@code Stream#forEach}
- * or {@code Stream#reduce}.  Stream operations may take as parameters <em>function values</em>
- * (which are often lambda expressions, but could be method references or objects) which parameterize
- * the behavior of the operation, such as a {@code Predicate} passed to the {@code Stream#filter} method.
+ * <p>Streams are used to create <em>pipelines</em> of {@link #StreamOps operations}.  A
+ * complete stream pipeline has several components: a source (which may be a {@code Collection},
+ * an array, a generator function, or an IO channel); zero or more <em>intermediate operations</em>
+ * such as {@code Stream#filter} or {@code Stream#map}; and a <em>terminal operation</em> such
+ * as {@code Stream#forEach} or {@code Stream#reduce}.  Stream operations may take as parameters
+ * <em>function values</em> (which are often lambda expressions, but could be method references
+ * or objects) which parameterize the behavior of the operation, such as a {@code Predicate}
+ * passed to the {@code Stream#filter} method.
  *
- * <p>Intermediate operations return a new {@code Stream}.  They are lazy; executing an intermediate
- * operation such as {@code Stream#filter} does not actually perform any filtering, instead creating a new
- * {@code Stream} that, when traversed, contains the elements of the initial {@code Stream} that match the
- * given {@code Predicate}.  Consuming elements from the stream source does not begin until the terminal
- * operation is executed.
+ * <p>Intermediate operations return a new {@code Stream}.  They are lazy; executing an
+ * intermediate operation such as {@code Stream#filter} does not actually perform any filtering,
+ * instead creating a new {@code Stream} that, when traversed, contains the elements of the
+ * initial {@code Stream} that match the given {@code Predicate}.  Consuming elements from the
+ * stream source does not begin until the terminal operation is executed.
  *
- * <p>Terminal operations consume the {@code Stream} and produce a result or a side-effect.  After a terminal
- * operation is performed, the stream can no longer be used.
+ * <p>Terminal operations consume the {@code Stream} and produce a result or a side-effect.
+ * After a terminal operation is performed, the stream can no longer be used and you must
+ * return to the data source, or select a new data source, to get a new stream. For example,
+ * obtaining the sum of weights of all red blocks, and then of all blue blocks, requires a
+ * filter-map-reduce on two different streams:
+ * <pre>
+ *     int sumOfRedWeights  = blocks.stream().filter(b -> b.getColor() == RED)
+ *                                           .mapToInt(b -> b.getWeight())
+ *                                           .sum();
+ *     int sumOfBlueWeights = blocks.stream().filter(b -> b.getColor() == BLUE)
+ *                                           .mapToInt(b -> b.getWeight())
+ *                                           .sum();
+ * </pre>
  *
- * <h3><a name="StreamSources">Stream sources</a></h3>
+ * <p>However, there are other techniques that allow you to obtain both results in a single
+ * pass if multiple traversal is impractical or inefficient.  TODO provide link
+ *
+ * <h3><a name="StreamOps">Stream operations</a></h3>
+ *
+ * <p>Intermediate stream operation (such as {@code filter} or {@code sorted}) always produce a
+ * new {@code Stream}, and are always<em>lazy</em>.  Executing a lazy operations does not
+ * trigger processing of the stream contents; all processing is deferred until the terminal
+ * operation commences.  Processing streams lazily allows for significant efficiencies; in a
+ * pipeline such as the filter-map-sum example above, filtering, mapping, and addition can be
+ * fused into a single pass, with minimal intermediate state.  Laziness also enables us to avoid
+ * examining all the data when it is not necessary; for operations such as "find the first
+ * string longer than 1000 characters", one need not examine all the input strings, just enough
+ * to find one that has the desired characteristics.  (This behavior becomes even more important
+ * when the input stream is infinite and not merely large.)
+ *
+ * <p>Intermediate operations are further divided into <em>stateless</em> and <em>stateful</em>
+ * operations.  Stateless operations retain no state from previously seen values when processing
+ * a new value; examples of stateless intermediate operations include {@code filter} and
+ * {@code map}.  Stateful operations may incorporate state from previously seen elements in
+ * processing new values; examples of stateful intermediate operations include {@code distict}
+ * and {@code sorted}.  Stateful operations may need to process the entire input before
+ * producing a result; for example, one cannot produce any results from sorting a stream until
+ * one has seen all elements of the stream.  As a result, under parallel computation, some
+ * pipelines containing stateful intermediate operations have to be executed in multiple passes.
+ * Pipelines containing exclusively stateless intermediate operations can be processed in a
+ * single pass, whether sequential or parallel.
+ *
+ * <p>Further, some operations are deemed <em>short-circuiting</em> operations.  An intermediate
+ * operation is short-circuiting if, when presented with infinite input, it may produce a
+ * finite stream as a result.  A terminal operation is short-circuiting if, when presented with
+ * infinite input, it may terminate in finite time.  (Having a short-circuiting operation is a
+ * necessary, but not sufficient, condition for the processing of an infinite stream to
+ * terminate normally in finite time.)
+ *
+ * Terminal operations (such as {@code forEach} or {@code findFirst}) are always eager
+ * (they execute completely before returning), and produce a non-{@code Stream} result, such
+ * as a primitive value or a {@code Collection}, or have side-effects.
+ *
+ * <h3>Parallelism</h3>
+ *
+ * <p>By recasting aggregate operations as a pipeline of operations on a stream of values, many
+ * aggregate operations can be more easily parallelized.  A {@code Stream} can execute either
+ * in serial or in parallel.  When streams are created, they are either created as sequential
+ * or parallel streams; the parallel-ness of streams can also be switched by the
+ * {@link java.util.stream Stream#sequential()} and {@link java.util.stream.Stream#parallel()}
+ * operations.  The {@code Stream} implementations in the JDK create serial streams unless
+ * parallelism is explicitly requested.  For example, {@code Collection} has methods
+ * {@link java.util.Collection#stream} and {@link java.util.Collection#parallelStream},
+ * which produce sequential and parallel streams respectively; other stream-bearing methods
+ * such as {@link java.util.stream.Streams#intRange(int, int)} produce sequential
+ * streams but these can be efficiently parallelized by calling {@code parallel()} on the
+ * result. The set of operations on serial and parallel streams is identical. To execute the
+ * "sum of weights of blocks" query in parallel, we would do:
+ *
+ * <pre>
+ *     int sumOfWeights = blocks.parallelStream().filter(b -> b.getColor() == RED)
+ *                                               .mapToInt(b -> b.getWeight())
+ *                                               .sum();
+ * </pre>
+ *
+ * <p>The only difference between the serial and parallel versions of this example code is
+ * the creation of the initial {@code Stream}.  Whether a {@code Stream} will execute in serial
+ * or parallel can be determined by the {@code Stream#isParallel} method.  When the terminal
+ * operation is initiated, the entire stream pipeline is either executed sequentially or in
+ * parallel, determined by the last operation that affected the stream's serial-parallel
+ * orientation (which could be the stream source, or the {@code sequential()} or
+ * {@code parallel()} methods.)
+ *
+ * <p>In order for the results of parallel operations to be deterministic and consistent with
+ * their serial equivalent, the function values passed into the various stream operations should
+ * be <a href="#NonInteference"><em>stateless</em></a>.
+ *
+ * <h3><a name="Ordering">Ordering</a></h3>
+ *
+ * <p>Streams may or may not have an <em>encounter order</em>.  Whether or not there is an
+ * encounter order depends on the source, the intermediate operations, and the terminal
+ * operation.  Certain stream sources (such as {@code List} or arrays) are intrinsically ordered,
+ * whereas others (such as {@code HashSet}) are not.  Some intermediate operations may impose
+ * an encounter order on an otherwise unordered stream, such as
+ * {@link java.util.stream.Stream#sorted()}.  Some intermediate operations may remove the
+ * constraint of ordering, rendering unordered a previously ordered stream.  Finally, some
+ * terminal operations may ignore encounter order, such as {@link java.util.stream.Stream#forEach},
+ * and others may have optimized implementations for the case where there is no defined
+ * encounter order.
+ *
+ * <p>If a Stream is ordered, most operations are constrained to operate on the elements in their
+ * encounter order; if the source of a stream is a {@code List} containing {@code [1, 2, 3]},
+ * then the result of executing {@code map(x -> x*2)} must be {@code [2, 4, 6]}.  However, if
+ * the source has no defined encounter order, than any permutation of the values {@code [2, 4, 6]}
+ * would be a valid result. Many operations can still be efficiently parallelized even under
+ * ordering constraints, but some (such as duplicate removal) may be more efficient without
+ * ordering constraints.
+ *
+ * TODO Interaction between ordering and concurrency
+ *
+ * <h2><a name="Non-Interference">Non-interference</h2>
+ *
+ * The {@code java.util.stream} package enables you to execute possibly-parallel
+ * bulk-data operations over a variety of data sources, including even non-thread-safe
+ * collections such as {@code ArrayList}.  This is possible only if we can
+ * prevent <em>interference</em> with the data source during the execution of a
+ * stream pipeline.  (Execution begins when the terminal operation is invoked, and ends
+ * when the terminal operation completes.)  For most data sources, preventing interference
+ * means ensuring that the data source is <em>not modified at all</em> during the execution
+ * of the stream pipeline.  (Some data sources, such as concurrent collections, are
+ * specifically designed to handle concurrent modification.)
+ *
+ * <p>Accordingly, lambda expressions (or other objects implementing the appropriate functional
+ * interface) passed to stream methods should never modify the stream's data source.  An
+ * implementation is said to <em>interfere</em> with the data source if it modifies, or causes
+ * to be modified, the stream's data source.  The need for non-interference applies to all
+ * pipelines, not just parallel ones.  Unless the stream source is concurrent, modifying a
+ * stream's data source during execution of a stream pipeline can cause exceptions, incorrect
+ * answers, or nonconformant results.
+ *
+ * <p>Further, results may be nondeterministic or incorrect if the lambda expressions passed to
+ * stream operations are <em>stateful</em>.  A stateful lambda (or other object implementing the
+ * appropriate functional interface) is one whose result depends on any state which might change
+ * during the execution of the stream pipeline.  An example of a stateful lambda is:
+ * <pre>
+ *     Set<Integer> seen = Collections.synchronizedSet(new HashSet<>());
+ *     stream.parallel().map(e -> { if (seen.add(e)) return 0; else return e; })...
+ * </pre>
+ * Here, if the mapping operation us performed in parallel, the results for the same input
+ * could vary from run to run, due to thread scheduling differences, whereas, with a stateless
+ * lambda expression the results would always be the same.
+ *
+ * <h2>Side-effects</h2>
+ *
+ * <h2><a name="Reduction">Reduction operations</h2>
+ *
+ * A <em>reduction</em> operation takes a stream of elements and processes them in a way
+ * that reduces to a single value or summary description, such as finding the sum or maximum
+ * of a set of numbers.  (In more complex scenarios, the reduction operation might need to
+ * extract data from the elements before reducing that data to a single value, such as
+ * finding the sum of weights of a set of blocks.  This would require extracting the weight
+ * from each block before summing up the weights.)
+ *
+ * <p>Of course, such operations can be readily implemented as simple sequential loops, as in:
+ * <pre>
+ *    int sum = 0;
+ *    for (int x : numbers) {
+ *       sum += x;
+ *    }
+ * </pre>
+ * However, there may be a significant advantage to preferring a {@link Stream#reduce reduce operation}
+ * over a mutative accumulation such as the above -- a properly constructed reduce operation is
+ * inherently parallelizable, so long as the {@link BinaryOperator} has the right characteristics,
+ * specifically that it is <a href="#Associativity">associative</a>.  For example, given a
+ * stream of numbers for which we want to find the sum, we can write:
+ * <pre>
+ *    int sum = numbers.reduce(0, (x,y) -> x+y);
+ * </pre>
+ * or more succinctly:
+ * <pre>
+ *    int sum = numbers.reduce(0, Integer::sum);
+ * </pre>
+ *
+ * <p>(The primitive specializations of {@link java.util.stream.Stream}, such as
+ * {@link java.util.stream.IntStream}, even have convenience methods for common reductions,
+ * such as {@link java.util.stream.IntStream#sum()} or {@link java.util.stream.IntStream#max()},
+ * which are implemented as simple wrappers around reduce.)
+ *
+ * <p>Reduction parallellizes well since the implementation of {@code reduce} can operate on
+ * subsets of the stream in parallel, and then combine the intermediate results to get the final
+ * correct answer.  Even if you were to use a parallelizable form of the {@link forEach} method
+ * in place of the original for-each loop above, you would still have to provide thread-safe
+ * updates to the shared accumulating variable {@code sum}, and the required synchronization
+ * would likely eliminate any performance gain from parallelism. Using a {@code reduce} method
+ * instead removes all of the burden of parallelizing the reduction operation, and the library
+ * can provide an efficient parallel implementation with no additional synchronization needed.
+ *
+ * <p>The "blocks" examples shown earlier shows how reduction combines with other operations
+ * to replace for loops with bulk operations.  If {@code blocks} is a collection of {@code Block}
+ * objects, which have a {@code getWeight} method, we can find the heaviest block with:
+ * <pre>
+ *     OptionalInt heaviest = blocks.stream()
+ *                                  .mapToInt(Block::getWeight)
+ *                                  .reduce(Integer::max);
+ * </pre>
+ *
+ * <p>In its more general form, a {@code reduce} operation on elements of type {@code T}
+ * yielding a result of type {@code U} requires three parameters:
+ * <pre>
+ * &lt;U> U reduce(U identity,
+ *                 BiFunction&lt;U, ? super T, U> accumlator,
+ *                 BinaryOperator&lt;U> combiner);
+ * </pre>
+ * Here, the <em>identity</em> element is both an initial seed for the reduction, and a default
+ * result if there are no elements. The <em>accumulator</em> function takes a partial result and
+ * the next element, and produce a new partial result. The <em>combiner</em> function combines
+ * the partial results of two accumulators to produce a new partial result, and eventually the
+ * final result.
+ *
+ * <p>This form is a generalization of the two-argument form, and is also a generalization of
+ * the map-reduce construct illustrated above.  If we wanted to re-cast the simple {@code sum}
+ * example using the more general form, {@code 0} would be the identity element, while
+ * {@code Integer::sum} would be both the accumulator and combiner. For the sum-of-weights
+ * example, this could be re-cast as:
+ * <pre>
+ *     int sumOfWeights = blocks.stream().reduce(0,
+ *                                               (sum, b) -> sum + b.getWeight())
+ *                                               Integer::sum);
+ * </pre>
+ * though the map-reduce form is more readable and generally preferable.  The generalized form
+ * is provided for cases where significant work can be optimized away by combining mapping and
+ * reducing into a single function.
+ *
+ * <p>More formally, the {@code identity} value must be an <em>identity</em> for the combiner
+ * function. This means that for all {@code u}, {@code combiner.apply(identity, u)} is equal
+ * to {@code u}. Additionally, the {@code combiner} function must be
+ * <a href="#Associativity">associative</a> and must be compatible with the {@code accumulator}
+ * function; for all {@code u} and {@code t}, the following must hold:
+ * <pre>
+ *     combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)
+ * </pre>
+ *
+ * <h3><a name="MutableReduction">Mutable Reduction</a></h3>
+ *
+ * A <em>mutable</em> reduction operation is similar to an ordinary reduction, in that it reduces
+ * a stream of values to a single value, but instead of producing a distinct single-valued result, it
+ * mutates a general <em>result container</em>, such as a {@code Collection} or {@code StringBuilder},
+ * as it processes the elements in the stream.
+ *
+ * <p>For example, if we wanted to take a stream of strings and concatenate them into a single
+ * long string, we <em>could</em> achieve this with ordinary reduction:
+ * <pre>
+ *     String concatenated = strings.reduce("", String::concat)
+ * </pre>
+ *
+ * We would get the desired result, and it would even work in parallel.  However, we might not
+ * be happy about the performance!  Such an implementation would do a great deal of string
+ * copying, and the run time would be <em>O(n^2)</em> in the number of elements.  A more
+ * performant approach would be to accumulate the results into a {@link StringBuilder}, which
+ * is a mutable container for accumulating strings.  We can use the same technique to
+ * parallelize mutable reduction as we do with ordinary reduction.
+ *
+ * </p>The mutable reduction operation is called {@link Stream#collect collect}, as it
+ * collects together the desired results into a result container such as {@code StringBuilder}.
+ * A {@code collect} operation requires three things: a factory function which will construct
+ * new instances of the result container, an accumulating function that will update a result
+ * container by incorporating a new element, and a combining function that can take two
+ * result containers and merge their contents.  The form of this is very similar to the general
+ * form of ordinary reduction:
+ * <pre>
+ * &lt;R> R collect(Supplier&lt;R> resultFactory,
+ *                  BiConsumer&lt;R, ? super T> accumulator,
+ *                  BiConsumer&lt;R, R> combiner);
+ * </pre>
+ * As with {@code reduce()}, the benefit of expressing {@collect} in this abstract way is
+ * that it is directly amenable to parallelization: we can accumulate partial results in parallel
+ * and then combine them.  For example, to collect the string representations of the elements
+ * in a stream into an {@code ArrayList}, we could write the obvious sequential for-each form:
+ * <pre>
+ *     ArrayList&lt;String> strings = new ArrayList&lt;>();
+ *     for (T element : stream) {
+ *         strings.add(element.toString());
+ *     }
+ * </pre>
+ * Or we could use a parallelizable collect form:
+ * <pre>
+ *     ArrayList&lt;String> strings = stream.collect(() -> new ArrayList&lt;>(),
+ *                                                   (c, e) -> c.add(e.toString()),
+ *                                                   (c1, c2) -> c1.addAll(c2));
+ * </pre>
+ * or, noting that we have buried a mapping operation inside the accumlator function, more
+ * succinctly as:
+ * <pre>
+ *     ArrayList&lt;String> strings = stream.map(Object::toString)
+ *                                          .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
+ * </pre>
+ * Here, our supplier is just the {@link ArrayList#ArrayList() ArrayList constructor}, the
+ * accumulator adds the stringified element to an {@code ArrayList}, and the combiner simply
+ * uses {@link ArrayList#addAll addAll} to copy the strings from one container into the other.
+ *
+ * <p>As with the regular reduction operation, the ability to parallelize only comes if an 
+ * {@link #Associativity associativity} condition is met. The {@code combiner} is associative
+ * if for result containers {@code r1}, {@code r2}, and {@code r3}:
+ * <pre>
+ *    combiner.accept(r1, r2);
+ *    combiner.accept(r1, r3);
+ * </pre>
+ * is equivalent to
+ * <pre>
+ *    combiner.accept(r2, r3);
+ *    combiner.accept(r1, r2);
+ * </pre>
+ * where equivalence means that {@code r1} is left in the same state (according to the meaning
+ * of {@link Object#equals equals} for the element types). Similarly, the {@code resultFactory}
+ * must act as an <em>identity</em> with respect to the {@code combiner} so that for any result
+ * container {@code r}:
+ * <pre>
+ *     combiner.accept(r, resultFactory.get());
+ * </pre>
+ * does not modify the state of {@code r} (again according to the meaning of
+ * {@link Object#equals equals}). Finally, the {@code accumulator} and {@code combiner} must be
+ * compatible such that for a result container {@code r} and element {@code t}:
+ * <pre>
+ *    r2 = resultFactory.get();
+ *    accumulator.accept(r2, t);
+ *    combiner.accept(r, r2);
+ * </pre>
+ * is equivalent to:
+ * <pre>
+ *    accumulator.accept(r,t);
+ * </pre>
+ * where equivalence means that {@code r} is left in the same state (again according to the
+ * meaning of {@link Object#equals equals}).
+ *
+ * <p> The three aspects of {@code collect}: supplier, accumulator, and combiner, are often very
+ * tightly coupled, and it is convenient to introduce the notion of a {@link Collector} as
+ * being an object that embodies all three aspects. There is a {@link Stream#collect(Collector) collect}
+ * method that simply takes a {@code Collector} and returns the resulting container.
+ * The above example for collecting strings into a {@code List} can be rewritten using a
+ * standard {@code Collector} as:
+ * <pre>
+ *     ArrayList&lt;String> strings = stream.map(Object::toString)
+ *                                          .collect(Collectors.toList());
+ * </pre>
+ *
+ * <a name="Associativity"><h2>Associativity</h2></a>
+ *
+ * An operator or function {@code op} is <em>associative</em> if the following holds:
+ * <pre>
+ *     (a op b) op c == a op (b op c)
+ * </pre>
+ * The importance of this to parallel evaluation can be seen if we expand this to four terms:
+ * <pre>
+ *     a op b op c op d == (a op b) op (c op d)
+ * </pre>
+ * So we can evaluate {@code (a op b)} in parallel with {@code (c op d)} and then invoke {@code op} on
+ * the results.
+ * TODO what does associative mean for mutative combining functions?
+ *
+ * TODO where does this section go?
+ * <h2><a name="StreamSources">Stream sources</a></h2>
  *
  * XXX - change to section to stream construction gradually introducing more
  *       complex ways to construct
@@ -134,283 +482,6 @@
  * then a {@code ConcurrentModificationException} will be thrown since the {@code peek} operation will attempt
  * to add the string "BAD LAMBDA" to the list after the terminal operation has commenced.
  *
- * <h3><a name="StreamOps">Stream operations</a></h3>
- *
- * <p>Stream operations are divided into two categories: <em>intermediate</em> and <em>terminal</em>.  An
- * intermediate operation (such as {@code filter} or {@code sorted}) produces a new {@code Stream}; a terminal
- * operation (such as {@code forEach} or {@code findFirst}) produces a non-{@code Stream} result, such as a
- * primitive value or a {@code Collection}.
- *
- * <p>All intermediate operations are <em>lazy</em>, which means that executing a lazy operations does not trigger
- * processing of the stream contents; all processing is deferred until the terminal operation commences.
- * Processing streams lazily allows for significant efficiencies; in a pipeline such as the filter-map-sum
- * example above, filtering, mapping, and addition can be fused into a single pass, with minimal intermediate
- * state.  Laziness also enables us to avoid examining all the data when it is not necessary; for operations such as
- * "find the first string longer than 1000 characters", one need not examine all the input strings, just enough to
- * find one that has the desired characteristics.  (This behavior becomes even more important when the input stream
- * is infinite and not merely large.)
- *
- * <p>Intermediate operations are further divided into <em>stateless</em> and <em>stateful</em> operations.  Stateless
- * operations retain no state from previously seen values when processing a new value; examples of stateless
- * intermediate operations include {@code filter} and {@code map}.  Stateful operations may incorporate state
- * from previously seen elements in processing new values; examples of stateful intermediate operations include
- * {@code distict} and {@code sorted}.  Stateful operations may need to process the entire input before producing a
- * result; for example, one cannot produce any results from sorting a stream until one has seen all elements of the
- * stream.  As a result, under parallel computation, some pipelines containing stateful intermediate operations
- * have to be executed in multiple passes.  Pipelines containing exclusively stateless intermediate operations
- * can be processed in a single pass, whether sequential or parallel.
- *
- * <p>Further, some operations are deemed <em>short-circuiting</em> operations.  An intermediate operation is
- * short-circuiting if, when presented with infinite input, it may produce a finite stream as a result.  A terminal
- * operation is short-circuiting if, when presented with infinite input, it may terminate in finite time.  (Having
- * a short-circuiting operation is a necessary, but not sufficient, condition for the processing of an infinite stream
- * to terminate normally in finite time.)
- *
- * <h3>Parallelism</h3>
- *
- * <p>By recasting aggregate operations as a pipeline of operations on a stream of values, many
- * aggregate operations can be more easily parallelized.  A {@code Stream} can execute either in serial or
- * in parallel.   When streams are created, they are either created as sequential or parallel streams;
- * the parallel-ness of streams can also be modified by the {@link java.util.stream Stream#sequential()} and
- * {@link java.util.stream.Stream#parallel()} operations.  The {@code Stream} implementations in the JDK
- * create serial streams unless parallelism is explicitly requested.  For example,
- * {@code Collection} has methods {@link java.util.Collection#stream}
- * and {@link java.util.Collection#parallelStream}, which produce serial and parallel streams respectively;
- * other stream-bearing methods such as {@link java.util.stream.Streams#intRange(int, int)} produce sequential
- * streams but these can be efficiently parallelized by calling {@code parallel()} on the result.
- * The set of operations on serial and parallel streams is identical.  There are also stream operations
- * {@code Stream#sequential} and {@code Stream#parallel} to convert between sequential and parallel execution.
- * To execute the "sum of weights of blocks" query in parallel, we would do:
- *
- * <pre>
- *     int sumOfWeights = blocks.parallelStream().filter(b -> b.getColor() == RED)
- *                                               .mapToInt(b -> b.getWeight())
- *                                               .sum();
- * </pre>
- *
- * <p>The only difference between the serial and parallel versions of this example code is
- * the creation of the initial {@code Stream}.  Whether a {@code Stream} is serial or parallel
- * can be determined by the {@code Stream#isParallel} method.  When the terminal operation
- * is initiated, the entire stream pipeline is either executed sequentially or in parallel, determined
- * by the last operation that affected the stream's serial-parallel orientation (which could be the
- * stream source, or the {@code sequential()} or {@code parallel()} methods.)
- *
- * <p>In order for the results of parallel operations to be deterministic and consistent with their
- * serial equivalent, the function values passed into the various stream operations should be
- * <a href="#NonInteference"><em>stateless</em></a>.
- *
- * <h3><a name="Ordering">Ordering</a></h3>
- *
- * <p>Streams may or may not have an <em>encounter order</em>.  Whether or not there is an encounter order
- * depends on the source, the intermediate operations, and the terminal operation.  Certain stream sources
- * (such as {@code List} or arrays) are intrinsically ordered, whereas others (such as {@code HashSet}) are
- * not.  Some intermediate operations may impose an encounter order on an otherwise unordered stream, such
- * as {@link java.util.stream.Stream#sorted()}.  Some intermediate operations may remove the constraint of
- * ordering, rendering unorerded an otherwise ordered stream.  Finally, some terminal operations may ignore
- * encounter order, such as {@link java.util.stream.Stream#forEach}, and others may have optimized
- * implementations for the case where there is no defined encounter order.
- *
- * <p>If a Stream is ordered, most operations are constrained to operate on the elements in their
- * encounter order; if the source of a stream is a {@code List} containing {@code [1, 2, 3]}, then the
- * result of executing {@code map(x -> x*2)} must be {@code [2, 4, 6]}.  However, if the source has no
- * defined encounter order, than any permutation of the values {@code [2, 4, 6]} would be a valid result.
- * Many operations can still be efficiently parallelized even under ordering constraints, but some (such
- * as duplicate removal) may be much more efficient without ordering constraints.
- *
- * @@@ Interaction between ordering and concurrency
- *
- * <h2><a name="Non-Interference">Non-interference</h2>
- *
- * The {@code java.util.stream} package enables you to execute possibly-parallel
- * bulk-data operations over a variety of data sources, including even non-thread-safe
- * collections such as {@code ArrayList}.  This is possible only if we can
- * prevent <em>interference</em> with the data source during the execution of a
- * stream pipeline.  (Execution begins when the terminal operation is invoked, and ends
- * when the terminal operation completes.)  For most data sources, preventing interference
- * means ensuring that the data source is <em>not modified at all</em> during the execution
- * of the stream pipeline.  (Some data sources, such as concurrent collections, are
- * specifically designed to handle concurrent modification, in which case their
- * {@code Spliterator} will report the {@code CONCURRENT} characteristic.)
- *
- * <p>Accordingly, lambda expressions (or other object implementing the appropriate functional interface)
- * passed to stream methods should never modify the stream's data source.  An implementation
- * is said to <em>interfere</em> with the data source if it modifies, or causes to be modified,
- * the stream's data source.  The need for non-interference applies to all pipelines, not just parallel
- * ones.  Unless the stream source is concurrent, modifying a stream's data source during
- * execution of a stream pipeline can cause exceptions, incorrect answers, or nonconformant
- * results.
- *
- * <p>Further results may be nondeterministic or incorrect if the lambda expressions passed to
- * stream operations are <em>stateful</em>.  A stateful lambda (or other object implementing the
- * appropriate functional interface) is one whose result depends on any state which might change
- * during the execution of the stream pipeline.  An example of a stateful lambda is:
- * <pre>
- *     Set<Integer> seen = Collections.synchronizedSet(new HashSet<>());
- *     stream.map(e -> { if (seen.add(e)) return 0; else return e; })...
- * </pre>
- * Stream pipelines with stateful lambda expressions may produce nondeterministic or incorrect results.
- *
- * <h2>Side-effects</h2>
- *
- * <h2><a name="Reduction">Reduction operations</h2>
- *
- * In simple terms, a <em>reduction</em> operation takes a stream of elements and processes them in a way
- * that reduces to a single value, such as finding the sum or maximum of a set of numbers. (In more complex
- * scenarios, the reduction operation might need to extract data from the elements before reducing that data
- * to a single value, such as finding the sum of weights of a set of blocks.  This would require extracting the
- * weight from each block before summing up the weights.)
- *
- * <p>Of course, such operations can be readily implemented as simple sequential loops, as in:
- * <pre>
- *    int sum = 0;
- *    for (int x : numbers) {
- *       sum += x;
- *    }
- * </pre>
- * However, there may be a significant advantage to preferring a {@link Stream#reduce reduce operation} over
- * a mutative accumulation such as the above -- a properly constructed reduce operation is inherently parallelizable,
- * so long as the {@link BinaryOperator} has the right characteristics, specifically that it is
- * <a href="#Associativity">associative</a>.  For example, given a stream of numbers for which we want to
- * find the sum, we can write:
- * <pre>
- *    int sum = numbers.reduce(0, (x,y) -> x+y );
- * </pre>
- * or more succinctly:
- * <pre>
- *    int sum = numbers.reduce(0, Integer::sum);
- * </pre>
- *
- * <p>(The primitive specializations of {@link java.util.stream.Stream}, such as {@link java.util.stream.IntStream},
- * even have convenience methods for common reductions, such as {@link java.util.stream.IntStream#sum()} or
- * {@link java.util.stream.IntStream#max()}, which are implemented as wrappers around reduce.)
- *
- * <p>Reduction parallellizes well since the implementation of {@code reduce} can operate on subsets of the
- * stream in parallel, and then combine the intermediate results to get the final correct answer.  Even if you were
- * to use a parallelizable form of the {@link forEach} method in place of the original for-each loop above, you would
- * still have to provide thread-safe updates to the shared accumulating variable {@code sum}, and the required
- * synchronization would likely eliminate any performance gain from parallelism. Using a {@code reduce} method instead
- * removes all of the burden of parallelizing the reduction operation, and the library can provide an efficient
- * parallel implementation.
- *
- * <p>A slightly more complicated example involves applying a transform to data elements before the reduction.
- * If {@code blocks} is a collection of {@code Block} objects, which have a {@code getWeight} method, we can find
- * the sum of the weight of all blocks with:
- * <pre>
- *     int sumOfWeights = blocks.stream()
- *                              .mapToInt(b -> b.getWeight())
- *                              .reduce(0, Integer::sum);
- * </pre>
- *
- * <p>In its more general form, a {@code reduce} operation on elements of type {@code T} yielding a result of
- * type {@code U} requires three parameters:
- * <pre>
- * &lt;U> U reduce(U identity,
- *                 BiFunction&lt;U, ? super T, U> accumlator,
- *                 BinaryOperator&lt;U> combiner);
- * </pre>
- * Here, the <em>identity</em> element is both an initial seed for the reduction, and a default result if
- * there are no elements. The <em>accumulator</em> function takes a partial result and the next element, and
- * produce a new partial result. The <em>combiner</em> function combines the partial results of two
- * accumulators to produce a new partial result, or eventually the final result.
- *
- * <p>This form is a generalization of the two-argument form, and is also a generalization of the map-reduce
- * construct illustrated above.  If we wanted to re-cast the simple {@code sum} example using the more general form,
- * {@code 0} would be the identity element, while {@code Integer::sum} would be both the accumulator and combiner.
- * For the sum-of-weights example, this could be re-cast as:
- * <pre>
- *     int sumOfWeights = blocks.stream().reduce(0,
- *                                               (sum, b) -> sum + b.getWeight())
- *                                               Integer::sum);
- * </pre>
- * though the map-reduce form is more readable and generally preferable.  The generalized form is provided
- * for cases where significant work can be optimized away by combining mapping and reducing into a single
- * function.
- *
- * <p>More formally, the {@code identity} value must be an <em>identity</em> for the combiner function.
- * This means that for all {@code u}, {@code combiner(identity, u)} is equal to {@code u}.
- * Additionally, the {@code combiner} function must be <a href="#Associativity">associative</a> and must be
- * compatible with the {@code accumulator} function; for all {@code u} and {@code t}, the following must hold:
- * <pre>
- *     combiner(u, accumulator(identity, t)) == accumulator(u, t)
- * </pre>
- *
- * <h3><a name="MutableReduction">Mutable Reduction</a></h3>
- *
- * A <em>mutable</em> reduction operation is similar to an ordinary reduction, in that it reduces a stream
- * of values to a single value, but instead of producing a distinct single-valued result, it instead
- * mutates a general <em>result container</em>, such as a {@code Collection} or {@code StringBuilder}, as it
- * processes the the elements in the stream.
- *
- * <p>If we wanted to take a stream of strings and concatenate them into a single long string, we <em>could</em>
- * achieve this with ordinary reduction:
- * <pre>
- *     String concatenated = strings.reduce("", String::concat)
- * </pre>
- *
- * We would get the desired result, and it would even work in parallel.  However, we might not be happy about
- * the performance!  Such an implementation would do a great deal of string copying, and the run time would be
- * <em>O(n^2)</em> in the number of elements.  A more performant approach would be to accumulate the results into
- * a {@link StringBuilder}, which is a mutable container for accumulating strings.  We can use the same technique
- * to parallelize mutable reduction as we do with ordinary reduction.
- *
- * </p>The mutable reduction operation is generally referred to as {@link Stream#collect collect}, as it collects
- * together the desired results into a result container such as {@code StringBuilder}.  A {@code collect} operation
- * requires three things: a factory function which will construct new instances of the result container, an
- * accumulating function that will update a result container by incorporating a new element, and a combining function
- * that can take two result containers and merge their contents.  The form of this is very similar to the general
- * form of ordinary reduction:
- * <pre>
- * &lt;R> R collect(Supplier&lt;R> resultFactory,
- *                  BiConsumer&lt;R, ? super T> accumulator,
- *                  BiConsumer&lt;R, R> combiner);
- * </pre>
- * As with {@code reduce()}, the benefit of expressing {@collect} in this abstract way is that it is directly
- * amenable to parallelization: we can accumulate partial results in parallel and then combine them.  For example,
- * to collect the string representations of the elements in a stream into an {@code ArrayList}, we
- * could write the obvious sequential for-each form:
- * <pre>
- *     ArrayList&lt;String> strings = new ArrayList&lt;>();
- *     for (T element : stream) {
- *         strings.add(element.toString());
- *     }
- * </pre>
- * Or we could use a parallelizable collect form:
- * <pre>
- *     ArrayList&lt;String> strings = stream.collect(() -> new ArrayList&lt;>(),
- *                                                   (c, e) -> c.add(e.toString()),
- *                                                   (c1, c2) -> c1.addAll(c2));
- * </pre>
- * or more succinctly:
- * <pre>
- *     ArrayList&lt;String> strings = stream.map(Object::toString)
- *                                          .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
- * </pre>
- * Here, our supplier is just the {@link ArrayList#ArrayList() ArrayList constructor}, the accumulator adds
- * the stringified element to an {@code ArrayList}, and the combiner simply uses {@link ArrayList#addAll addAll}
- * to copy the strings from one container into the other. As with the regular reduction operation, the ability to
- * parallelize only comes if an associativity condition are met.
- *
- * <p> The three aspects of {@code collect}: supplier, accumulator, and combiner, are often very tightly coupled, and
- * it is convenient to introduce the notion of a {@link Collector} as being an object that embodies all three aspects.
- * There is a {@link Stream#collect(Collector) collect} method that simply takes a {@code Collector} and returns
- * the resulting container.  The above example for collecting strings into a {@code List} can be written as:
- * <pre>
- *     ArrayList&lt;String> strings = stream.map(Object::toString)
- *                                          .collect(Collectors.toList());
- * </pre>
- *
- * <a name="Associativity"><h2>Associativity</h2></a>
- *
- * An operator or function {@code op} is <em>associative</em> if the following holds:
- * <pre>
- *     (a op b) op c == a op (b op c)
- * </pre>
- * The importance of this to parallel evaluation can be seen if we expand this to four terms:
- * <pre>
- *     a op b op c op d == (a op b) op (c op d)
- * </pre>
- * So we can evaluate {@code (a op b)} in parallel with {@code (c op d)} and then invoke {@code op} on
- * the results.
  *
  */