pythonic way of depth first and breadth first tree iterators

[Gonçalo Rodrigues]

On Fri, 15 Mar 2002 20:37:59 -0500, Dave Reed <dreed at capital.edu> wrote:

>
>We're planning to use Python in our CS1 and CS2 courses next year so
>I'm beginning to think about the issues for these courses.
>
>http://www.python.org/doc/current/lib/typeiter.html states:
>
>  If a container supports different types of iteration, additional
>  methods can be provided to specifically request iterators for those
>  iteration types. (An example of an object supporting multiple forms
>  of iteration would be a tree structure which supports both
>  breadth-first and depth-first traversal.)
>
>I don't quite understand exatly what that is saying - what would be
>the pythonic way of defining/calling separate breadth first and depth
>first iterators for a binary tree class - i.e., is there a way to
>indicate which method to use when you make the call to iter() so that
>I could do something like: for node in tree('depth'):
>
>and
>
>for node in tree('breadth'):
>
>Or is that just implying that I can make a depth first class iterator
>class and breadth first iterator class that both support the
>corresponding next() method and do something like:
>
>d = DepthIter(tree) 
>for node in d:
>
>where DepthIter is a class that takes a tree as a parameter to its
>constructor and has a next() method that returns the nodes in a depth
>first manner. And similarly, write a BreadthIter class?
>
>Thanks,
>Dave

The standard way to define an iterator is via

def __iter__(self):
    <whatever>

and THIS iterator is what is used in the for loop, e.g

for node in tree:
    <whatever>

But there are classes(trees, dictionaries, etc.) where more than one
iterator (more than one to traverse it) is useful.

In the example of a tree the __iter__ could be the breadth-first
traversal and then you could code ANOTHER iterator, e.g.

def depth_first(self):
    <whatever>

To use this second iterator, you just do

for node in tree.depth_first():
    <whatever>

Hope it helps.

Best regards,
Gonçalo Rodrigues