Substream applied to unordered streams

[Brian Goetz]

I haven't yet determined whether we want to commit to stable sorting. 
But I think we probably do not.  Stability is a relatively cheap 
property to preserve in a sequential sort (which is why Arrays.sort is 
spec'ed as stable), but a relatively expensive property to preserve in 
an parallel sort, and this moves the balance of whether stability is 
worth the cost.

So I would say the answer is likely to be: "stream sorts are not 
guaranteed stable at all", though you might get stability by accident 
with some sequential streams.

On 3/16/2013 4:43 PM, Georgiy Rakov wrote:
>
> On 15.03.2013 22:45, Brian Goetz wrote:
>>> it seems that 'limit' and 'substream' methods applied to unordered
>>> stream return result which seems to be only partially deterministic.
>>
>> Right, which makes sense.  substream (and by extension limit) are
>> defined in terms of encounter order; if the encounter order is merely
>> accidental, as it is in an unordered stream, there's not much we can
>> do there.
>>
>>> Similar thing is true for 'sorted' method provided stream contains equal
>>> elements and 'sorted' uses algorithm preserving order.
>>
>> I think you're asking whether sorting is stable (for ordered streams)
>> or not?
>>
>
> Pardon me, yes I meant "stable sorting",
> I meant that 'sorted' result becomes a bit more nondetermenistic for
> unordered streams provided they contain equal elements and 'sorted' uses
> stable sorting; actually stable sorting turns into unstable sorting (of
> course if sorting was stable originally).
>
> In general I asked whether you see useful to show these points in spec,
> e. g. if spec contains something like:
>
>     You should keep in mind that substream() could return stream which
>     content is nondeterministic provided original stream encounter order
>     is not defined, e.g. for stream returned from HashSet instance.
>
> and for "sorted":
>
>     You should keep in mind that sorting becomes actually unstable when
>     applied to unordered stream.
>
> The later only makes sense if "sorted()" uses stable sort, if it uses
> non stable sorting nothing changes for unordered streams.
>
> And the question you mentioned above is relevant as well - I would
> appreciate greatly if you tell whether "sorted()" uses stable sorting.
>
> Thank you,
> Georgiy.