recursive outline numbering for object trees
Alia Khouri
alia_khouri at yahoo.com
Mon Mar 30 11:31:38 EDT 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