Se quer uma estrutura hierárquica, então uma lista contendo todos os objetos não é uma boa opção.
Uma alternativa seria cada Folder
ter uma lista contendo apenas os seus filhos diretos. Usando o seu exemplo, o Folder
_ROOT teria uma lista de filhos contendo apenas "A" e "B". Já o Folder
"A" teria uma lista contendo apenas "C", que por sua vez teria uma lista contendo apenas "E", e por fim "B" teria uma lista contendo apenas "D".
Ou seja, adicione esta lista de filhos na sua classe Folder
:
class Folder:
def __init__(self, id, title, parent_id):
self.id = id
self.title = title
self.parent_id = parent_id
self.children = [] # lista de filhos, começa vazia
Se a ideia é partir da lista que você tem, então você percorre ela e para cada elemento verifica quem é o pai, e adiciona na lista de filhos deste:
def build_tree(folders):
root = None
for folder in folders:
if folder.parent_id < 0: # assumindo que o root tem parent_id negativo
root = folder
else: # procura o pai deste folder, e atualiza a lista de filhos deste
parent = next(filter(lambda f: f.id == folder.parent_id, folders))
parent.children.append(folder)
return root # retorna o nó raiz
Estou assumindo que o Folder
raiz é o que tem parent_id
negativo, e que só terá um. Para os demais, eu procuro pelo pai e adiciono o folder
atual na lista de filhos do pai.
Claro que uma forma melhor seria poder passar a lista de filhos no próprio construtor, ou criar um método para adicionar. Mas se a ideia é construir a partir da lista, teria que ser assim (até daria para construir um dicionário que mapeia cada id
com o respectivo Folder
, assim não precisaria usar filter
).
Também estou assumindo que filter
sempre encontrará o id
em questão, ou seja, não estou validando a estrutura. Você pode incluir esta verificação, bastando checar se next
lança um StopIteration
, por exemplo.
Depois, tendo o folder
raiz, podemos fazer uma função recursiva que imprime toda a estrutura a partir dele:
def print_tree(folder, indent=''):
print(f'{indent}{folder.title}')
for child in folder.children:
print_tree(child, indent + ' ')
Ou seja, primeiro imprime o Folder
atual e depois imprime os seus filhos (adicionando espaços no início para ficar indentado). Testando:
folders = []
folders.append(Folder(id=0, title='_ROOT', parent_id=-1000))
folders.append(Folder(id=1, title='A', parent_id=0))
folders.append(Folder(id=2, title='D', parent_id=3))
folders.append(Folder(id=3, title='B', parent_id=0))
folders.append(Folder(id=4, title='C', parent_id=1))
folders.append(Folder(id=5, title='E', parent_id=4))
root = build_tree(folders)
print_tree(root)
Saída:
_ROOT
A
C
E
B
D
Solução - na minha opinião - melhor
Como já dito acima, uma forma que considero melhor seria cada Folder
poder ser criado já com seus filhos, além de ter um método para adicionar um novo filho:
class Folder:
def __init__(self, id, title, parent_id=None, children=None):
self.id = id
self.title = title
self.parent_id = parent_id
self.children = []
if children is not None:
for child in children:
self.add_child(child)
# adiciona "child" na lista de filhos, e atualiza o parent_id deste
def add_child(self, child):
self.children.append(child)
child.parent_id = self.id
No construtor eu optei por adicionar os filhos um a um usando o método add_child
, pois ele já trata da lógica de atualizar o parent_id
de cada filho (assim eu reaproveito esta lógica, em vez de duplicá-la no construtor).
Desta forma, eu elimino a necessidade de usar a lista (e consequentemente, também não preciso mais da função build_tree
):
c = Folder(id=4, title='C', children=[Folder(id=5, title='E')])
a = Folder(id=1, title='A', children=[c])
b = Folder(id=3, title='B', children=[Folder(id=2, title='D')])
root = Folder(id=0, title='_ROOT', parent_id=-1000, children=[a, b])
print_tree(root)
# adicionar novos folders na estrutura fica mais fácil do que usando a lista
a.add_child(Folder(id=6, title='F'))
root.add_child(Folder(id=7, title='G', children=[Folder(id=8, title='H')]))
print_tree(root)
Repare que assim fica mais simples adicionar novos folders na estrutura. Usando a lista, você teria que chamar build_tree
novamente (ou então fazer um build_tree_parcial
, que verifica quais folders precisariam ser atualizados), ou seja, é mais uma prova de que a lista com todos os folders não é a estrutura mais adequada. E usar a estrutura de dados correta é meio caminho andado para um código melhor.
A saída do código acima é:
_ROOT
A
C
E
B
D
_ROOT
A
C
E
F
B
D
G
H
Se ainda sim você quiser uma lista com todos os folders (sem se preocupar muito com a hierarquia), é possível obtê-la a partir do folder raiz:
# generator que obtém todos os folders a partir de um folder inicial
def get_all_folders(initial_folder):
yield initial_folder
for child in initial_folder.children:
yield from get_all_folders(child)
# cria uma lista com todos
todos = list(get_all_folders(root))
# se eu só quero percorrer todos, não preciso criar uma lista
for folder in get_all_folders(root):
# faz algo com o folder
Enfim, uma vez tendo a estrutura correta (cada folder contém uma lista dos filhos), é possível manipulá-la da maneira que quiser, e de forma bem mais simples do que se usasse uma lista com todos os folders.
Considerações finais
Só para constar, se fosse para continuar usando a lista, você teria que fazer algo do tipo:
def print_folders(folders, indent='', current_id=0):
current = next(filter(lambda f: f.id == current_id, folders))
print(f'{indent}{current.title}')
for child in filter(lambda f: f.parent_id == current.id, folders):
print_folders(folders, indent + ' ', child.id)
print_folders(folders)
A ideia é a mesma da função print_tree
: começo na raiz e depois vou buscando os filhos dela (e faço chamadas recursivas para pegar os netos, bisnetos, etc). Mas veja que, como os folders só tem a informação de quem é o pai, eu preciso percorrer a lista toda hora, buscando os elementos que tem determinado parent_id
. Isso é extremamente ineficiente, pois percorre a lista várias vezes (tendo uma lista de filhos, como feito anteriormente, pode até "gastar um pouco mais de espaço", mas o ganho em tempo acaba compensando, na minha opinião, pois assim eu não preciso percorrer todos os folders toda hora).
Mas e se você quisesse uma lista que, além de ter os folders, também tem a informação sobre o seu respectivo nível na hierarquia, então uma alternativa seria criar uma lista de tuplas (onde cada tupla tem o folder e seu nível):
def build_tree(folders, tree, level=0, current_id=0):
current = next(filter(lambda f: f.id == current_id, folders))
tree.append((current, level)) # folder e seu respectivo nível na árvore
for child in filter(lambda f: f.parent_id == current.id, folders):
build_tree(folders, tree, level + 1, child.id)
tree = []
build_tree(folders, tree)
for folder, level in tree:
print(f'{" " * level}{folder.title}')
Mas ainda sim tem o mesmo problema da ineficiência de percorrer a lista várias vezes. No fim, ainda prefiro as soluções anteriores (cada folder tem uma lista dos filhos), que não só são mais eficientes, como também são semanticamente mais corretas (já que a estrutura representa melhor como os dados são organizados de fato: como uma árvore/hierarquia).