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

Dave Kuhlman dkuhlman at rexx.com
Fri Jul 13 20:46:57 CEST 2007

```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
```