recursive outline numbering for object trees

[Alia Khouri]

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/[email protected]/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

 

[Gabriel Genellina]

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)

 

[Alia K]

Thanks Gabriel. Your solution works like a charm. (-:

AK

 

[Gabriel Genellina]

Thanks Gabriel. Your solution works like a charm. (-:

You should thank Aaron Brady who wrote the original function. I just
smoothed some edges and glued it with your own code.

 

[Alia K]

You should thank Aaron Brady who wrote the original function. I just  
smoothed some edges and glued it with your own code.

Ah, Aaron Brady is castironpi... Well, thank you both then. (-:

AK