Recursive generator

[Ben C]

On 2008-02-13, Erich <sophacles at gmail.com> wrote:
> On Feb 12, 5:15 am, Ben C <spams... at spam.eggs> wrote:
>> I think this works OK, but it seems a bit odd. Is there something more
>> "Pythonic" I should be doing?
>
> I have a similar tree to the one you describe here at work. I have a
> visit function that is very similar to yours, but takes function
> arguments for doing pre- and/or post- order operations on the node
> (code below). It also yeilds the nodes, but in a postorder manner. The
> flexibility is quite useful.

Yes that's pretty good too, although usually I want either a callback or
to yield a result, but not both, and often a function of a node passed
in to say whether to prune at that point (i.e. not visit further
descendents).

For various other reasons I've now gone to a tree where each node has a
parent, sibling and first child reference. No children array. The
generator yields tuples of (DOWN, node), (RIGHT, node) and (UP, node),
and is not itself recursive-- it uses the parent references instead.

If the caller wants pre-order it just ignores UP visits. If it wants
post-order it ignores DOWN. The distinction between DOWN and RIGHT is
important if the caller wants to push and pop stacks as it walks the
tree.

The generator itself is not so pretty, but the caller can more easily do
everything with it that it would be able to do if it was recursive
itself.

    def genDescendents(self, prune = None):
        node = self
        dir = DOWN
        while 1:
            if prune and prune(node):
                if dir == DOWN: dir = RIGHT
            else:
                yield dir, node

            # Go down if we can, unless we've been there already, else
            # right, or as a last resort, up.
            if dir != UP:
                if node.firstChild:
                    node = node.firstChild
                    dir = DOWN
                else:
                    # Back up through leaf nodes-- so we change dir but not
                    # node. Sort of a U-turn.
                    dir = UP
            elif node.sibling:
                node = node.sibling
                dir = RIGHT
            elif node.parent:
                node = node.parent
                dir = UP
            else: break

> Regards,
> Erich
>
>     def visit(self,prefunc = None, postfunc = None):
>         if prefunc:
>             prefunc(self)
>
>         for child in self.children:
>             for y in child.visit(prefunc, postfunc):
>                 yield y
>
>         if postfunc:
>             postfunc(self)
>
>         yield self