sort_tree.py

#!/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