A new tree drawing approach

[vitalije]

For several days now, I've been working on a new drawing approach. The preliminary results of this work can be seen in the new branch tree-refresh. There are still some things missing (like hoisting and chapters) but they won't be hard to add if Edward accepts this idea.

I had an Aha moment: The outline structure can be represented as a set of links, where each link is just a tuple (parent_id, index, child_id). In other words, all the information about the structure (or shape) of the Leo outline including the information about clones, can be represented by the set of elements (parent.gnx, index, child.gnx). And what is more important is that obtaining this set from the Leo is not too expensive operation.

import timeit
def makeset():
    def it(v):
        for i, ch in enumerate(v.children):
            yield v.fileIndex, i, ch.fileIndex
            yield from it(ch)
    return set(it(c.hiddenRootNode))
g.es(timeit.timeit(makeset, number=100)/100*1000, 'ms')

On my fastest computer this gives 6.14ms for LeoPy.leo. On older computers it might be about 12ms.

The idea is to keep track of this set each time we redraw the tree. On the next redraw we can simply use the set arithmetic to find what is changed in the tree. We calculate new set (let's call it a current_links) and then use (current_links - last_links) to get all the inserts and (last_links - current_links) to get all deletes.

Both of these operations are very fast and then we just need to add several new links or delete some of the previously existstent links to draw new version of tree.

This techinque can eliminate a lot of unnecessary redraws. For example if the node is expanded nothing is changed and the only thing necessary is to set certain tree item to expanded state.

It isn't only about the speed. There are more benefits of using this approach to draw tree. After redrawing the tree, for every position in the Leo there exists a single item. This fact alone can make a lot of other parts of Leo much simpler. A lot of checks that position exists and is still valid may be skipped if the position comes from the tree. Keeping track of expanded/collapsed state for each position can be delegated to the tree items, because for each valid position there exists a single item.

The code in tree-refresh branch is a prototype that shows this approach as possible. It doesn't do hoisting and chapters yet, and the code is not cleaned. A lot of qt_tree code is not used and can be deleted. There is one more status field in the status line which shows how much time took the last redraw. All of the unit tests pass.

There is a room for improvements of diff-calcualtion. In the current version bare set difference is used which is not producing the smallest possible diff. For example if a parent node has 10 children and we delete first one, the difference will contain not just one delete operation as it would ideally but 10 deletes followed by 9 inserts, because every child has now the different index. Perhaps we can process these differences a bit before applying them. But for now it works just fine. Deleting 9 items and creating new 9 items is still much less work than deleting the whole outline and recreating it from scratch.

Vitalije

[Brian Theado]

Vitalije,

This looks interesting. Thanks for sharing. I'm not familiar with how the existing tree drawing approach works. Could you share (in broad strokes) what the current drawing does and how it is different from your new scheme?

Is it that the existing code recreates all the QT items from scratch every time there is a redraw? And your code can add/remove a much smaller subset of QT items because of your set operations?

I didn't quite follow your example about expanding a node. When a node is expanded, then the children or descendants must appear in the display. How does that relate to the "set of links" you are using to represent the outline structure?

Thanks,

Brian

--
You received this message because you are subscribed to the Google Groups "leo-editor" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leo-editor+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/945d9bd3-7653-47ba-9617-8359587ae8b5%40googlegroups.com.

[vitalije]

Is it that the existing code recreates all the QT items from scratch every time there is a redraw? And your code can add/remove a much smaller subset of QT items because of your set operations?

Yes, that's the difference.

 

I didn't quite follow your example about expanding a node. When a node is expanded, then the children or descendants must appear in the display. How does that relate to the "set of links" you are using to represent the outline structure?

In my code, all nodes both visible and invisible are added to the tree once. Expanding and collapsing is done by the QTreeWidget and there is no need to add any node for this operation to work. Currently when user clicks in the "plus icon" in tree, Leo redraws all visible items and adds those previously invisible nodes. To allow user to expand clones separately Leo currently uses the following scheme. If a node p.v is a clone then it is expanded only if it has expanded bit set on the v-node and v.expandedPositions contains a copy of p. However, keeping copies of positions in v.expandedPositions is error prone. Some structural changes of the outline, like inserting or deleting a node make those cached positions invalid and the information about expanded/collapsed state is lost. This scheme also doesn't allow to separately expand children of clones. If you try to expand one child of a clone, then it is expanded in all other clones of its parent. In the new scheme every position has its own item in the QTreeWidget and every item keeps track of its expanded/collapsed state. 

I hope this clears a bit what I meant by this example.

Vitalije

[Edward K. Ream]

On Wednesday, April 8, 2020 at 9:05:25 PM UTC-5, btheado wrote:

This looks interesting. Thanks for sharing. I'm not familiar with how the existing tree drawing approach works. Could you share (in broad strokes) what the current drawing does and how it is different from your new scheme?

Thanks for these question, Brian. I was about to ask similar questions.

Edward

[Edward K. Ream]

On Thu, Apr 9, 2020 at 2:21 AM vitalije <vita...@gmail.com> wrote:

Is it that the existing code recreates all the QT items from scratch every time there is a redraw? And your code can add/remove a much smaller subset of QT items because of your set operations?

Yes, that's the difference.

 

I didn't quite follow your example about expanding a node. When a node is expanded, then the children or descendants must appear in the display. How does that relate to the "set of links" you are using to represent the outline structure?

 

In my code, all nodes both visible and invisible are added to the tree once.

Sounds interesting.

In the new scheme every position has its own item in the QTreeWidget and every item keeps track of its expanded/collapsed state.

Sounds very interesting :-)

Please continue your work. I fully approve.

Edward