Re: rethinking GtkTreeModelSort

[jrb redhat com]

Havoc Pennington <hp redhat com> writes:

> Hi,
> 
> I think we should rethink GtkTreeModelSort as an approach to tree
> sorting. As we know, it has the following disadvantages:
>   - it's not especially efficient; by adding the 
>     cheesy GTK_TREE_MODEL_ITERS_PERSIST flag we made it better, but 
>     still not great
>   - it chews RAM; you have to keep the tree of persistent iters in 
>     addition to the real model
>   - it introduces the complicated and confusing ITERS_PERSIST flag
>   - it limits how models can be implemented, and limits our ability 
>     to warn about bad iterators

I'm a little confused, Havoc.  How's it inefficient.  Speed?  Space?  In
terms of speed, it's pretty darn fast.  In terms of space it requires 32
bytes per visible node (on IA32), though 8 of them could be cut down if
we decide to remove some unused pointers from GtkTreeIter (probably a
good idea.)  Not exactly trivial, but certainly a space-saver when
considring multiple models (see below).  Also, why is the ITERS_PERSIST
flag cheesy?  It's a performance saver, but GtkTreeModelSort should work
without it set (albeit less efficiently.)

> So, why not give up on this, and simply add a
> set_sort_column(GtkTreeModel *model, gint column) virtual function to
> GtkTreeModel. I guess the objection here is that it's less convenient
> to use; I don't think it really is. We would go ahead and implement it
> for the standard models, which 90% of trees will use. For other trees,
> any sane language has sort functions for common data structures, so
> typically the implementation of this function would be a simple
> qsort() or g_slist_sort() in C, or a sort() in C++, etc. I would
> expect the function to typically require only a few lines to
> implement. It's slightly more work to honor the sort column in the
> insert/append/prepend/etc. implementation, but shouldn't be rocket
> science. This is CS 101 stuff, and to write a custom model you already
> have to understand GObject, so you should be able to keep a list
> sorted.

The problem is that it's done at the model level, while it's really a
view issue, and the benefits of Model/View are lost.  The main reason it
is done this way is so that you can have multiple views of the same
model, each sorted differently.  As an example, consider a
filemanager.  We could have one model of the filesystem for everything.
If we have a list view in each pane, we save memory by only resorting it
versus having a new model for each.

> Also, this lets us automatically wire up the
> clicking-on-column-sorts-it stuff, with TreeModelSort users have to
> manually set up a callback on column clicked which calls
> set_sort_column. So stuff will Just Work with the standard GTK models
> (ListStore and TreeStore). For that matter you could even add a
> column_is_sortable virtual method that lets TreeView automatically
> decide whether to make each column header clickable.

I started working on a convenience function in gtktreemodelsort to do
this kind of thing.  Something like:

static void
gtk_tree_view_set_sort_column (GtkSortView       *sort_view,
                               GtkTreeViewColumn *column,
                               GtkTreeModelSort  *sort,
                               GValueCompareFunc  func);

Etc...

I don't think it matters too much where this type of function actually
lives...

Thanks,
-Jonathan