RFR: 8266571: Sequenced Collections [v4]

[Chen Liang]

On Tue, 28 Mar 2023 02:37:22 GMT, Stuart Marks <smarks at openjdk.org> wrote:

>> PR for Sequenced Collections implementation.
>
> Stuart Marks has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Simplify handling of cached keySet, values, and entrySet views.

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.

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

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