recursive outline numbering for object trees

Alia Khouri alia_khouri at yahoo.com
Mon Mar 30 17:31:38 CEST 2009


Hi,

Here my problem description:

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:


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(1)
        except up:
            # print 'up'
            stack.pop(-1)
            stack[-1] += 1


def test_outline():
    print
    o = outline()
    print o.next()
    print o.throw(down)
    print o.throw(down)
    print o.next()
    print o.throw(up)
    print o.throw(down)
    print o.next()

running test_outline() generates the required output so, so I tried to
incorporate the above into my walk function with mixed results
(warning: it's ugly):

from itertools import count

def walk(node, level=outline(), last=None, i=count(1), root=True):
    '''tree walker assigns parent attribute, creates numbered outline
    '''
    if root:
        node.level = level.next()
    yield node
    if last:
        node.level = last
        last = None
    if node.children:
        next = level.throw(down)
    elif i.next() == 5: # length of nodes (hardcoded here for tsting)
        raise StopIteration
    else:
        next = level.throw(up)
    for child in node.children:
        child.parent = node
        child.level = next or level.next()
        if child == node.children[-1]:
            last = child.level
        for subchild in walk(child, level, last, i, root=False):
            yield subchild

works for

tree = Node('root    [1] ', [
        Node('branch [1.1]', [
            Node('leaf [1.1.1]', []),

        ]),
        Node('branch [1.2]', [
            Node('leaf [1.2.1]', []),
        ])
    ])

but barfs for the required tree1 (above).

I've kinda hit a wall here, so any help would be appreciated.

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

Best,

AliaK













More information about the Python-list mailing list