[REVIEW REQUEST] Improvements to TableView sorting

Tue Feb 19 03:37:26 PST 2013

I have a few questions, most are related to this use case:

Have a huge list (say a million items), sort it, user shift selects the 
top half a million items (0-500000), now sort it again on some unrelated 
criteria (making the distribution of selected items random) and now 
remove those items (user presses delete). It's important none of those 
actions slow the system down to a crawl (it will kill the Swing 
implementation).  Possible performance problems:

- Transforming a select range of 0-500000 to many smaller select ranges 
when a resort occurs
- Huge 'mapping' arrays being used with "before" and "after" sort states 
for keeping track of selection
- Depending on the backing list, many random deletes in a huge List will 
be costly (ArrayList won't cut it, any Events being triggered on 
modification of the list will likely also introduce a huge bottleneck).  
Note that the use case specifically causes these deletes to be random!  
It's not possible to do it in a single remove event.
- Resorting after every list change

1) Does SortedList force a specific type of List implementation, or is 
it an Interface?
2) How is the change of sort order communicated to the Selection Model?  
Will it be possible to override the selection model with a custom 
implementation (one that is sort order independent for example) without 
incurring overhead from unnecessary selection model updates caused by 
sorting?

I like the flexibility provided:

SortEvent seems to cover the option of creating an (external) 
implementation of sorting yourself should there be performance problems.

SortPolicy -- if I understand correctly -- externalizes the entire 
sorting (and filtering?) mechanism, similar to what the SelectionModel 
and FocusModel do.  This keeps the View classes cleaner (they're quite 
complex already) and more focused on their tasks of managing Cells and 
navigation between cells.  You call it a Callback, does that mean it 
instantiates something or is just an interface?

The only thing for now that I think smells a bit is the special case for 
SortedList.  Is this hidden away in the SortPolicy or will it touch the 
View classes as well?

--John

On 17/02/2013 22:36, Jonathan Giles wrote:
> Hi all,
>
> I am wanting to summarise my plans on how to improve TableView sorting 
> in JavaFX 8.0, given the conclusions reached regarding the 
> introduction of SortedList in JavaFX 8.0 [1]. Apologies for the length 
> of this email. If I had more time I would have made it shorter.
>
> OVERVIEW
> ====================
> For a while I've maintained an umbrella issue for improved sorting 
> functionality in TableView (RT-19479 [2]). My expectation is what I 
> outline below should work towards resolving as many of the issues 
> outlined in this Jira issue, most importantly the following features 
> are ones I would love to support:
>
> 1) Support returning to an unsorted state.
> 2) Support forcing a 'continuous' sort (so that whenever the items 
> list is changed the TableView remains sorted).
> 3) Support custom sort policies (to allow for people to override the 
> current in-memory sort policy and instead, say, go direct to a 
> database to do the sort).
> 4) Be notified of when a sort event is about to occur and prevent it 
> from happening.
> 5) Make it possible to force a sort when something elsewhere in the 
> universe (unrelated to the tableview) has changed (e.g. when you know 
> the tableview is no longer consistent and should re-run its sort policy).
>
> I'm not aware of other features that should be supported. If you have 
> some and they are within the scope of TableView sorting, then please 
> read the rest of this email and then reply to it so we can discuss.
>
> IMPLEMENTATION
> ====================
> I have attached an early draft patch for the following functionality 
> inside RT-19479. It is 'early and draft' in the sense that I'm fairly 
> comfortable with the API, but there is still a lot of implementation 
> and javadoc work that needs to be done. Hopefully it should give you 
> all an idea of what is planned, so that you may offer any thoughts 
> before I get too far into implementation and javadoc.
>
> To summarise the patch, what I've done is add a new SortEvent class, 
> and then for both TableView and TreeTableView I have done the following:
>
>  * I've introduced a public static Callback DEFAULT_SORT_POLICY that
>    encapsulates the current sorting code. Users are free to overwrite
>    this sort policy should they wish to instead go to the database, for
>    example. They do this by calling tableView.setSortPolicy(...).
>  * I have made the TableView and TreeTableView sort() methods public,
>    but they simply defer to the sort policy (assuming it is non-null,
>    which is the case by default as the DEFAULT_SORT_POLICY is set by
>    default).
>  * I have made the code that calls sort() more full-featured. This
>    happens in a few places, most notably when the 'sortOrder' list is
>    changed (where sortOrder is a list of TableColumns which the user /
>    developer has specified are to be used to sort the data in the
>    table). In particular, I now do the following when the sortOrder
>    changes (or any of the other sort criteria relevant to the sort):
>      o I update the Comparator that I am about to use. This Comparator
>        is now publicly readable (but not writable), so that people can
>        do
> sortedList.comparatorProperty().bind(tableView.comparatorProperty()).
>          + The reason why I don't want the comparator to be writable is
>            that it would then allow for the comparator to be
>            inconsistent with the sortOrder list, whereas I view the
>            comparator as a reflection of the sortOrder. If people don't
>            want to use this comparator they are free to set their own
>            sort policy and use whatever they want in there.
>      o I fire the SortEvent. If this event is consumed I do not run the
>        sort().
>      o I call sort()
>      o sort() is now very simple: it calls getSortPolicy() and runs it,
>        passing in the TableView / TreeTableView and expecting a boolean
>        response to indicate success or failure.
>
> The above outline essentially allows for features 2), 3), 4) and 5) 
> from the list above. The only feature missing therefore is 1), which 
> is support for returning to an unsorted state. The solution to this is 
> to have a special-case support inside TableView / SortedList such that 
> the developer may do what I mentioned above (namely, 
> sortedList.comparatorProperty().bind(tableView.comparatorProperty())), 
> and when the tableView.sortOrder list is empty the TableView / 
> SortedList will take that to mean there is no sort desired and to 
> return to the original, unsorted state.
>
> The other important note to make is that if you as the developer 
> provide the TableView with a SortedList this is telling the TableView 
> not to sort the collection or modify the Comparator if the user / 
> developer changes the sortOrder (e.g. by clicking on the column 
> headers). In other words, a TableView with a SortedList can not have 
> its sort order changed by default. Of course, if you DO want the 
> Comparator to be changed in your SortedList (and to support unsorted 
> state as above), you can simply bind the comparator of the list to the 
> tableview comparator.
>
> I hope that is clear. It's a lot of detail to get out, but hopefully 
> it meets the expectations of everyone and I can go forth and implement 
> it (and pray for no gnarly edge cases). I think the most probable area 
> for issues is around maintaining consistent visuals for the sorted 
> table column(s) given the ability for sorting to fail and / or be 
> ignored by the developer implementation of the comparator / sort policy.
>
> As always, your thoughts and comments are appreciated, but lets keep 
> this discussion focused solely on sorting in TableView (and to a 
> lesser degree TreeTableView).
>
> [1] See the last comment by Richard Bair here: 
> http://javafx-jira.kenai.com/browse/RT-17053
> [2] http://javafx-jira.kenai.com/browse/RT-19479
>
> Thanks,
> -- Jonathan
>