как изменить кортеж в словаре дерево питона

Question

есть кортеж, как это:

t = (
    (1, -1, 'python'), 
    (2, -1, 'ruby'), 
    (3, -1, 'php'), 
    (4, -1, 'lisp'), 
    (5, 1, 'flask'), 
    (6, 1, 'django'), 
    (7, 1, 'webpy'), 
    (8, 2, 'rails'), 
    (9, 3, 'zend'), 
    (10, 6, 'dblog') 
) 

Я хочу, чтобы изменить его в список, и каждый элемент списка представляет собой словарь. этот словарь имеет ключевого сына - это другой словарь. как изменить кортеж т, я надеюсь, что список-словарь дерева, как это:

l = [ 
{ 
    'id': 1, 
    'fid': -1, 
    'title': 'python', 
    'son': [ 
     { 
      'id': 5, 
      'fid': 1, 
      'title': 'flask', 
     }, 
     { 
      'id': 6, 
      'fid': 1, 
      'title': 'django', 
      'son': [ 
       { 
        'id': 10, 
        'fid': 6, 
        'title': 'dblog', 
       }, 
      ] 
     }, 
     { 
      'id': 7, 
      'fid': 1, 
      'title': 'webpy', 
     }, 
    ] 
}, 
{ 
    'id': 2, 
    'fid': -1, 
    'title': 'ruby', 
    'son': [ 
     { 
      'id': 8, 
      'fid': 2, 
      'title': 'rails', 
     }, 
    ] 
}, 
{ 
    'id': 3, 
    'fid': -1, 
    'title': 'php', 
    'son': [ 
     { 
      'id': 9, 
      'fid': 3, 
      'title': 'zend', 
     }, 
    ] 
}, 
{ 
    'id': 4, 
    'fid': -1, 
    'title': 'lisp', 
} 

]

большое спасибо

Answer 1

l = [] 
entries = {} 

for id, fid, title in t: 
    entries[id] = entry = {'id': id, 'fid': fid, 'title': title} 
    if fid == -1: 
     l.append(entry) 
    else: 
     parent = entries[fid] 
     parent.setdefault('son', []).append(entry) 

Здесь entries отслеживает все записи, которые были созданы до сих пор, так что вы можете добавить «сыновей» к ним напрямую, без необходимости искать дерево.

Предполагается, что ваш список t правильно сортируется по id и этим сыновьям всегда являются дети нижних ids.

Демо:

>>> from pprint import pprint 
>>> t = (
... (1, -1, 'python'), 
... (2, -1, 'ruby'), 
... (3, -1, 'php'), 
... (4, -1, 'lisp'), 
... (5, 1, 'flask'), 
... (6, 1, 'django'), 
... (7, 1, 'webpy'), 
... (8, 2, 'rails'), 
... (9, 3, 'zend'), 
... (10, 6, 'dblog') 
...) 
>>> l = [] 
>>> entries = {} 
>>> for id, fid, title in t: 
...  entries[id] = entry = {'id': id, 'fid': fid, 'title': title} 
...  if fid == -1: 
...   l.append(entry) 
...  else: 
...   parent = entries[fid] 
...   parent.setdefault('son', []).append(entry) 
... 
>>> pprint(l) 
[{'fid': -1, 
    'id': 1, 
    'son': [{'fid': 1, 'id': 5, 'title': 'flask'}, 
      {'fid': 1, 
      'id': 6, 
      'son': [{'fid': 6, 'id': 10, 'title': 'dblog'}], 
      'title': 'django'}, 
      {'fid': 1, 'id': 7, 'title': 'webpy'}], 
    'title': 'python'}, 
{'fid': -1, 
    'id': 2, 
    'son': [{'fid': 2, 'id': 8, 'title': 'rails'}], 
    'title': 'ruby'}, 
{'fid': -1, 
    'id': 3, 
    'son': [{'fid': 3, 'id': 9, 'title': 'zend'}], 
    'title': 'php'}, 
{'fid': -1, 'id': 4, 'title': 'lisp'}] 

Если «груда-приходит-после-ид» предположение не выдерживает, вам нужно добавить очередь детей идентификаторами для обработки еще:

l = [] 
entries = {} 
queue = {} 

for id, fid, title in t: 
    entries[id] = entry = {'id': id, 'fid': fid, 'title': title} 
    if id in queue: 
     entry['sons'] = queue[id] 
     del queue[id] 
    if fid == -1: 
     l.append(entry) 
    elif fid in entries: 
     parent = entries[fid] 
     parent.setdefault('son', []).append(entry) 
    else: 
     queue.setdefault(fid, []).append(entry) 

if queue: 
    raise ValueError('No entries found for fid(s) {}'.format(queue.keys())) 

Теперь порядок записей в t может быть совершенно случайным образом:

>>> import random 
>>> t = list(t) 
>>> random.shuffle(t) 
>>> l = [] 
>>> entries = {} 
>>> queue = {} 
>>> for id, fid, title in t: 
...  entries[id] = entry = {'id': id, 'fid': fid, 'title': title} 
...  if id in queue: 
...   entry['sons'] = queue[id] 
...   del queue[id] 
...  if fid == -1: 
...   l.append(entry) 
...  elif fid in entries: 
...   parent = entries[fid] 
...   parent.setdefault('son', []).append(entry) 
...  else: 
...   queue.setdefault(fid, []).append(entry) 
... 
>>> if queue: 
...  raise ValueError('No entries found for fid(s) {}'.format(queue.keys())) 
... 
>>> pprint(l) 
[{'fid': -1, 
    'id': 1, 
    'son': [{'fid': 1, 'id': 7, 'title': 'webpy'}, 
      {'fid': 1, 'id': 5, 'title': 'flask'}, 
      {'fid': 1, 
      'id': 6, 
      'sons': [{'fid': 6, 'id': 10, 'title': 'dblog'}], 
      'title': 'django'}], 
    'title': 'python'}, 
{'fid': -1, 
    'id': 2, 
    'son': [{'fid': 2, 'id': 8, 'title': 'rails'}], 
    'title': 'ruby'}, 
{'fid': -1, 
    'id': 3, 
    'son': [{'fid': 3, 'id': 9, 'title': 'zend'}], 
    'title': 'php'}, 
{'fid': -1, 'id': 4, 'title': 'lisp'}] 

fid может, быть любым id, при условии, что этот идентификатор называется где-то в последовательности t или -1 для корневых записей.

Answer 2

Создать отдельный словарь, который отображает идентификатор локального id- fid-title-son dictionary. Соедините локальные словари вместе, найдя fid в отдельном словаре. Если значение fid локального словаря равно -1, добавьте его в список. Это работает, потому что локальный словарь - это тот же объект, независимо от того, что его содержит.

Answer 3

Если первоначальный список заказан правильно, взгляните на решение Martijn Pieters. Однако, если вы не можете гарантировать заказ, одно из решений состоит в том, чтобы зациклиться дважды над исходным списком:

children = {} 
objs = [] 
l = [] 
for id, parent, title in t: 
    obj = { 
     "id": id, 
     "fid": parent, 
     "title": title 
    } 
    objs.append(obj) 

    if parent == -1: # keep only roots 
     l.append(obj) 

    if parent not in children: # append to children 
     children[parent] = [] 
    children[parent].append(obj) 

for obj in objs: 
    if obj["id"] in children: 
     obj["son"] = children[obj["id"]]