Skip to content

Instantly share code, notes, and snippets.

@sardbaba
Created November 14, 2020 08:03
Show Gist options
  • Save sardbaba/118fd106b9c1595937f19ac69968e581 to your computer and use it in GitHub Desktop.
Save sardbaba/118fd106b9c1595937f19ac69968e581 to your computer and use it in GitHub Desktop.
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment