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.

Answer 2

you could use recursive approach, this function will make dictionary you want in linear time:

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 = 0
def gather(d):
    global i
    res = []
    while i < len(functions):
        if functions[i]["depth"] < d:
            return res
        elif functions[i]["depth"] == d:
            value, i = functions[i], i + 1
            children = gather(d + 1)
            res.append({"value": value, "children": children})
    return res

result = gather(0)

or you could do it without global variables:

def gather(d, i):
    res = []
    while i < len(functions):
        if functions[i]["depth"] < d:
            return i, res
        elif functions[i]["depth"] == d:
            value = functions[i]
            i, children = gather(d + 1, i + 1)
            res.append({"value": value, "children": children})
    return i, res

result = gather(0, 0)[1]