[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
More information about the Tutor
mailing list