Dave Kuhlman wrote: > On Fri, Jul 13, 2007 at 12:39:40PM +1200, John Fouhy wrote: >> On 13/07/07, Dave Kuhlman <[EMAIL PROTECTED]> 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 _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
