Re: [External] :?==?utf-8?q? Re: ReversibleCollection proposal

[Anthony Vanelverdinghe]

Hi Rémi

The discussion "new types? or new default methods?" is indeed a valid one. In fact, I think this choice has already been made once in favor of a default method, when adding `List::sort` was chosen over adding `SortedList` (though I imagine that choice was a no-brainer).

In this case I prefer adding new types though, so I wanted to share my take on this.

In the following diagram (see [1] in case it got mangled), I've tried to arrange all relevant Collection types by their defining characteristics:

|- Collection ---------------------------------------------------------------------------------------------------------------|
|unordered    ordered                                   sorted           distinct    distinct & ordered    distinct & sorted |
|                                                                        Set                                                 |
|             Queue = (get|remove)First + addLast       PriorityQueue                                                        |
|             Stack = (add|get|remove)Last                                                                                   |
|             Deque = Queue + Stack + addFirst                                       LinkedHashSet         SortedSet         |
|             List = Deque + (add|get|remove)Indexed    List::sort                                         NavigableSet      |
|----------------------------------------------------------------------------------------------------------------------------|

As I see it, there are a couple of issues with this:
* conceptually, every List is a Deque, but List doesn't extend Deque. If it would, all uses of List (e.g. as a parameter type in APIs) where the indexed access isn't required could be replaced with Deque instead. Or e.g. when you need to take a stack as argument: currently Deque is the recommended parameter type, but that means you can't just pass a List to the method as-is. With RC, you'd be able to use that as parameter type and pass both Deque and List.
* LinkedHashSet and SortedSet lack a common ancestor which asserts "this is an ordered set". So when defining an API, I'm forced to choose between SortedSet, which is more specific than I want, or List, which is more generic than I want (usually I go with SortedSet, because enforcing something through Javadoc isn't very reliable (cf. Collectors::toList: even though the spec clearly says the result might not be modifiable, people tend to simply assume it is)).

Now with RC/RS these issues would be solved, where RC is ~ Deque + reversed, and RS ~ Deque + distinct + reversed. In terms of the diagram, they group together a bunch of closely-related Collection types (see [1] if needed):

|- Collection ---------------------------------------------------------------------------------------------------------------|
|unordered    ordered                                   sorted           distinct    distinct & ordered    distinct & sorted |
|                                                                        Set                                                 |
|             Queue = (get|remove)First + addLast       PriorityQueue                                                        |
|             Stack = (add|get|remove)Last                                                                                   |
|            |- ReversibleCollection -----------------------------------|           |- ReversibleSet -----------------------||
|            |Deque = Queue + Stack + addFirst                          |           |LinkedHashSet         SortedSet        ||
|            |List = Deque + (add|get|remove)Indexed    List::sort      |           |                      NavigableSet     ||
|            |----------------------------------------------------------|           |---------------------------------------||
|----------------------------------------------------------------------------------------------------------------------------|
 
On Wednesday, May 12, 2021 13:22 CEST, forax at univ-mlv.fr wrote: 
 
> First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap, the keySet should be a ReversibleSet.

I'm not sure what you meant, but the PR already defines `LinkedHashMap::keySet` as `public ReversibleSet<K> keySet()`.

> Again, we have seen that introducing those interfaces
> - is not source backward compatible thus it will be painful for some of our users,
>   I believe NavigableSet/NavigableMap did not have that issue because only one existing implementation per interface was retrofitted to implement those interfaces, TreeSet for NavigableSet and TreeMap for NavigableMap.
>   ConcurrentSkipListSet/ConcurrentSkipListMap were added at the same time, so there was no existing code doing a lub (lowest upper bound) between TreeSet and ConcurrentSkipListSet.
>   Here, they are a lot of implementations that will implement be retrofitted to ReversibleCollection, ReversibleSet and ReversibleMap.

As far as I understand, both options might cause source incompatibilities, but I assume you estimate the actual impact of adding default methods to be (much) smaller?

> - people will have to wait a theoretically infinite time before being to introduce a public method that takes a ReversibleCollection, ReversibleSet and ReversibleMap to their library, because it requires
>   all existing implementations of collection with an order to be retrofitted to implement those interfaces.

I think I'm missing something here. I just did an experiment to convince myself that the set of interfaces a class implements isn't hard-wired in its class file. In other words, that any custom List/Deque/SortedSet/... implementation would be seen as implementing RC/RS without having to recompile it (that, or my experiment was flawed somehow, of course). So am I correct that your concerns are only about custom collections that implement Collection directly? If so, if I'd introduce a public method in my library today, I'd have to declare the parameter as Collection in order for custom collections to be able to use it. So in the future, I could either introduce an overloaded the method (one with a Collection parameter & one with a ReversibleCollection), or I could expect clients to do `List::copyOf`... right? I'd appreciate it if you could elaborate on this point, because I don't understand the concern yet.

> - adding any new interfaces has a real cognitive cost, the collection API is supposed to be simple, does being reversible really worth such new weight.

I believe this is subjective, but to me the new interfaces are like "the missing piece" of the Collections API puzzle. I believe their value is also in the fact that they reconcile List/Deque and LinkedHashSet/SortedSet and are very useful as parameter/return types in APIs.

> > 
> > s'marks
> 
> Rémi

Kind regards, Anthony

[1] https://gist.github.com/anthonyvdotbe/e2e313693f032e4336e5385334a476db