SitemapMcMillan Enterprises, Inc. Python Pages Sockets HOWTO Distributing Python Programs A Python C++ API Embedding Python Stackless Python Getting Started with Stackless Fibonacci Generators Walking the Leaves of a Tree Parsing SelectDispatcher MkSQL Import Hooks Java Samples About ME Inc.
|
Walking the Leaves of a Tree
Note: These examples are based on release version 1.1.1 (3/29/00) of stackless. Some samples may require tweaking for release 1.2; I don't know. You can be fairly sure that sooner or later, these examples will become obsolete.
This is a fun one. The problem is to define something that will return the leaves of a tree in depth-first, left to right order. Let's call this thing fringe . A simple use is as follows:
def printinorder(lst):
print repr(lst)
rslt = fringe(lst)
while rslt:
nxt, val = rslt
print val,
rslt = nxt()
print
So printinorder([0, 1, 2, 3, 4, 5, 6]) will print:
0 1 2 3 4 5 6
as will printinorder([0, 1, [2, [3]], [4,5], [[[6]]] ]) .
But, just for the heck of it, let's not keep explicit track of the nesting depth, but use recursion instead.
def fringe(lst, top=None, depth=1, verbose=0):
if verbose:
print " "*depth, "fringe initializing"
back = continuation.caller()
if top is None:
top = back
for e in lst:
if type(e) is _listtype:
if verbose:
print " "*depth, "fringe recursing"
fringe(e, top, depth+1)
else:
if verbose:
print " "*depth, "fringe returning", e
top.update()
top.jump_cv(e)
if verbose:
print " "*depth, "fringe ending"
back.flags = 4
back()
Notice there are two continuation objects used in this code. The first, back , is the continuation of the code that called us. That is, it is where we "return" to. The other, top , is the very first back - that is, it's the code that started this. It's also the code that wants the leaves of the tree. So while it's back we "return" to, it's top we send the results to. Note that the depth argument is not used in fulfilling the essential duties of the code. It's only there so that if you turn verbose on, you get nicely indented output.
There's only one new thing in this code. The back.flags = 4 is the same thing as c.link = None we saw in a previous example, except done from the other side. That is, this is a way of getting back to properly self-destruct after it's used. Without it, we would leak continuation objects, (again, either the GC in Python 2.0 or Christian's new version may fix this problem).
Finally, a more sophisticated testbed, which compares the results of walking two distinct trees.
def fcmp(lst1, lst2, verbose=0):
if verbose:
print "comparing", lst1, "to", lst2
rslt1 = fringe(lst1)
rslt2 = fringe(lst2)
while rslt1 and rslt2:
#print ".",
nxt1, v1 = rslt1
nxt2, v2 = rslt2
if v1 != v2:
if verbose:
print "Difference in values:", v1, v2
return cmp(v1, v2)
rslt1 = nxt1()
rslt2 = nxt2()
nxt1.link = None
nxt2.link = None
if rslt1 is None and rslt2 is None:
if verbose:
print "Both lists exhausted"
return 0
elif rslt1 is None:
if verbose:
print "Values left on list 2"
return -1
else:
if verbose:
print "Values left on list 1"
return 1
If you try rewriting this yourself, be warned: it's relatively easy to define fringe so that printinorder succeeds, but fcmp breaks.
Next: A "classic" example.
|