On Tue, 8 Feb 2022 17:23:38 GMT, Stuart Marks <sma...@openjdk.org> wrote:
> PR for Sequenced Collections implementation.
Hello, Stuart!
I'm really glad that this proposal progresses, and now we have a solid
implementation draft. In general, I like it very much. You may find a couple of
comments from me in this review, hopefully, they are useful. Sorry if I wrote
some nonsense, it's already too late here :-)
src/java.base/share/classes/java/util/LinkedHashMap.java line 782:
> 780: return svs;
> 781: } else {
> 782: return new LinkedValues(false);
Is it possible that this branch is visited? If yes, probably it worth adding a
comment when this happens.
src/java.base/share/classes/java/util/LinkedHashMap.java line 1123:
> 1121:
> 1122: public V put(K key, V value) {
> 1123: return base.put(key, value);
Why `put()` simply delegates to `base.put()` while `putAll()` below does more
complex containsKey-put-putFirst procedure? I think that `putAll()` should be
equivalent to `for(var e : m.entrySet()) put(e.getKey(), e.getValue());`. Am I
missing something?
src/java.base/share/classes/java/util/LinkedHashMap.java line 1197:
> 1195:
> 1196: public V computeIfAbsent(K key, Function<? super K, ? extends
> V> mappingFunction) {
> 1197: return base.computeIfAbsent(key, mappingFunction);
Again, it's somewhat worrysome that methods like `computeIfAbsent` will
actually add new nodes to the end of original LinkedHashMap instead of to the
beginning. Probably not very big deal but looks inconsistent...
src/java.base/share/classes/java/util/ReverseOrderDequeView.java line 64:
> 62:
> 63: public Spliterator<E> spliterator() {
> 64: return
> Spliterators.spliteratorUnknownSize(base.descendingIterator(), 0);
Could we use here `Spliterators.spliterator(this,
base.spliterator().characteristics())`? Current implementation is not
late-binding and never sized.
src/java.base/share/classes/java/util/ReverseOrderDequeView.java line 103:
> 101: }
> 102:
> 103: // copied from AbstractCollection
Probably not the part of this PR, but it could be reasonable to create some
utility CollectionSupport class and create static methods (e.g. `static boolean
remove(Collection<?> c, Object o)`) with the implementations of common
collection algorithms, like this one. WDYT?
src/java.base/share/classes/java/util/ReverseOrderDequeView.java line 167:
> 165: public <T> T[] toArray(T[] a) {
> 166: // TODO can probably optimize this
> 167: return toArray(i -> (T[])
> java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), i));
Hm... Does it follow the spec when the size of `a` is greater than the size of
this collection? In this case, we should return the supplied array filling it
partially and setting the next element to null. Here, we will always create a
new array, which seems to violate the spec.
src/java.base/share/classes/java/util/ReverseOrderListView.java line 153:
> 151: public Spliterator<E> spliterator() {
> 152: // TODO can probably improve this
> 153: return Spliterators.spliteratorUnknownSize(new
> DescendingIterator(), 0);
Again, `Spliterators.spliterator(this, base.spliterator().characteristics())`
may work better (though haven't checked)
src/java.base/share/classes/java/util/ReverseOrderListView.java line 168:
> 166: boolean modified = false;
> 167: for (E e : c) {
> 168: base.add(0, e);
This is worrysome from performance point of view for base implementations like
ArrayList where every insertion means shifting the whole array. At least, we
could optimize if `c` is `SequencedCollection`, like `if (c instanceof
SequencedCollection<? extends E> sc) base.addAll(0, sc.reversed())`. Otherwise,
we can use `base.addAll(0, Arrays.asList(sc.toArray()).reversed())` (with a
couple of unchecked casts).
src/java.base/share/classes/java/util/ReverseOrderListView.java line 288:
> 286: public <T> T[] toArray(T[] a) {
> 287: // TODO can probably optimize this
> 288: return toArray(i -> (T[])
> java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), i));
Incorrect implementation again
src/java.base/share/classes/java/util/ReverseOrderListView.java line 316:
> 314: public void add(int index, E element) {
> 315: checkModifiable();
> 316: base.add(base.size() - index, element);
Note that if index is out of bounds, the original collection may throw a
confusing exception, as `base.size() - index` will be reported instead.
Probably adding explicit bounds checking call before delegation would be
better. Same applies to other index-based operations.
src/java.base/share/classes/java/util/ReverseOrderListView.java line 319:
> 317: }
> 318:
> 319: public boolean addAll(int index, Collection<? extends E> c) {
Similar considerations, as for `addAll(Collection)`.
src/java.base/share/classes/java/util/ReverseOrderSortedMapView.java line 99:
> 97:
> 98: public Set<K> keySet() {
> 99: return new AbstractSet<>() {
At very least, please delegate `contains`, `remove`, and `clear`, to avoid O(N)
complexity there. Same for `values()` and `entrySet()`
src/java.base/share/classes/java/util/ReverseOrderSortedMapView.java line 185:
> 183:
> 184: static <K, V> Iterator<K> descendingKeyIterator(SortedMap<K, V> map)
> {
> 185: return new Iterator<>() {
Probably create `descendingEntryIterator` as base, and derive
`descendingKeyIterator` and `descendingValueIterator`? This way, `map.get()`
inside `descendingValueIterator` and `descendingEntryIterator` could be avoided.
-------------
PR Review: https://git.openjdk.org/jdk/pull/7387#pullrequestreview-1357459425
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148075441
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148079423
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148081322
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148090986
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148092195
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148096483
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148097411
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148098823
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148099182
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148099726
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148100155
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148102202
PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1148103978
