ReversibleCollection proposal

Peter Levart peter.levart at
Tue Apr 27 09:25:30 UTC 2021

On 4/27/21 5:50 AM, Stuart Marks wrote:

> 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

Right, I'm persuaded. Now if only the problems of transition to the 
usage of new type that Remi is worried about were mild enough. Source 
(in)compatibility is not that important if workarounds exist that are 
also backwards source compatible so that the same codebase can be 
compiled with different JDKs. Binary compatibility is important. And I 
guess there is a variant of the proposal that includes 
ReversibleCollection and ReversibleSet and is binary compatible.

Now just some of my thoughts about the proposal:

- SortedSet.addFirst/.addLast - I think an operation that would be used 
in situations like: "I know this element should always be greater than 
any existing element in the set and I will push it to the end which 
should also verify my assumption" is a perfectly valid operation. So 
those methods throwing IllegalStateException in case the invariant can't 
be kept seem perfectly fine to me.

- ReversibleCollection.addFirst/.addLast are specified to have void 
return type. This works for List and Deque which always add element and 
so have no information to return. OTOH Collection.add is specified to 
return boolean to indicate whether collection was modified or not, but 
Set modifies the specification of that method a bit to be: return false 
or true when Set already contained an element equal to the parameter or 
not. So ReversibleCollection.addFirst/.addLast could play the same 
trick. for List(s) and Deque(s) it would always return true, but for 
ReversibleSet(s) it would return true only if the set didn't contain an 
element equal to the parameter, so re-positioning of equal element would 
return false although the collection was modified as a result.

- Perhaps unrelated to this proposal, but just for completeness, 
existing Collection interface could be extended with methods like: 
getAny() and removeAny().

Regards, Peter

More information about the core-libs-dev mailing list