Convert a list of dictionaries to a hierarchy structure

Question

I found my self in the need of some assitance, I'm trying to convert a list of dictionaries (you'll see) in to some sort of tree/hirarchy structure. All i have to work with is there depth-param en the current order of the list (which is correct).

functions = [
  {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'},
  {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'},
  {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'},
  {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'},
  {'depth': 1, 'line': 12,  'type': 'def', 'name': 'find_multi(self)'},
  {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'},
  {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'},
  {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'}
]

I was cosidering getting the result to look like the following hierarchy:

functions_hir = [{
    'value': {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    'children': [{

        'value': {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'},
        'children': [{

            'value': {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'},
            'children': []
        }]
    },{
        'value': {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'},
        'children': []
    },{
        'value': {'depth': 1, 'line': 12,  'type': 'def', 'name': 'find_multi(self)'},
        'children': [] 
    }]
},{
    'value': {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'},
    'children': []
},{
    'value': {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'},
    'children': [{

        'value': {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'},
        'children': []
    }]
}]

Now it's simple for me to iterate/recurse over it. But I have not had any luck with generating a hierarchy like this from my list (I have not even come close, I guess).. And I actually have no clue where to start.. Hope anyone can manage to help me out!

Answer 1

For the simple case shown, you could just keep track of parents and build your tree in one pass from the list, something like this would work:

hir = {'children': [], 'parent': None}
depth, current = 0, hir

for f in functions:
    f['children'] = [] 
    f_depth = f['depth']
    if depth == f_depth:
        current['children'].append(f)
        f['parent'] = current
        current = f
        depth += 1
    else:
        while depth > f_depth:
            depth -= 1
            current = current['parent']
        current['children'].append(f)
        f['parent'] = current
        current = f
       depth += 1

You want your root node to look like the other nodes, or you'll have to add special handling for that which is messy.