# 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