RFR: 8266571: Sequenced Collections [v4]

[Tagir F. Valeev]

On Thu, 30 Mar 2023 06:41:38 GMT, Stuart Marks <smarks at openjdk.org> wrote:

>> In the JEP:
>>> A sequenced collection supports common operations at either end, and it supports processing the elements from first to last and from last to first (i.e., forward and reverse).
>> 
>>> The reverse-ordered view enables all the different sequenced types to process elements in both directions, using all the usual iteration mechanisms: Enhanced for loops, explicit iterator() loops, forEach(), stream(), parallelStream(), and toArray().
>> 
>> This implies that for the reversed view, collection operations are not only supported, but can potentially be optimized. Our design should anticipate implementations of `SequencedCollection` to provide specific reversed implementations, like what we are already doing with `addAll` in ArrayList and ArrayDeque. If a collection cannot have efficient reverse-sequenced operations, it shouldn't be retrofitted into `SequencedCollection`, just like how we don't fit Deques into Lists.
>> 
>> Hence, I recommend:
>> 1. Declare `reversed()` and one of the (First/Last) operation sets (add|get|remove) `abstract`, and delegae the other set to default call the operation on the reversed instead. 
>>    - Since we tend to work with the end of collections, I'd declare the `Last` methods to be abstract and delegate the `First` default implementations to `this.reversed().xxxLast()`
>> 2. I don't think leaving `addLast()` implemented by default is a good idea, for modifiable implementations cannot discover that they missed the `addLast()` at compile time and can only discover when the implementation is actually used.
>> 3. In the default `reversed()` implementation of `List` and `Deque`, add API notes to indicate to implementations opportunities to optimize the implementation, especially batch operations like `addAll` when the base implementation offers such an optimization.
>
> @liach 
> 
> I understand that you're suggesting adding various default implementations in order to make it easier for people to bring up implementations of SequencedCollections. However, adding default implementations to SequencedCollection itself is unlikely to help. I expect that most implementations will override both addFirst and addLast. Requiring overriding of only one of them will hardly help anything, because the more difficult task is implementing the reverse-ordered view. I'd prefer to concentrate on some kind of implementation assistance for doing that. For example, there could be an "AbstractSequencedCollection" that would require overriding only a couple methods, rather like `AbstractCollection`. I'm a bit reluctant to introduce new abstract classes into the public API though. An alternative might be to have some kind of static factory method that takes something like a Collection and a reverse iterator and returns a SequencedCollection.
> 
> It's not clear to me that such support is necessary. It's pretty easy to bring up a List using AbstractList, and a List is a SequencedCollection. But if we do add something, it should be driven by use cases, and not speculation.

@stuart-marks 

> Thanks for looking! I took a quick look through the comments and they seem reasonable. Right now I'm concentrating on the specification in order to get the CSR Finalized. Do you have any comments on the specifications? I'll take a look at the implementation comments afterward. Some I'll be able to address before integration, but some I might need to postpone until later.

The specification is mostly well-written, thanks! I've added a few comments on the spec and few more comments on the implementation. Please check.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1490024150