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
<https://github.com/leo-editor/leo-editor/tree/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
--
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/leo-editor/945d9bd3-7653-47ba-9617-8359587ae8b5%40googlegroups.com.
