RFR: 8294693: Add Collections.shuffle overload that accepts RandomGenerator interface [v3]

[jmehrens]

On Fri, 28 Oct 2022 23:18:00 GMT, Stuart Marks <smarks at openjdk.org> wrote:

> I'm having difficulty imagining how SequencedCollection::replaceAll could work or be useful. Obviously it's on List already.
In Collections.java, it seems that the cases of AbstractSequentialList are handled like so:

1. Call toArray
2. Perform some permutation on the array copy.
3. Write results back to using a loop ListIterator::set.

Step three can always be rewritten with List::replaceAll (new RFE).  SequencedCollection is somewhat like AbstractSequentialList because calls to get are not used.  Therefore, if AbstractSequentialList has positional read access but it is not used and SequencedCollection doesn't have positional access either then the two types could be substituted if we had some sort of way to write the permutation back to the SequencedCollection.  One way to do that is replaceAll as it is a sequenced (non-random) write operation.

> However, LinkedHashSet is a Set and so has a unique-elements constraint. What should replaceAll do if the replacement element already exists in the set? (For a shuffle operation, the first swap operation by definition replaces an element with another element that's somewhere else in the set, so this issue arises immediately.) 

On an SequencedSet it is effectively a swap operation.  Ejecting the existing element would be a CCE and adding a new element would be a CCE so the only way to implement is with position swap.  It just would mean the UnaryOperator could encounter the same element for the whole iteration if it was constantly swapped with (i + 1).  Perhaps that is violation where this all falls apart?

> A replaceAll operation on a NavigableSet seems right out. The elements are positioned according to their sort order, so there's no notion of updating an element "in-place" at all.

My understand is that addFirst/addLast would be present on NavigableSet per retrofitting section of the JEP.  The replaceAll would have API wiggle words the same way addFirst/addLast would.

At any rate I don't want to derail this PR and I appreciate your response.  It just seems odd to me that SequencedCollection has a sequence but we can't sort or shuffle that sequence via Collections.java as we do for AbstractSequentialList.

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

PR: https://git.openjdk.org/jdk/pull/10520