[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openjdk-lambda-spec-observers
Subject:    Encounter order
From:       Paul Sandoz <paul.sandoz () oracle ! com>
Date:       2013-01-29 17:12:03
Message-ID: 678009ED-739F-4E4D-B5C4-33D148A93C98 () oracle ! com
[Download RAW message or body]

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=


[prev in list] [next in list] [prev in thread] [next in thread]