In the previous post, I have explained two basic helper classes
NData and gave you an example of a picture showing content of Leo model data for one example outline. In this part, I will use more pictures like that one. If you don’t understand what the picture represents, please read again previous post.
Let’s start with one of the basic operations:
How to delete node
To delete node (and of course its entire subtree) from new data model, we have to delete items from all lists:
positions, nodes, levels. We also need to update size of all ancestor nodes. We have to cut links between its parent node and this one. We need to delete this block of items from all other occurrences of the parent node in the outline. And finally, we may have to clean
attrs if the deleted node occurred only once in the outline.
Here is a picture that shows changes in model data when
delete_node(P5) is executed.
As you can see there are not many differences (which are marked with red colour). In first four columns the only differences are sizes of ancestor nodes. In the right part we can see that node at the position P2 has changed his list of parents. Missing parent is actually deleted node. Also node at the position P4 has changed list of its children. Missing child is the deleted node. And of course some rows are deleted.
Now let’s see the code that has done all these changes to the model.
def delete_node(self, pos): ( positions, nodes, attrs, levels, expanded, marked) = self.data # this node i = positions.index(pos) gnx = nodes[i] sz = attrs[gnx].size ns = nodes[i:i+sz] if sz > len(positions) - 2: # cant delete the only top level node return # parent node pi = parent_index(levels, i) pp = positions[pi] pgnx = nodes[pi] psz = attrs[pgnx].size # distance from parent pdist = i - pi # remove all nodes in subtree for pxi in gnx_iter(nodes, pgnx, psz-sz): a = pxi + pdist b = a + sz del nodes[a:b] del positions[a:b] del levels[a:b] # now reduce sizes of all ancestors update_size(attrs, pgnx, -sz) attrs[gnx].parents.remove(pgnx) self._update_children(pgnx) clean_parents(attrs, nodes, ns)
Is deletion allowed
If the outline has a single top level node its size must be one less than the number of positions in the outline. That is why we check this condition in lines 10-12 and return immediately if that is the case. We don’t allow the only top-level node to be deleted.
In line 21 we calculate the distance between the node being deleted and its parent node. In our case we are deleting the node at the position P5, and its parent is at position P4, so the distance
pdist = 1. That means wherever we find parent node in the outline, we are certain that at the index increased by
pdist we will have clone of the node we are deleting.
gnx_iter is a generator that yields indexes of all occurrences of the given gnx (in our case we are iterating occurrences of our parent node). That is why in line 24 we use
pgnx as argument for
gnx_iter. Here is the definition of the generator:
As you can see it uses
sz argument as a hint for how many nodes it is safe to skip before searching for another occurrence. Normally, node can’t be in its own subtree so it is safe to skip its size. However, when we are deleting from this node we are actually reducing its size by the number of deleted nodes. That is why in the line 24 we subtract size of this node from the size of its parent as third argument to the
Inside for loop (lines 24-29),
pxi is index of parent node. At the distance of
pdist begins data block that represents the node we are deleting. The block is
sz items long. In lines 27-29 we delete the block from all lists.
update_size recursively updates sizes of all ancetors.
Cutting links between nodes
Line 34 removes link from this node to its parent. Method
_update_children, recalculates list of children for a given node.
The first child if there is one, has index one greater than the index of its parent. That is why we start with the index
i + 1 in line 58. Upper limit
B is size of the parent away from parent index (line 57). We are increasing index
j by the size of child (line 62). And finally in line 63 we update list of children.
Cleaning lists of parents
There is one more thing that needs to be done. There is a possiblity that any of deleted nodes was parent to some node in the remaining part of the outline. In our example we can see that node at position P20 has parents with the gnxes
[B, F, H, N]. Node that we are deleting has gnx
B. As you can see, after deletion node in position P20 needs to update its list of parents by removing any gnx that was in the deleted block. After deletion list of its parents is
[F, H, N]. In line 36 we call function for cleaning lists of parents. Here is its definition:
It performs two cleanings: first in lines 65-68 and second cleaning lines 69-71. First we calculate all gnxes of all nodes that are not anymore part of the outline line 65. Argument
ns is a list of nodes that were removed from the outline. If some of the removed nodes had some clone outside the deleted block, then this node should not be cleaned from lists of parents. If however there were no other clones outside deleted block, then such nodes should be removed from all lists of parents (line 68).
In the second cleaning we are calculating which gnxes are still in
attrs but are not anymore in the outline (line 69). For each missing node we remove it from the
attrs dictionary. This might be unnecessary but makes everything cleaner and at least makes testing easier. Because of this we are sure that every item in
attrs is part of the outline.
In the following part you can find description of the other tree operations.