>
>
> Great help in quickly traversing tree to the given top position is to now
>> how many nodes are in its subtree. In my model it is the size of a node.
>>
>
> True, but the big payoff will come from just drawing/allocating
> approximately N nodes, where there are N visible nodes in the outline.
> This will eliminate the performance bug when expanding all nodes. No
> matter how many nodes the outline contains, the performance of the
> algorithm should be roughly O(1).
>
> What I meant is that it can help to calculate the top_position. Let's say
we want to start drawing at the 100th node. We need to skip 99 nodes
before. It helps if you know that the first top level node has 98 nodes in
its subtree and you can be sure that none of them should be drawn. If you
don't know you have to traverse its subtree to find out.
An advantage of using QGraphicsScene and its items is that you can draw
tree starting at any given node. It doesn't require items to have parents
all the way to the top. Each position knows its level so you can move the
corresponding graphics item at the correct indentation without drawing any
parent items. Look at the miniTkLeo how items are drawn in Tk.Canvas. I am
sure QGraphicsScene items will be very similar.
Anyway you decide for yourself. I have bad memories about QTreeWidget
(though they are fading).
> p.moveToVisNext is pretty slow, but not slow enough to be dangerous.
> Trying to optimize it might require a lot of code when expanding and
> contracting a node.
>
They are fast enough to draw once the drawing starts, but they take their
time while skipping invisible nodes (nodes that would be visible in large
enough screen).
I have been wondering whether "stable" positions might be added to Leo's
> existing data model. Can you point to some documentation?
>
The fragile position parts are integer index of vnode and int indexes in
their stacks. If you add a dictionary to each node that maps child
addresses (for example letters) to child nodes then position can put that
address (letter) into its stack and its childIndex field. Accessing child
nodes then would be two step process instead of just one. First you convert
index into address (a letter) and then that address into a child node. That
is little more work, but positions would become more immune to the tree
modifications. At some point I was thinking about this idea to use letters
or short strings to point to the child nodes. It is like UNL with indexes,
but much shorter and faster to calculate. This approach would require some
more work to keep those addresses in sync with the actual content of the
"children" field. Every time this field is adjusted it needs to update this
lookup dictionary.
class Vnode:
def __init__(self, ...):
...
self.a2v = {}
self.address_list = []
self._addrcounter = 0
def new_free_address(self):
self._addrcounter += 1
return '%x'%self._addrcounter
def _addLink(self, childIndex, parent_v):
v = self
...
# at the end
myaddr = parent_v.new_free_address()
parent_v.children.insert(childIndex, v)
parent_v.address_list.insert(childIndex, v)
parent_v.a2v[myaddr] = v
def _cutLink(self, childIndex, parent_v):
v = self
...
# at the end
myaddr = parent_v.address_list[childIndex]
del parent_v.address_list[childIndex]
del parent_v.a2v[myaddr]
To access child node by index one needs to get the address of this child (addr
= v.address_list[i]) and then to reach the node (child = v.a2v[addr])
That is more work to get to the child node, but positions can be fully
defined by the string that is concatenation of all the addresses along the
path to the vnode.
That string can become an immutable id of the position.
parent position id is just p.full_address.rpartition(sep)[0]
id of the position of child at the address a is just p.full_address + sep +
a
And the real index of the position is just
p._parentVnode().address_list.index(p.full_address.rpartition(sep)[2])
But I guess most of the time it won't be necessary to calculate this index
at all. Just operate with the addresses.
HTH
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 post to this group, send email to leo-editor@googlegroups.com.
Visit this group at https://groups.google.com/group/leo-editor.
For more options, visit https://groups.google.com/d/optout.
