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

[Kent Johnson]

Dave Kuhlman wrote:
> 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()

I think Version 2 is preferable. Not only is it shorter, but it is 
safer. Version 1 has essentially a singleton iterator so any code that 
tries to iterate the same node more than once will fail.  For example 
multi-threaded code, or perhaps during an iteration there could be a 
reason to start a new iteration.

Kent