Today I saw how Leo can delete resurrected nodes safely and usefully.
The key idea came was to create a "Resurrected Nodes" node, just as
with "Recovered Nodes" node. This should make it safe to delete
resurrected nodes--they will just move from @thin trees to children of
the "Resurrected Nodes" node. We expect the user will usually delete
the "Resurrected Nodes" node after glancing at its contents.
But first, I had to find a way to delete a list of nodes. The key
idea is a theorem, discussed below. Here is the code in
at.deleteUnvisitedNodes that does the delete safely. BTW, I have
verified that this code with a new unit test that I think tests all
important cases::
# Traverse root's subtree, moving nodes.
p = root.copy()
after = p.nodeAfterTree()
p.moveToFirstChild()
while p and p != after:
if p.isVisited():
p.moveToThreadNext()
else:
# Move p (and its subtree).
next = p.nodeAfterTree()
p.moveToLastChildOf(r)
p = next
if not g.unitTesting:
g.es('resurrected node:',p.h,color='red')
g.es('in file:',root.h,color='blue')
Notes:
1. I haven't shown the code that creates r, the 'Resurrected Nodes'
node.
2. The theorem is this.
The statement p.moveToLastChildOf(r)
can not disrupt the later operation of the traversal as show.
Proof. Suppose we do the move in the else clause. The assignment p =
next sets p to the node after p's tree, and this node is the same
after the move as before the move. We must show that moving the node
out of the tree can not change the nodes visited by the traversal
later on: the same nodes will be visited. This is easy to do.
Indeed, a position p consists of p.v and p.stack, the ancestors of p
**at position p of the traversal.**. But moving p can never affect
the ancestors of the position at p.nodeAfterTree. That's all there is
too it.
Thus, this is *completely* safe code, provided that r is not in root's
tree, which it is not.
3. Generalizing the code, say by creating p.deletePositionsInList,
would be straightforward. Instead of testing p.isVisited(), it would,
say, test p in aList. To make this method general enough, we would
need a callback telling it how to do the "delete". Here, the callback
would be something like::
def callback(p,r):
p.moveToLastChildOf(r)
if not g.unitTesting:
g.es('resurrected node:',p.h,color='red')
g.es('in file:',root.h,color='blue')
I'll probably do this tomorrow, and create a new section in the
Scripting chapter to discuss this tricky topic.
Edward
--
You received this message because you are subscribed to the Google Groups
"leo-editor" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/leo-editor?hl=en.
