ReversibleCollection proposal

[Stuart Marks]

On 4/25/21 11:09 AM, Peter Levart wrote:
> When making this proposition, I was only thinking of how to enable new 
> yet-nonexistent operations on collections that have order / are reversible and that 
> the code calling these methods would already knows that it is dealing with ordered / 
> reversible collections. I wasn't thinking about how to prevent mistakes like passing 
> unordered collection to code that expects ordered / reversible collection. This can 
> only be solved in two ways. The way immutability of collections is solved (throw 
> exception in runtime when requesting operation that makes no sense in unordered 
> collection) or by introducing new type - ReversibleCollection that solves this in 
> compile time. So I take back my vote for suggestion to introduce methods like 
> getFirst(), removeFirst() that would return arbitrary element. There's still a 
> possibility for those methods to throw at runtime though. But I don't know whether 
> this would be so nicely accepted as immutability was. WDYT?

Consider some collection implementation X that has some semantics and a suite of 
operations that support those semantics. An implementation can throw 
UnsupportedOperationException if for some reason that operation doesn't make sense 
for the implementation, but fundamentally that implementation still has "X-ness".

Look at Arrays.asList for example. It's backed by an array, so add and remove 
operations aren't supported. But it's still fundamentally a List in that it has N 
elements, is ordered, the elements are numbered from 0 to N-1, sublists can be 
obtained between two arbitrary indexes, its ListIterator supports iteration in both 
directions, it has a clear and useful definition for equals() and hashCode(), etc.

Similarly, an unmodifiable List is still a List.

Now consider adding {add,get,remove}{First,Last} methods to the Collection 
interface. Collection doesn't have any semantics for these methods itself, so we're 
hoping that there is some sensible mapping from these methods to appropriate 
operations on Collections implementations or subinterfaces.

  * Presumably for unordered collections like HashSet, all of these methods would be 
left to throw UOE.

  * A queue has a head and a tail, so perhaps these are mapped to first and last, 
respectively, and Queue would support addLast and removeFirst but not addFirst and 
removeLast. But that wouldn't work for PriorityQueue.

  * A stack has a "top": the most recently pushed element. Does the stack top 
correspond to the first or the last? It could be either -- in fact, in the JDK, for 
Stack the top is the last element but for Deque the top is the first element.

  * For some other ordered collection, who knows what a reasonable mapping would be?

This approach feels backwards to me. Instead of starting from an abstraction that 
has strong semantics and then applying all (or at least most) of the applicable 
methods, we're starting with a suite of methods and looking around for relationships 
to a variety of abstractions that might or might not have much in common. That seems 
like a recipe for a bad API to me.

s'marks