p.deletePositionsInList now on trunk. Pls use and test
Edward K. Ream
very tricky code works, even for clones. A substantial unit tests
also works, and it does test clones.
Please test this in your code/plugins, and report any problems
immediately.
Passing an iterator to the method just adds needless complication.
Instead, 'self' (the receiver, in SmallTalk parlance) now specifies
the starting node of the traversal, and afterLastNode specifies the
node *after* the last node to be traversed.
Here is p.deletePositionsInList. As you can see, the docstring is
longer than the code. Read the docstring carefully or suffer the
consequences!
def deletePositionsInList (self,afterLastNode,aList,callback):
'''Traverse the nodes from self up to but *not* including
afterLastNode. The
traversal continues to the end of the outline if afterLastNode is
None. The
**range** of the traversal is the set of nodes from self to the
node
*before* afterLastNode.
This method calls the callback for any position in aList found in
the range,
excluding any node whose ancestor has already been passed to the
callback.
The callback takes one explicit argument, p. As usual, the
callback can bind
values using keyword arguments. The callback may delete p or move
p out of
the range. The callback **must not** move p within range.
'''
p = self.copy()
after = afterLastNode and afterLastNode.copy()
while p and p != after:
if p in aList:
next = p.nodeAfterTree()
callback(p.copy())
p = next
else:
p.moveToThreadNext()
Edward
P.S. Here is how Leo uses deletePositionsInList to handle resurrected
nodes::
def deleteUnvisitedNodes (self,root):
'''Delete unvisited nodes in root's subtree, not including root.
Actually, instead of deleting the nodes, we move them to be
children of the
'Resurrected Nodes' r.
'''
at = self
if not root.hasChildren():
return
# Carefully set up the arguments.
aList = [z.copy() for z in root.subtree() if not z.isVisited()]
r = at.createResurrectedNodesNode()
afterLastNode=root.nodeAfterTree() # Do this *after* creating r!
callback=at.defineResurrectedNodeCallback(r,root)
# Now move the nodes.
root.firstChild().deletePositionsInList(afterLastNode,aList,callback)
def createResurrectedNodesNode(self):
'''Create a 'Resurrected Nodes' node as the last top-level
node.'''
at = self ; c = at.c ; tag = 'Resurrected Nodes'
# Find the last top-level node.
last = c.rootPosition()
while last.hasNext():
last.moveToNext()
if last.h == tag:
# The 'Resurrected Nodes' node already exists.
p = last
else:
# Create the 'Resurrected Nodes' node after 'last'.
p = last.insertAfter()
p.setHeadString(tag)
p.expand()
return p
def defineResurrectedNodeCallback (self,r,root):
'''Define a callback that moves node p as r's last child.'''
def callback(p,r=r.copy(),root=root):
'''The resurrected nodes callback.'''
child = r.insertAsLastChild()
child.h = 'From %s' % root.h
p.moveToLastChildOf(child)
if g.unitTesting:
# g.trace(p.h,r.h)
pass
else:
g.es('resurrected node:',p.h,color='red')
g.es('in file:',root.h,color='blue')
return callback
EKR
Ville M. Vainio
(if you think it'll speed it up or whatever)?
Also, why is there afterLastNode? Why not just stop when all the
positions have been deleted?
> --
> You received this message because you are subscribed to the Google Groups "leo-editor" group.
> To post to this group, send email to leo-e...@googlegroups.com.
> To unsubscribe from this group, send email to leo-editor+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/leo-editor?hl=en.
>
>
--
Ville M. Vainio @@ Forum Nokia
Terry Brown
"Edward K. Ream" <edre...@gmail.com> wrote:
> Passing an iterator to the method just adds needless complication.
Looks like a useful method. Wouldn't passing in an iterator / list be more versatile? For example the context menu multiple selected nodes delete (and the unimplemented cut/copy) could use it then.
Cheers -Terry
Edward K. Ream
> Why not just have c.deletePositionsInList? With possible root argument
> (if you think it'll speed it up or whatever)?
That's possible, but imo the method more naturally belongs in the
position class.
> Also, why is there afterLastNode? Why not just stop when all the
> positions have been deleted?
Because all positions need not be deleted explicitly. Indeed, a p1
and p2 may be in aList such that p2 is a descendant of p1. In that
case, p1 will be explicitly deleted (moved), but p2 will "go along for
the ride". This is an extremely important benefit to the client code:
it doesn't have to worry about redundant deletes.
One could image doing what you suggest, but it adds yet another
theorem to be proved. Perhaps that would be easy. Perhaps not. I
suspect clones might rear their ugly heads, and I would rather move on
now...
Edward
Edward K. Ream
> Looks like a useful method. Wouldn't passing in an iterator / list be more versatile? For example the context menu multiple selected nodes delete (and the unimplemented cut/copy) could use it then.
Imo, the present code is easy enough to use.
More to the point, today's work shows that using the iterator won't
work. In fact, *not* using iterators is an extremely important
optimization.
The essential problem is that iterators assume that the tree they are
iterating over will not change. Absolutely all bets are off if that
isn't so. To avoid this problem, one could "capture" the iterator as
follows:
positions = [z.copy() for z in theIter]
...
for p in positions:
Alas, this is a serious gc bug: it creates one position for every
position in the traversal.
I then attempted to compute the first and afterLast nodes directly
from the iterator. But how to do this?
Wrong 1:
for p in theIter:
if not first: first = p.copy()
afterLast = p.copy # Wrong: p is undefined outside theIter.
Wrong 2:
for p in theIter:
if not first: first = p.copy()
last = p.copy() # Wrong: the same gc bug in a different form.
afterLast = last.threadNext()
Furthermore, both of these wrong approaches will waste a lot of time
iterating through an entire tree.
In short, we had best stick with what we have.
Edward
Ville M. Vainio
> One could image doing what you suggest, but it adds yet another
> theorem to be proved. Perhaps that would be easy. Perhaps not. I
> suspect clones might rear their ugly heads, and I would rather move on
> now...
We can easily prune the positions that are descendants of other
positions in the list before sweeping out the positions.
I just feel that the api you suggest is quite cryptic for something
user feels should be a straightforward operation - delete these
positions from the tree c.
Edward K. Ream
> We can easily prune the positions that are descendants of other
> positions in the list before sweeping out the positions.
>
> I just feel that the api you suggest is quite cryptic for something
> user feels should be a straightforward operation - delete these
> positions from the tree c.
Alright. Let me attempt to do as you suggest.
Edward
Terry Brown
"Edward K. Ream" <edre...@gmail.com> wrote:
> Imo, the present code is easy enough to use.
But not for the 'context menu delete multiple selected nodes' (CMDMSN) case, where the selected nodes may not be contiguous.
> The essential problem is that iterators assume that the tree they are
> iterating over will not change.
I guess CMDMSN uses vnodes rather than positions for that reason. Appended.
Cheers -Terry
def deletenodes_rclick_cb():
c.endEditing()
cull = []
# try and find the best node to select when this is done
nextviz = []
tmp = pl[0].copy().moveToVisBack(c)
if tmp:
nextviz.append(tmp.v)
tmp = pl[-1].copy().moveToVisNext(c)
if tmp:
nextviz.append(tmp.v)
for nd in pl:
cull.append((nd.v, nd.parent().v or None))
u.beforeChangeGroup(current,undoType)
for v, vp in cull:
for pos in c.vnode2allPositions(v):
if c.positionExists(pos) and pos.parent().v == vp:
bunch = u.beforeDeleteNode(pos)
pos.doDelete()
u.afterDeleteNode(pos,undoType,bunch)
c.setChanged(True)
break
u.afterChangeGroup(current,undoType)
# move to a node that still exists
for v in nextviz:
pos = c.vnode2position(v)
if c.positionExists(pos):
c.selectPosition(pos)
break
else:
c.selectPosition(c.allNodes_iter().next())
c.redraw()
Edward K. Ream
> On Tue, 3 Aug 2010 13:38:50 -0500
> "Edward K. Ream" <edre...@gmail.com> wrote:
>
>> Imo, the present code is easy enough to use.
>
> But not for the 'context menu delete multiple selected nodes' (CMDMSN) case, where the selected nodes may not be contiguous.
>
>> The essential problem is that iterators assume that the tree they are
>> iterating over will not change.
>
> I guess CMDMSN uses vnodes rather than positions for that reason. Appended.
Why not step through the entire outline? p = c.rootPosition() ;
afterLastNode = None. This should work for any set of nodes in the
outline.
Edward
Edward K. Ream
Do you have something better than this O(N**2) algorithm?
# Remove any items in aList whose ancestors are in aList.
aList2 = []
for z in aList:
for z2 in aList:
if z2.isAncestorOf(z):
break
else:
aList2.append(z)
In general this will be fast enough because we expect small lists, but
I'm not sure that the minor convenience is worth the worst-case
behavior.
Edward
Ville M. Vainio
> In general this will be fast enough because we expect small lists, but
> I'm not sure that the minor convenience is worth the worst-case
> behavior.
The convenience is not minor - the original API is not something that
should be published at all (i.e. it should be a private method).
c.deletepositions(list-of-positions-to-delete) is something you can
understand in a heartbeart.
This should be good enough for now. If it ever proves to be a problem,
it can be optimized. One optimization could me sorting positions by
depth and only comparing a position to "deeper" positions (because a
position can only be ancestor of a position with bigger depth).
Lexical sorting of the positions in general can give us linear speed -
if we have positions
1,1,3
1,1,3,2
1,2,12,2
We will see that a position can only be ancestor of the positions
directly following it in lexically sorted order.
But that's something that can be done later.
>
> Edward
>
> --
> You received this message because you are subscribed to the Google Groups "leo-editor" group.
> To post to this group, send email to leo-e...@googlegroups.com.
> To unsubscribe from this group, send email to leo-editor+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/leo-editor?hl=en.
>
>
--
Terry Brown
"Edward K. Ream" <edre...@gmail.com> wrote:
> > "Edward K. Ream" <edre...@gmail.com> wrote:
> >
> >> Imo, the present code is easy enough to use.
> >
> > But not for the 'context menu delete multiple selected nodes' (CMDMSN) case, where the selected nodes may not be contiguous.
> >
> Why not step through the entire outline? p = c.rootPosition() ;
> afterLastNode = None. This should work for any set of nodes in the
> outline.
Um, because I didn't spend enough time studying the API to fully understand what it required. Yes, I suppose that would work. So p and afterLastNode are really just hints to the method to allow it to not step through parts of the outline which the caller knows do not include any of the target nodes? So they could default to p = c.rootPosition() and afterLastNode = None, giving you the
c.callback_on_list(aList, callback, start=c.rootPosition(), end=None) API?
Cheers -Terry
Edward K. Ream
>> Why not step through the entire outline? p = c.rootPosition() ;
>> afterLastNode = None. This should work for any set of nodes in the
>> outline.
>
> Um, because I didn't spend enough time studying the API to fully understand what it required. Yes, I suppose that would work. So p and afterLastNode are really just hints to the method to allow it to not step through parts of the outline which the caller knows do not include any of the target nodes? So they could default to p = c.rootPosition() and afterLastNode = None, giving you the
> c.callback_on_list(aList, callback, start=c.rootPosition(), end=None) API?
Yes, but following Ville's suggestion things have changed :-) There
is no more afterLastNode arg: the scan continues until the end of the
outline or all positions have been found.
If you are actually deleting nodes this is perfectly safe. If you are
moving nodes, it would be best to move nodes to a child of a node that
can not be affected by any other moves. This is true for the
top-level "Resurrected Nodes" node.
Edward
Edward K. Ream
> The convenience is not minor - the original API is not something that
> should be published at all (i.e. it should be a private method).
I do not entirely agree, but nevertheless I've followed this
suggestion at rev 3200. The new code is almost as simple as the old::
def deletePositionsInList (self,aList,callback):
# docstring omitted.
p = self.copy()
while p and aList:
if p in aList:
aList.remove(p)
for z in aList:
if p.isAncestorOf(z):
aList.remove(z)
next = p.nodeAfterTree()
callback(p.copy())
p = next
else:
p.moveToThreadNext()
As you can see, aList continually gets shorter, so there is a tiny
speed improvement in the test 'p in aList', at the cost, of course, of
removing descendant nodes from aList. I suspect speed will never be
an issue.
Nevertheless, I am a bit uneasy about the new api. The explicit
afterLastNode no longer exists, so there is no easy way to describe
the range of the traversal. This doesn't *necessarily* have to
matter, but it could matter, and it might lead to some nasty bugs.
True, there can be no problem in the "natural" case, in which the
callback just deletes the node. But trying to describe the
circumstances in which *moves* are safe brings us right back to the
range defined by p and afterLastNode. So the easy cases are
simplified, while the harder cases might be obscured.
In any case, I think we can live with the newest code. I don't plan
any changes unless there are real bugs.
Edward
P.S. As I write this I see that we could define a default callback
that would just delete the node. Might as well do it.
EKR
Edward K. Ream
> P.S. As I write this I see that we could define a default callback
> that would just delete the node.
Done at rev 3201. This default case should be quite useful.
Edward