Encounter order

[Paul Sandoz]

Hi,

This patch is a speculative attempt at introducing an encounter order flag:

  http://cr.openjdk.java.net/~psandoz/lambda/eorder/webrev/

Encounter order is a generalisation, defined by Brian, of what Guy Steel refers to as spatial order in some of his excellent talks i have viewed online.

If an input to the pipeline has an encounter order then one may expect the output to have some correlation to that order, depending on the operations that are performed e.g.:

  List in = ...
  List out = l.parallel().map(...).into(new ArrayList<>());

Some operations inject encounter order, such as sorted, but any intermediate stateful operation that is evaluated in parallel also injects encounter order, which may or may not be considered important for processing by further operations downstream.

This flag is likely only relevant for parallel evaluation. 

An intermediate stateful operation or a terminal operation might choose a different algorithm based on whether encounter order needs to be preserved or not, for example the GroupByOp.evaluateParallel does not currently preserve encounter order for the grouped elements, but it could be easily modified to switch to an algorithm that does.

Preserving encounter order is likely to be important when the terminal operation is Stream.reduce/reduceBy that takes an associative combining function. Arguably it might be a warning/error for the input to reduce/reduceBy to not have a known encounter order if we assume by default the combining function is associative, rather than associative and commutative.

--

I am not sure of the intent of java.util.streams.Streams. Is this class intended for public or internal use? Methods such as the following exposed as part of the public API are asking for trouble:

    public static<T> Stream<T> stream(Collection<T> source, int flags) {

    public static<T> Stream<T> stream(Traversable<T> source, int sizeOrUnknown)

    public static<T> Stream<T> stream(Traversable<T> source, int sizeOrUnknown, int flags)

Where as if they are just used internally to hide details of the Stream implementation then i think they are OK.

Paul.