[pygtk] Sorting every row of a tree regardless of its hierarchy

[Jiri Bajer]

On Wed, 2009-08-26 at 01:47 +0200, John Finlay wrote:
> > If I store the data in a TreeModel, wrap a TreeModelSort over it and
> > display the result via TreeView, the sorting mechanism is not able to
> > put "Task 2" before "Task 1.2" even if "Task 2" has higher priority. It
> > is caused by respecting the hierarchy - sorting won't break a child from
> > its parent (but I need to do so).
> >
> > Is there any way how to achieve such sorting without maintaining two
> > copies of all data - one in TreeStore and one in ListStore and
> > sorting/displaying the ListStore instead?
> >   
> Look at the TreeModelFilter. With the right set_modify_func() function 
> you may be able to massage the look for your purposes.

Thanks for a hint! I've managed to create a 1:1 mapping between filtered
and original model - but I don't see how to change the row hierarchy in
the filtered model. It seems to me it is not possible to do anything
else than setting a value for filtered model's cell and thus using
PyGTK's native tree sorting mechanism over the filtered model won't
work.

Did you mean I can reorder the filtered tree rows as if they were sorted
by a given column (with original model's hierarchy that doesn't respect
my re-ordering) and then hide the expanders? That would also mean I have
to maintain a path-to-path/row-to-row mapping for every tree row and
every column I want to sort-by.

Mapping example for sort by Priority:

tree -> sorted "flat" list
(0,) -> (0,)
(0,0) -> (1,)
(0,1) -> (3,)
(1,) -> (2,)

Do you have any tips for the mapping? If I use something like the
example before I have to go through most of the tree and re-number the
paths with every row insert/delete (but finding the right path is easy).

Or I could store "pointers" like iterators or row references for every
row and every sortable column - they wouldn't need any additional care
in case of row insert/delete. But the iterators are not guaranteed to be
persistent and large number of row references would slow down the tree
to crawl...

That looks like having two copies of all data (a tree and a list)
doesn't help either because I would have to maintain the path-to-path
mapping anyway (or compute it on a fly by walking through all tree rows,
counting the rows traversed and searching for a particular hierarchy
number - which is too slow, O(N) for N=number of tree rows).

I can also imagine a hybrid solution where every parent tree node keeps
a number of nodes in his subtree which would speed up the tree
traversing to something like O(log N) but would also add O(log N)
operation of re-calculating the counts in a part of subtree on every row
add/delete.

>From what I've thought about so far it seems the easiest way would be to
hack into the TreeModelSort and add a property that would control if the
rows compared during the sort operation will respect the hierarchy or if
every row in the model gets compared. Can it be done directly from
Python or will I have to roll up the sleeves and dive into the C code?
Are there any tutorials available?

Thanks for any further ideas!

Jirka