[Tutor] Here is newbie doc on how to implement generators

[John Fouhy]

On 13/07/07, Dave Kuhlman <dkuhlman at rexx.com> wrote:
> And, I have a question -- If you look at the example of the
> iterative (non-recursive) generator (the Doubler class), you will
> see that it walks a list, not a tree.  That's because I was *not*
> able to figure out how to implement a non-recursive tree walk
> generator.

You should just be able to use a stack -- push the children onto a
stack, then pop them off and walk through them.

Here's an example, using tuples and lists as a basic tree data type:

####### treetest.py #########

TREE = (0, [(1, [(2, [(3, []),
                      (4, []),
                      (5, [(6, []),
                           (7, []),
                           (8, []),
                           (9, []),
                           ]),
                      (10, [(11, []),
                            (12, []),
                            ]),
                      ]),
                 (13, [(14, []),
                       (15, []),
                       (16, [])]),
                 (17, []),
                 (18, []),
                 ]),
            (19, []),
            (20, []),
            ])

def walkTree(tree):
    # stack to hold nodes as we walk through
    stack = []
    stack.append(tree)

    while stack:
        value, children = stack.pop()
        for child in reversed(children):  # reverse children to get
the right order.
            stack.append(child)
        yield value

if __name__ == '__main__':
    for value in walkTree(TREE):
        print value

####### treetest.py #########

HTH!

-- 
John.