Re: A new tree drawing approach

[Edward K. Ream]

On Thu, Apr 9, 2020 at 2:21 AM vitalije  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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/leo-editor/CAMF8tS1t1Gq3y7b1%2B%2BjpL%2BqWD3xLttOiF1FrtyEqYfZrppVozw%40mail.gmail.com.

Re: A new tree drawing approach

[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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/leo-editor/5478bd0a-f906-4f81-a525-3c039c037457%40googlegroups.com.

Re: A new tree drawing approach

[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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/leo-editor/30cc48dd-da11-40d5-a3af-b17eb322eaa0%40googlegroups.com.

Re: A new tree drawing approach

[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

On Tue, Apr 7, 2020 at 9:02 AM vitalije  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 .
> 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 leo-editor+unsubscr...@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
> 
> .
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 

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


-- 
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+unsubscr...@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.