ReversibleCollection proposal

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Stuart Marks" <stuart.marks at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Samedi 1 Mai 2021 00:42:10
> Objet: Re: ReversibleCollection proposal

>> You did not really answer to the real question, why should i use
>> ReversibleCollection instead of a Collection as parameter.
>> You said that it's a better type because you can not send a HashSet, but as i
>> said, sending a HashSet of 0 or 1 element is perfectly valid.
>> For me, we are not far from, it's typechecking for the sake of typechecking.
> 
> I thought I did answer it, but it might have been in response to a different
> message
> on a different part of the thread. But I'll make the case in a more explicit
> fashion
> here.
> 
> First, a couple background points related to this:
> 
>  - ReversibleCollection is not intended to, and indeed cannot represent all
>  ordered
> collections. Queue is ordered and is not a ReversibleCollection, and there are
> likely other collections out there that are ordered but that implement
> Collection
> directly. Also, they might or might not be reversible.
> 
>  - I expect that few, if any Java SE APIs will be adjusted to use
> ReversibleCollection as a parameter type. Any APIs that use Collection but
> require
> an ordered type cannot be changed because of compatibility reasons.
> 
> Despite both of these points, I believe ReversibleCollection can be successful,
> and
> it can be useful in APIs as a parameter type. (The proposal itself uses
> ReversibleCollection and ReversibleSet as method return types.)
> 
> Consider the case of a large application or other system, one that's large
> enough to
> have lots of internal APIs, but that is built as a single unit, so
> release-to-release compatibility isn't an issue. Suppose there is some method
> 
>     processItemsInOrder(List<Item> items)
> 
> that has to process items in the order in which they occur, because processing
> of
> later items might depend the processing of earlier ones. The maintainer of this
> API
> chose to accept a List as a parameter, because it's a common interface and it's
> clearly an ordered collection.
> 
> Now consider a client that gets items from different places, keeping them in
> order,
> but removing duplicates. It might do something like this:
> 
>     var items = new LinkedHashSet<Item>();
>     items.addAll(getItemsFromSomeplace());
>     items.addAll(getItemsFromAnotherPlace());
>     items.addAll(getItemsFromSomeplaceElse());
>     processItemsInOrder(new ArrayList<>(items));
> 
> It turns out the copying of the items into an ArrayList is a performance
> bottleneck,
> so the maintainer of the client code asks the maintainer of the items processing
> code to change the API to accept Collection instead.
> 
> The items processing maintainer demurs, recalling that the API *did* accept
> Collection in the past, and a bug where somebody accidentally passed a HashSet
> resulted in a customer escalation because of item processing irregularities. In
> the
> aftermath of that escalation, the API was changed to List. The client maintainer
> reluctantly pursues alternatives for generating a deduplicated List.
> 
> But wait! Those Java guys added a ReversibleCollection interface in Java N. It
> has
> the desired property of being ordered, and conveniently it's a supertype of both
> List and LinkedHashSet. The items processing maintainer adjusts the API to
> consume
> ReversibleCollection, and the client maintainer removes the temporary ArrayList,
> and
> everybody is happy.

I suppose the performance issue comes from the fact that traversing a LinkedHahSet is slow because it's a linked list ?

You can replace a LinkedHashSet by a List + Set, the List keeps the values in order, the Set avoids duplicates.

Using a Stream, it becomes
  Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), getItemsFromSomeplaceElse())
   .flatMap(List::stream)
   .distinct()              // use a Set internally
   .collect(toList());

I think there are maybe some scenarios where ReversibleCollection can be useful, but they are rare, to the point where when there is a good scenario for it people will not recognize it because ReversibleCollection will not be part of their muscle memory.

There is a real value to add methods like descendingSet/descendingList()/getFirst/getLast on existing collections, but we don't need a new interface (or two) for that. 

> 
> s'marks

Rémi