recursive outline numbering for object trees

Gabriel Genellina gagsl-py2 at yahoo.com.ar
Mon Mar 30 18:15:36 CEST 2009


Alia Khouri <alia_khouri <at> yahoo.com> writes:

> Given the following class:
> 
> class Node(object):
>     def __init__(self, name, children=[], parent=None):
>         self.name = name
>         self.level = ''
>         self.children = children
>         self.parent = parent
> 
>     def __repr__(self):
>         name = self.__class__.__name__
>         return "<%s %s>" % (self.name, self.level)
> 
>     def __iter__(self):
>         yield self
>         for child in self.children:
>             child.parent = self
>             for subchild in iter(child):
>                 yield subchild
> 
> and the following example:
> 
> tree1 = Node('root    [1] ', [
>         Node('branch [1.1]', [
>             Node('leaf [1.1.1]', []),
>             Node('leaf [1.1.2]', []),
> 
>         ]),
>         Node('branch [1.2]', [
>             Node('leaf [1.2.1]', []),
>             Node('leaf [1.2.2]', []),
>         ])
>     ])
> 
> I would like to create a walk function which when given the root node
> (tree1) automatically sets the correct outline numbering for all its
> subnodes.
> 
> such that
> 
> for i in walk(tree):
>     print i.level
> 
> should give the following output:
> 
> 1
> 1.1
> 1.1.1
> 1.1.2
> 1.2
> 1.2.1
> 1.2.2
> 
> Now, I have scoured the web and found this (http://
> www.opensubscriber.com/message/python-list <at> python.org/9056939.html)
> solution from castironpi, which seems to work nicely:

With a slight modification (don't automatically advance in up/down) 
castironpi's code is easier to use in this case:

class up( Exception ): pass
class down( Exception ): pass

def outline():
    stack = [1]
    while True:
        try:
            # print 'next'
            yield '.'.join(str(s) for s in stack)
            stack[-1]+= 1
        except down:
            # print 'down'
            stack.append(0)
        except up:
            # print 'up'
            stack.pop(-1)

def walk(node, o=None):
    if o is None:
        o = outline()
    node.level = o.next()
    yield node
    if node.children:
        o.throw(down)
        for child in node.children:
            for subnode in walk(child, o):
                yield subnode
        o.throw(up)

(BTW, there is a proposal for a "yield from" statement, so the last part would 
become:

        o.throw(down)
        for child in node.children:
            yield from walk(child, o)
        o.throw(up)

and I think it's a lot clearer)

> As an aside, if a solution is possible as an external walk function
> would it be possible to work in __iter__?

return walk(self)

-- 
Gabriel Genellina





More information about the Python-list mailing list