RFR: 8301761: The sorting of the SortedList can become invalid [v4]

[Oliver Kopp]

On Mon, 7 Oct 2024 16:25:22 GMT, Loay Ghreeb <duke at openjdk.org> wrote:

>> Fix an issue in `SortedList` where the sorting became incorrect when adding new items that are equal to existing items according to the comparator. The `SortedList` should consider the insertion index of these items to maintain the correct order.
>
> Loay Ghreeb has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains seven additional commits since the last revision:
> 
>  - Merge branch 'master' into SortedList
>  - Merge branch 'master' into SortedList
>  - Merge branch 'master' into SortedList
>  - Merge branch 'master' into SortedList
>  - Merge branch 'master' into SortedList
>  - Add test case
>  - Fix SortedList to maintain insertion order for equal elements

TL;DR: This change is covered by an additional test. All other tests remain intact. Thus, this change does not break anything; it merely introduces a new feature.

> > Shift + Click again on Col2 to remove the sort from Col2. The order will stay the same [1, 0, 3, 2], but the expected order is [1, 0, 2, 3] as in step 2.
> 
> Why is that the expected order?

In the role of a user, I persieve removing an additional sort order as undo operation. 

Applying that thought to the example: "undo" is the reverse operation of a "do" operation. Meaning: First, Col2 should be considered as additional sorting. Then, it should not be considered as additional sorting. 

Applying that thought to a longer table: I as user have a dataset with n columns. If the dataset is in [1NF](https://en.wikipedia.org/wiki/First_normal_form) only, there might be many columns having the same values. If I as user begin to sort starting from column 1, then column 2, then column 3. Then I see: Oh, wait, no, I want to skip that column and sort by column 4 instead of 3. Then I undo the sort by column 3 and continue with 4. -- If the sort is not reverted to the previous state, but some other state, I need to start from the beginning. For two columnsd, this "annoyance" might be OK, but what for 10 columns? If I made a sorting mistake at column 9, I really need to redo all 8 columns before?

> If we want to distinguish between equal elements to give them a fixed sub-ordering (and the inverse one I suppose when the sort is descending) then what should the distinguishing factor be? Its position in the underlying unsorted list? The time it was added to the underlying list? They need not be the same. Using the position in the underlying list could be quite random if the source of the list doesn't guarantee a fixed position (from an unsorted database query for example).

I like the position in the list. At the time of "materialization" of the list, the position of an element is known - indepenent of it was retrieved by a SQL query or other sources.

Since this change "only" narrows the order, does not contradict other expectations, and really helps our desktop application to be more usable, I am strongly in favour to use the index as second criterion. -- An indication for no-change-for-others is that there was only an additional test case needed - and all existing test cases were unmodified.

> What if the underlying list is another sorted list or a filtered list, can we even rely on the indices those provide?

It would be even natural if the index change, the result of the SortedList also changes. I think, this is OK.

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

PR Comment: https://git.openjdk.org/jfx/pull/1519#issuecomment-2408469365