Simplifying Sofeng’s Python Recursion Example

29 08 2008

In Python recursion example to navigate tree data, Sofeng presents this solution…

def outer(data):
    class Namespace: pass
    ns = Namespace()
    ns.level = 1

    def inner(data):
        print ' ' * ns.level + data['text']
        if data['count'] > 0:
            ns.level += 1
            for kid in data['kids']:
                inner(kid)
            ns.level -= 1

    inner(data)

if __name__ == '__main__':
    outer(data)

…for traversing a dictionary of the form:

data = {'count': 2,
        'text': '1',
        'kids': [{'count': 3,
                  'text': '1.1',
                  'kids': [{'count': 1,
                            'text': '1.1.1',
                            'kids': [{'count':0,
                                      'text': '1.1.1.1',
                                      'kids': []}]},
...
}

Since his blog doesn’t seem to support code formatting in the comments, I’m repeating my comment here:

You actually don’t need the ‘count’ keys in the data dictionary, nor do you need the “if data[‘count’] > 0:” block. The code can be simplified even further by using a closure instead of the ‘Namespace’ class, eliminating the need for two (“outer” & “inner”) routines:

def traverse(data):
    print ' ' * traverse.level + data['text']
    for kid in data['kids']:
        traverse.level += 1
        traverse(kid)
        traverse.level -= 1
if __name__ == '__main__':
    traverse.level = 1
    traverse(data)
Advertisements

Actions

Information

2 responses

10 02 2010
jotr

Please blog more about Plone!

10 08 2010
EvanPM

I liked your example, except these solutions are not generic enough for me. So i decided to make my own mini token machine.

This example takes a dictionary with keys and action and checks to see if the dictionary has this token then performs the action. This is so the path can be specified by a series of tokens. The token option can be removed and the treeclimber can be used by itself. Hope the
data = {‘count’: 2,
‘text’: ‘1’,
‘kids’: {‘count’: 3,
‘text’: ‘1.1’,
‘kids’: {‘count’: 1,
‘text’: ‘1.1.1’,
‘kids’: {‘count’:0,
‘text’: ‘1.1.1.1’,
‘kids’: “end”}}}}

def climbtree(parent, tokens):
if type(parent) is dict: # wasnt sure the best way to do this
for child in parent: # for each child inspect tokens
for token in tokens:
if token == child:
tokens[token](token) // call doThis() to print token
climbtree(parent[child], tokens) # make the child a parent now
else:
doThis(parent) # no children 😦

def doThis(action):
print ‘TOKEN : ‘, action

if __name__ == ‘__main__’:
tokens = {‘kids’:doThis, ‘count’: doThis }
climbtree(data, tokens)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: