order_list_by_dependencies.py

order_list_by_dependencies.py

import json

views = {
    "a1": {"position":0,"depends": []},
    "a2": {"position":0,"depends": ["a1"]},
    "a3": {"position":0,"depends": ["a2"]},
    "a5": {"position":0,"depends": ["a9"]},
    "a9": {"position":0,"depends": ["a7","a8"]},
    "a7": {"position":0,"depends": []},
    "a8": {"position":0,"depends": []},
    "br": {"position":0,"depends": ["a3","a5","a8","a7"]}
}

def order_views(p):
    def calculate_depths(d):
        # thanks to https://stackoverflow.com/a/59223344
        depths = {}
        stack = [(d, list(d.keys()))]
        while stack:
            cur, keys = stack.pop()
            while keys:
                k, keys = keys[0], keys[1:]

                klen = len(stack) + 1
                if k not in depths:
                    depths[k] = klen
                else:
                    # NOTE: keep the maximum value
                    depths[k] = klen if depths[k] < klen else depths[k]

                v = cur[k]
                if isinstance(v, dict):
                    stack.append((cur, keys))
                    stack.append((v, list(v.keys())))
                    break
        return depths

    data = []
    for curr_view in p:
        # Create a list of lists, on which each sub-list
        # contains the view name with its dependency (if any)
        if len(p[curr_view]['depends']) > 0:
            for dependent_view in p[curr_view]['depends']:
                data.append([curr_view, dependent_view])
        else:
            data.append([curr_view, ''])

    # Create a hierarchical tree
    # @thanks to
    # https://stackoverflow.com/questions/47497117/creating-hierarchical-tree-from-nested-dictionary-in-python
    roots = set()
    mapping = {}
    for child,parent in data:
        childitem = mapping.get(child,None)
        if childitem is None:
            childitem =  {}
            mapping[child] = childitem
        else:
            roots.discard(child)
        parentitem = mapping.get(parent,None)
        if parentitem is None:
            mapping[parent] = {child:childitem}
            roots.add(parent)
        else:
            parentitem[child] = childitem

    depths = calculate_depths(mapping[''])
    #print(json.dumps(mapping['']))

    for curr_view in p:
        p[curr_view]['position'] = depths[curr_view] if curr_view in depths else 0

    views_sorted = []
    for view in p:
        views_sorted.append({
            'view_name': view,
            'position': p[view]['position'],
            'depends': p[view]['depends']
        })

    newlist = sorted(views_sorted, key=lambda k: k['position'])
    return newlist

views_ordered = order_views(views)
for v in views_ordered:
    print(json.dumps(v))