Encounter order

[Brian Goetz]

> As I discussed on IM with Brian yesterday it doesn't make sense to ask
> what properties the parallel() stream has. parallel() in and of itself
> does not preserve or mutate order. The question is what does
> parallel().op() do - and that depends both on the op() and what entity
> you applied parallel() to.

Right.  The implementation maintains a set of flags describing 
properties of the source, such as "has encounter order", "is infinite", 
"is sorted by natural order", "is distinct", etc.  Similarly, each op 
has a a set of corresponding flag modifiers, of the form
   ({sets, clears, preserves }, flag)

So map() preserves size and encounter order, sort injects encounter 
order and sortedness, filter preserves order but not size, etc.

> For some ops like sum(), max() (the commutative ones) it doesn't matter
> how you implement them (serial, parallel) the result is always the same
> - given the input there is only one possible answer.

True.  Though we don't have sum(), min(), max() on Stream -- because we 
don't know enough about the (erased) type parameter to know whether the 
thing is summable, maxable, etc.  So instead we have 
reduce(BinaryOperator).  The argument to reduce is traditionally assumed 
to be associative but not commutative.

> For other ops, like findAny, there may be multiple possible answers, so
> the result is a function of both the input data and the algorithm used
> to locate it - hence a parallel implementation may not only produce a
> different result to a serial implementation, it may produce a different
> result each time it is executed.

Correct.

> My concern with all this is that when writing the specification for
> SomeClass.op we have to understand what actions can precede it in the
> pipeline and how they affect the semantics that op provides.

I don't think so.  Instead, it only has to be a function of the known 
upstream flags alluded to above.  Which is a lot easier.  So, findFirst 
can say something about what it does if the stream has no defined 
encounter order, but need not address the combinatorial explosion of 
ways a stream might find itself lacking such an order.