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 On Tue, Apr 7, 2020 at 9:02 AM vitalije <[email protected]> wrote: > 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 > <https://groups.google.com/d/msgid/leo-editor/945d9bd3-7653-47ba-9617-8359587ae8b5%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- 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/CAO5X8CwEfWaZeT5GOyctv-0badT2e6AKdN%3D4-f%3DhAcGj5Poo5w%40mail.gmail.com.
