-
Egmont Schreiter authoredEgmont Schreiter authored
sort_tree.py 3.45 KiB
#!/bin/python3
def sort_tree(tree):
"""Funktion sortiert einen Baum, dass zuerst die Wurzel und Zweige immer erst später erscheinen
- ändert die Reihenfolge der Einträge
- Unbekannte parent_ids werden auf None gesetzt
- für Listen im Muster [uid, name, parent_uid]
Usage:
tree = [
["105", "zweig", "100"], # muss später eingefügt werden, parent_uid ist noch nicht bekannt
["100", "wurzel 1", None],
["102", "wurzel 2", None],
["103", "zweig", "100"],
["104", "zweig", "101"], # parent_uid wird auf None gesetzt, da sie nicht enthalten ist
]
print(sort_tree(tree))
"""
unsorted_tree = list()
ids = list() # alle IDs zum nachsehen eintragen
ids_without_root = list()
elements_without_root = list()
#print(f"Vorher {len(tree)}, unsorted_tree={len(unsorted_tree)}, elements_without_root={len(elements_without_root)}, Summe={len(unsorted_tree)+len(elements_without_root)}")
for i, element in enumerate(tree):
if element[2] == None: # kein parent --> kann übernommen werden
unsorted_tree.append(element)
ids.append(element[0])
continue
parent_id = element[2]
try:
ids.index(parent_id) # gefunden?
unsorted_tree.append(element)
ids.append(element[0])
continue
except:
pass
elements_without_root.append(element)
ids_without_root.append(element[0])
#print(f"Vorher {len(tree)}, unsorted_tree={len(unsorted_tree)}, elements_without_root={len(elements_without_root)}, Summe={len(unsorted_tree)+len(elements_without_root)}")
# in elements_without_root alle parent IDS auf None setzen die gar nicht existieren!
new_elements_without_root = list()
for element in elements_without_root:
try:
parent_id = element[2]
ids.index(parent_id) # todo entweder sie ist i n ids_without_root ODER ids!!! nicht nur in ids_without_root
new_elements_without_root.append(element)
continue
except:
pass
try:
parent_id = element[2]
ids_without_root.index(parent_id) # todo entweder sie ist i n ids_without_root ODER ids!!! nicht nur in ids_without_root
new_elements_without_root.append(element)
continue
except:
new_elements_without_root.append([element[0], element[1], None])
#print(f"Vorher {len(tree)}, unsorted_tree={len(unsorted_tree)}, elements_without_root={len(elements_without_root)}, Summe={len(unsorted_tree)+len(elements_without_root)}")
# jetzt gibt es zwei Listen, die eine hat schon alle Elemente in der Reihenfolge, die zweite hat die Elemente die zunächst keinen Vorgänger hatten.
# jetzt hängen wir beide Listen hintereinander
for element in new_elements_without_root:
unsorted_tree.append(element)
#print(f"Vorher {len(tree)}, unsorted_tree={len(unsorted_tree)}, elements_without_root={len(elements_without_root)}, Summe={len(unsorted_tree)+len(elements_without_root)}")
# wenn es noch was zum anhängen gab, noch mal sortieren (rekursiv)
#print(f"Anzahl vom Rest = {len(new_elements_without_root)}")
#print(new_elements_without_root)
if len(new_elements_without_root) > 0:
unsorted_tree = sort_tree(unsorted_tree)
else:
# wenn die letzte Liste leer war,
return unsorted_tree # jetzt sortiert
# muss dass im obigen else stehen
return unsorted_tree