Natural Encounter Order (was RE: Stream#generate() vs. iterate())

[Millies, Sebastian]

Thanks for that information. Part of my confusion may be just a language thing. I'd call the property
of having a first, second etc. element "indexed", not "ordered". In German, "ordered" is more akin to
"sorted". (But perhaps even in English, cf. SQL ORDER BY clause?).

For that reason, I'd not have expected to have to unorder() a stream that had never been
explicitly sort() 'ed. 

Or in other words, I'd have expected sorted()/unordered() and sequential()/parallel() to
be pairs of operations that converted along the two dimensions, with "unordered sequential" always
the default unless explicitly coded otherwise.

Setting aside the choice of words, is there some rigorous definition of "natural encounter order" that
will let me know whether a stream will in fact be ordered or unordered when I create it?
Consider the following:

        TreeSet<String> t = new TreeSet<>();
        HashSet<String> h = new HashSet<>();
        Set<String> s;

        s = t;
        Stream<String> tStream = s.parallelStream();
        assert(tStream.spliterator().hasCharacteristics(Spliterator.ORDERED)) ;

        s = h;
        Stream<String> hStream = s.parallelStream();
        assert( ! hStream.spliterator().hasCharacteristics(Spliterator.ORDERED));

Usually having a Set reference I will not know whether the object has been created 
a TreeSet or HashSet. Similarly, having a Map.EntrySet I will usually not know whether the
underlying Map was a LinkedHashMap. So for good parallel performance I will be forced
to always explicitly call unordered(), or conduct that complicated test on the spliterator's
characteristics. Unless I'm overlooking something, I am not happy  with the concept "natural 
encounter order", because it seems unknowable.

-- Sebastian

> -----Original Message-----
> From: Brian Goetz [mailto:brian.goetz at oracle.com]
> Sent: Saturday, October 05, 2013 9:56 PM
> To: Millies, Sebastian
> Cc: lambda-dev at openjdk.java.net
> Subject: Re: Stream#generate() vs. iterate()
> 
> Sequential and unordered are orthogonal characteristics.
> 
> Ordered/unordered means that the source has a natural encounter order, and that
> stream operations should respect that order.  For example, lists and arrays have a
> natural encounter order; they have a first element, a second element, etc.  Whereas
> a HashSet has no natural encounter order; processing the elements in one order is as
> good as any other.
> 
> Sequential/parallel has to do with whether the stream operations will execute
> sequentially or in parallel when the terminal operation is initiated.
> 
> generate() returns a sequential, unordered stream.  You can turn that into a parallel,
> unordered stream with generate(f).parallel().
> 
> On Oct 5, 2013, at 6:54 PM, Millies, Sebastian wrote:
> 
> > I'm a bit confused, perhaps it's just terminology:
> >
> > Looking at the Javadoc (in b106) for Stream#generate(Supplier) it says it returns a
> sequential stream.
> > In your post you say it returns an unordered stream. In what way can a sequential
> stream be unordered?
> >
> > -- Sebastian
> >
> > -----Original Message-----
> > From: lambda-dev-bounces at openjdk.java.net [mailto:lambda-dev-
> bounces at openjdk.java.net] On Behalf Of Brian Goetz
> > Sent: Saturday, October 05, 2013 6:13 PM
> > To: Arne Siegel
> > Cc: lambda-dev at openjdk.java.net
> > Subject: Re: stream.parallel().limit() not usable
> >
> > [snip]
> >
> > You might also do better with Stream.generate, since it creates an unordered
> stream:
> >
> >     Stream.generate(generatorFunction)
> >                  .parallel()
> >                  ...
> >
> >
> >
> >
> > Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany
> – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management
> Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Dr. Wolfram Jost, Arnd
> Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas
> Bereczky - http://www.softwareag.com
> >
> >