On Wed, Oct 5, 2011 at 12:12 PM, Edward K. Ream <[email protected]> wrote:
> Indeed, deleting a node
> (or moving a node to a "safe" spot, like the child of an unmoving root
> node), can *not* change the position of nodes that appear *earlier* in
> the (forward) tree traversal. True, the clone status of earlier nodes
> can change, but that does *not* change the positions of those nodes!
I don't think the "crude" reverse traversal will work, but the
observation above provides the insight for the proper way.
Let p_last be the last node of the outline. This can be usually be
computed very quickly (we only have to traverse the tree of the last
top-level) and certainly can be computed in linear time. The reverse
algorithm (untested!) is::
p = p_last
while p:
if p.isMarked():
next = p.threadBack()
p.doDelete()
p = next
else:
p.moveToThreadBack()
The point is that the position of next does *not* change when p is
deleted, regardless of whether p is a clone or not. This is a big
Aha.
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.
