RFR: 8266571: Sequenced Collections [v4]

[Tagir F. Valeev]

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.

src/java.base/share/classes/java/util/AbstractMap.java line 899:

> 897:      * @param <E> the view's element type
> 898:      */
> 899:     /* non-public */ static class ViewCollection<E> implements Collection<E> {

Should we declare it abstract to depict that this class is not intended to be instantiated directly?

src/java.base/share/classes/java/util/LinkedHashMap.java line 78:

> 76:  * on collection-views do <i>not</i> affect the order of iteration of the
> 77:  * backing map.
> 78:  *

I see above the list of methods that affect the encounter order in access-order mode:
> Invoking the put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access...

Should we extend it to add new methods like putFirst and putLast? Also, it says that 'In particular, operations on collection-views do not affect the order of iteration of the backing map'. Now, we have a map-view (`reversed()`). We should specify whether operations on the reversed map change the encounter order of the original map, and if yes then how exactly they do this (moving entries to the end, like in the original map, or moving them to the beginning?)

src/java.base/share/classes/java/util/LinkedHashMap.java line 1189:

> 1187: 
> 1188:         public V putIfAbsent(K key, V value) {
> 1189:             return base.putIfAbsent(key, value);

`putIfAbsent` should also preserve insert at the beginning. The default implementation from the `Map` interface will actually work (though requires double lookup):


V v = get(key);
if (v == null) {
  v = put(key, value);
}
return v;

Or we can narrow it a little bit:

V v = base.get(key);
if (v == null) {
  v = base.putFirst(key, value);
}
return v;

src/java.base/share/classes/java/util/SequencedCollection.java line 45:

> 43:  * required to operate on elements in encounter order include the following:
> 44:  * {@link Iterable#forEach forEach}, {@link Collection#parallelStream parallelStream},
> 45:  * {@link Collection#spliterator spliterator}, {@link Collection#stream stream},

Should we require in specification that the implementations of `SequencedCollection::spliterator` must have the `ORDERED` charactersitic?

src/java.base/share/classes/java/util/SequencedCollection.java line 78:

> 76:  * @since 21
> 77:  */
> 78: public interface SequencedCollection<E> extends Collection<E> {

Should we narrow the specification for `Collection::add` here, saying that `add` is essentially `addLast`? Specification for deque mentions that `add` and `addLast` are equivalent. Otherwise, the implementation of `SequencedCollection::add` that adds the element to a random position will comply the spec.

Another thing is `remove(Object)`. Should we specify here that it will remove the first instance of Object inside the collection (like it's specified in the list)? Or is it allowed to return a random one?

src/java.base/share/classes/java/util/SequencedMap.java line 125:

> 123:  * @since 21
> 124:  */
> 125: public interface SequencedMap<K, V> extends Map<K, V> {

Again, it would be good to specify here the behavior of some old methods from `Map`. Methods `put`, `putIfAbsent`, `merge`, `compute`, and `computeIfAbsent` may add new mapping as well. Should we specify that for ordered map the mapping is added at the end of collection? Or is it at discretion of the implementation?

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

PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1153019190
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1153002016
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1153013781
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1152981740
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1152978206
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1152994927