Sitemap

McMillan 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.

copyright 1999-2002
McMillan Enterprises, Inc.