ReversibleCollection proposal

[Stuart Marks]

On 4/17/21 2:48 AM, Stephen Colebourne wrote:
> On Fri, 16 Apr 2021 at 18:41, Stuart Marks <stuart.marks at oracle.com> wrote:
>> This is a proposal to add a ReversibleCollection interface to the Collections
>> Framework. I'm looking for comments on overall design before I work on detailed
>> specifications and tests. Please send such comments as replies on this email thread.
> 
> I think this could be an interesting addition to the framework.

Great!

>> # Ordering and Reversibility
> 
> Reading this section, it seems like ordering is a more significant
> quality than reversibility. Yet the API is named "reversible". That
> seems odd, esepcially given the stream characteristic.

I probably could have explained this better in the writeup.

"Reversible" is a stronger concept (i.e., it implies more things) than "Ordered". A 
reversible collection is ordered, it is traversable in both directions, both ends 
are accessible, and it affords operations at both ends. However, being ordered does 
not imply reversibility. For example, a PriorityQueue is ordered, but you can't get 
to the tail or iterate in reverse without a bunch of computation.

>> SortedSet::addFirst and addLast throw UnsupportedOperationException. This is because
>> SortedSet's ordering is determined by the comparison method and cannot be controlled
>> explicitly.
> 
> This seems undesirable. Maybe SortedSet should not implement
> reversible/ordered? Maybe they should add to the set but validate
> whether they would be in first/last position? Simply allowing users to
> get a new instance with a different (eg. reversed) comparator would
> meet much of the use case.

This is certainly an unpleasant asymmetry. But this is the Collections Framework; we 
should be used to unpleasant asymmetries. :-)

My typical examples of this are: various Map views like entrySet are that elements 
can be removed but they cannot be added; elements in Arrays.asList can be set but 
not added or removed; CopyOnWriteArrayList is mutable, but its iterators are not; etc.

Of course the presence of asymmetries doesn't justify the addition of more. But 
there is a precedent here: collections will implement an interface if they can 
support "most" of the operations, and the ones that aren't appropriate will throw 
UnsupportedOperationException. That's the precedent I'm following here with 
SortedSet (and NavigableSet).

An alternative as you suggest might be that SortedSet::addFirst/addLast could throw 
something like IllegalStateException if the element is wrongly positioned. 
(Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity 
restriction.) This seems error-prone, though, and it's easier to understand and 
specify that these methods simply throw UOE unconditionally. If there's a good use 
case for the alternative I'd be interested in hearing it though.

> Also, SortedSet uses first() and last(), yet the proposed interface
> uses getFirst() and getLast().

Deque defines a full set of operations at both ends, including:

     { add, get, remove } x { First, Last }

so it seemed sensible to take that complete set and promote it to ReversibleCollection.

s'marks