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

[Dave Kuhlman]

On Fri, Jul 13, 2007 at 12:39:40PM +1200, John Fouhy wrote:
> 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 #########

John -

That is so cool.  I can't believe that it is so simple and elegant. 
I thought that a stack was involved in the solution, but I could
not figure out how to use it.  Thanks.

And, to extend this a bit more, here are two slightly modified
versions of your solution that implement classes whose
instances are iterators.


#
# Version #1 -- This version has a next() method, as required by
#   the iterator protocol.
#
class Node(object):
    def __init__(self, value='<no value>', children=None):
        self.value = chr(value + 97) * 3
        if children is None:
            children = []
        else:
            self.children = children
    def walk_tree(self):
        # stack to hold nodes as we walk through
        stack = []
        stack.append(self)
        while stack:
            node = stack.pop()
            # reverse children to get the right order.
            stack.extend(reversed(node.children))
            yield node
    def __iter__(self):
        self.iterator = self.walk_tree()
        return self
    def next(self):
        return self.iterator.next()


#
# Version #2 -- This version does not have a next() method, but
#   the iterators returned by __iter__() do have a next().
#
class Node(object):
    def __init__(self, value='<no value>', children=None):
        self.value = chr(value + 97) * 3
        if children is None:
            children = []
        else:
            self.children = children
    def walk_tree(self):
        # stack to hold nodes as we walk through
        stack = []
        stack.append(self)
        while stack:
            node = stack.pop()
            # reverse children to get the right order.
            stack.extend(reversed(node.children))
            yield node
    def __iter__(self):
        return self.walk_tree()


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


#
# Here is a function to exercise the iterator.
#
def test():
    for node in TREE:
        print 'value: %s' % (node.value, )

Dave



-- 
Dave Kuhlman
http://www.rexx.com/~dkuhlman