Wie dict mit Kindern von dict mit parent_id erstellen

Question

Wie aus dieser dict erhalten:

cats = [ 
    {'parent_id': False, 'id': 1, 'title': u'All'}, 
    {'parent_id': False, 'id': 2, 'title': u'Toys'}, 
    {'parent_id': 2, 'id': 3, 'title': u'Toypads'}, 
    {'parent_id': 3, 'id': 4, 'title': u'Green'}, 
    ] 

So etwas wie das?

cats = [ 
{'parent_id': False, 'id': 1, 'title': u'All'}, 
{'parent_id': False, 
'children': [{'parent_id': 2, 
       'children': [{'parent_id': 3, 'id': 4, 
          'title': u'Green'}], 
       'id': 3, 'title': u'Toypads'}, 
       [{'parent_id': 3, 'id': 4, 'title': u'Green'}]], 
'id': 2, 'title': u'Toys'} 
] 

Ich brauche es, um ein Menü \ Untermenü in Jinja2 zu bauen. Ich habe einen sehr schlechten Code geschrieben. Es wäre eine elegantere Lösung.

# Step 1: index all categories by id and add an element 'children' 
nodes = {} 
for cat in cats: 
    nodes[cat['id']] = cat 
    cat['children'] = [] 

# Step 2: For each category, add it to the parent's children 
for index, cat in nodes.items(): 
    if cat['parent_id']: 
     nodes[cat['parent_id']]['children'].append(cat) 

# Step 3: Keep only those that do not have a parent 
cats = [c for c in nodes.values() if not c['parent_id']] 

Beachten Sie, dass jeder Knoten ein Attribut 'children', das sein kann, eine leere Liste oder eine Liste mit einem oder mehreren Knoten genannt haben:

q = dict(zip([i['id'] for i in cats], cats)) 

    from collections import defaultdict 
    parent_map = defaultdict(list) 

    for item in q.itervalues(): 
     parent_map[item['parent_id']].append(item['id']) 

    def tree_level(parent): 
     for item in parent_map[parent]: 
      yield q[item] 
      sub_items = list(tree_level(item)) 
      if sub_items: 
       for ca in cats: 
        if ca['id'] == item: 
         cats[cats.index(ca)]['children'] = sub_items 
         for s_i in sub_items: 
          try: 
           for ca_del_child in cats: 
            if ca_del_child['id'] == s_i['id']: 
             del cats[cats.index(ca_del_child)] 
          except: 
           pass 
       yield sub_items 
    for i in list(tree_level(False)): 
     pass 

Answer 1

Hier ist eine ziemlich präzise Lösung:

cats = [{'parent_id': False, 'id': 1, 'title': u'All'}, 
     {'parent_id': False, 'id': 2, 'title': u'Toys'}, 
     {'parent_id': 2, 'id': 3, 'title': u'Toypads'}, 
     {'parent_id': 3, 'id': 4, 'title': u'Green'},] 

cats_dict = dict((cat['id'], cat) for cat in cats) 

for cat in cats: 
    if cat['parent_id'] != False: 
     parent = cats_dict[cat['parent_id']] 
     parent.setdefault('children', []).append(cat) 

cats = [cat for cat in cats if cat['parent_id'] == False] 

Beachten Sie, dass die Vergleiche auf False sind in der Regel nicht notwendig, aber sie sollten Sie mit 0 als seine ID oder parent_id eine Katze hatte hier für den Fall verwendet werden. In diesem Fall würde ich None anstelle von False für eine Katze ohne Eltern verwenden.

Answer 2

Es kann wie folgt durchgeführt werden. Wenn Sie keine leeren children Listen möchten, können Sie sie einfach zwischen Schritt 2 und Schritt aus jeder Kategorie in nodes entfernen.

Beachten Sie auch, dass das obige davon ausgeht, dass ein Knoten mit einem gegebenen parent_id tatsächlich existiert. Beachten Sie schließlich, dass if not c['parent_id'] auch wahr ist, wenn ein Knoten mit der ID Null vorhanden ist. Sie müssen also daran denken, dass dies möglich ist.