Encounter order

[Paul Sandoz]

Hi,

Below is description of encounter order for the Streams API.

The implementation in the lambda repo currently conforms to this documentation although it is not implemented exactly as described.

Paul.

--

A source has or does not have encounter order.
List and arrays are sources that have encounter order (arrays can be said to also have a spatial order).
HashSet is a source that does not have encounter order (another example is PriorityQueue).

A terminal operation preserves or does not preserve encounter order when producing a result.
Non-preserving terminal operations are forEach, forEachUntil, findAny, match{Any, None, All}, collect(toHashSet()) and
collectUnordered.

An intermediate operation may inject encounter order down-stream.
The sorted() operation injects encounter order when the natural comparator is used to sort elements.

An intermediate operation may clear encounter order down-stream.
There are no such operations implemented. 
(Previously the unordered() operation cleared encounter order.)

Otherwise an intermediate operation must preserve encounter order if required to do so (see next paragraphs).

An intermediate operation may choose to apply a different algorithm if encounter order of the elements output from the intermediate operation must be preserved or not.
The distinct() operation will, when evaluating in parallel, use a ConcurrentHashMap to store unique elements if encounter order does not need to be preserved, otherwise if encounter order needs to be preserved a fold will be performed (equivalent of, in parallel, map each element to a singleton set then associatively reduce the sets to one set).

An intermediate operation should preserve encounter order of the output elements if:

a.1) the upstream elements input to the intermediate operation has an encounter order (either because the source has encounter order or because an upstream operation injected encounter order); and
a.2) the terminal operation preserves encounter order.

An intermediate operation does not need to preserve encounter order of the output elements if:

b.1) the upstream elements input to the intermediate operation has no encounter order (either because the source has no encounter order or because an upstream operation cleared encounter order); or
b.2) the terminal operation does not preserve encounter order *and* the intermediate operation is in a sequence of operations, to be evaluated, where the last operation in the sequence is the terminal operation and all operations in the sequence are evaluated in parallel.

Rule b.2 above ensures that for the following pipeline encounter order is preserved on the sequential forEach:

list.parallelStream().distinct().sequential().forEach()

i.e. the distinct() operation will preserve the encounter order of the list