tree erstellen...

[jens]

Also ich breche mir gerade einen ab

Ich schaffe es nicht eine Baum zu erstellen. Hab folgende Daten:

Code: Alles auswählen

data = [
    {'shortcut': 'Index',               'id': 1L,   'parent': 0L},
    {'shortcut': 'Elementary',          'id': 13L,  'parent': 10L},
    {'shortcut': 'OldDefault',          'id': 12L,  'parent': 10L},
    {'shortcut': 'SourceCode',          'id': 7L,   'parent': 2L},
    {'shortcut': 'RSS',                 'id': 6L,   'parent': 2L},
    {'shortcut': 'SmallWhite',          'id': 14L,  'parent': 10L},
    {'shortcut': 'SmallDark',           'id': 11L,  'parent': 10L},
    {'shortcut': 'Designs',             'id': 10L,  'parent': 0L},
    {'shortcut': 'TinyTextileExample',  'id': 3L,   'parent': 2L},
    {'shortcut': 'ExamplePages',        'id': 2L,   'parent': 0L},
    {'shortcut': 'Contact',             'id': 5L,   'parent': 2L},
    {'shortcut': 'SiteMap',             'id': 4L,   'parent': 2L},
    {'shortcut': '3.Ebene',             'id': 15L,  'parent': 3L},
]

Das soll daraus werden:

Code: Alles auswählen

sitemap = [
    {'parent': 0L, 'id': 1L, 'shortcut': 'Index'},
    {
        'parent': 0L, 'id': 10L, 'shortcut': 'Designs',
        'subitems': [
            {'parent': 10L, 'id': 13L, 'shortcut': 'Elementary'},
            {'parent': 10L, 'id': 12L, 'shortcut': 'OldDefault'},
            {'parent': 10L, 'id': 14L, 'shortcut': 'SmallWhite'},
            {'parent': 10L, 'id': 11L, 'shortcut': 'SmallDark'}
        ]
    },
    {
        'parent': 0L, 'id': 2L, 'shortcut': 'ExamplePages',
        'subitems': [
            {'parent': 2L, 'id': 7L, 'shortcut': 'SourceCode'},
            {'parent': 2L, 'id': 6L, 'shortcut': 'RSS'},
            {
                'parent': 2L, 'id': 3L, 'shortcut': 'TinyTextileExample',
                'subitems': [
                    {'parent': 3L, 'id': 15L, 'shortcut': '3.Ebene'},
                ]
            },
            {'parent': 2L, 'id': 5L, 'shortcut': 'Contact'},
            {'parent': 2L, 'id': 4L, 'shortcut': 'SiteMap'}
        ]
    }
]

Schön wäre auch, wenn ein "deep/Level" info eingefügt wird.

Jemand eine Idee, wie man das macht? Ist IMHO eine Allgemeine Fragestellung. Geht wohl irgendwie rekursiv.

Was ähnliches hatten wir hier: http://www.python-forum.de/topic-7501.html Hilft mir aber gerade nicht so weiter...

EDIT: Ha, ich hab was: [EDIT2: Alte Version gelöscht]

[jens]

So, eine neue Version. Nun hab ich auch meine Level Angabe drin:

Code: Alles auswählen

from pprint import pprint

data = [
    {'id': 1,   'parent': 0,  'name': '1. Entry'},
    {'id': 2,   'parent': 1,  'name': '1.1. first subitem'},
    {'id': 3,   'parent': 1,  'name': '1.2. second subitem'},
    {'id': 4,   'parent': 2,  'name': '1.2.1 first sub-subitem'},
    {'id': 5,   'parent': 2,  'name': '1.2.2 second sub-subitem'},
    {'id': 6,   'parent': 0,  'name': '2. Entry'},
    {'id': 7,   'parent': 6,  'name': '2.1. first subitem'},
]


class TreeGenerator(object):
    def __init__(self, start_level=1):
        self.start_level = start_level

    def insert_level(self, data, level):
        """
        insert in every row a 'level'-key
        """
        for row in data:
            row["level"] = level
        return data

    def make_dict(self, data, key_name):
        """
        generate a dict based on key_name
        """
        result = {}
        for row in data:
            key = row[key_name]
            if not key in result:
                result[key] = [row]
            else:
                result[key].append(row)

        return result

    def generate(self, data):
        """
        returns the tree data
        """
        parent_dict = self.make_dict(data, "parent")

        root_id = min(parent_dict.keys())
        print "root id:", root_id

        root = parent_dict.pop(root_id)
        root = self.insert_level(root, self.start_level)

        tree = self.gen(root, parent_dict, level=self.start_level+1)
        return tree


    def gen(self, block, data, level):
        """
        generate recurive the tree data
        """
        for row in block:
            id = row["id"]
            if id in data:
                subitems = data.pop(id)
                subitems = self.insert_level(subitems, level)
                row["subitems"] = self.gen(subitems, data, level+1)

        return block


tree = TreeGenerator().generate(data)
print "="*80
pprint(tree)

Wie kann man es besser machen???

Was ich eigentlich auch noch brauche: slicing!
Also: gib mir alle Eintrage ab dem Level-X oder bis zum Level-Y...

Ausgabe ist dann:

Code: Alles auswählen

[{'id': 1,
  'level': 1,
  'name': '1. Entry',
  'parent': 0,
  'subitems': [{'id': 2,
                'level': 2,
                'name': '1.1. first subitem',
                'parent': 1,
                'subitems': [{'id': 4,
                              'level': 3,
                              'name': '1.2.1 first sub-subitem',
                              'parent': 2},
                             {'id': 5,
                              'level': 3,
                              'name': '1.2.2 second sub-subitem',
                              'parent': 2}]},
               {'id': 3,
                'level': 2,
                'name': '1.2. second subitem',
                'parent': 1}]},
 {'id': 6,
  'level': 1,
  'name': '2. Entry',
  'parent': 0,
  'subitems': [{'id': 7,
                'level': 2,
                'name': '2.1. first subitem',
                'parent': 6}]}]

[rayo]

Hi

Also einen Baum von einem gewissen Level bekommst du mit Levelorder-Traversierung, z.B. so:

Code: Alles auswählen

def get_sub_tree(tree ,level):
    result = []
    q = Queue()
    for x in tree:
        q.put(x)

    while not q.empty():
        item = q.get()
        if item['level'] == level:
            result.append(item)
        else:
            if item.has_key('subitems'):
                for x in item['subitems']:
                    q.put(x)
    return result

Und bis Level x würde ich den Baum so lassen und einfach bei der bearbeitung beim Level x abbrechen.

Gruss

[keboo]

Hallo Leute!

Ich bin im moment verzeweifelt dabei eine Produktbaum aus einer postgres DB rauszuholen.

Ich habe dabei eine Junction Table in welcher immer zu einer ID die darunterliegende ID angegeben ist.

Wie kann man den Code von Jens anpassen, damit zu einer ID nicht die ParentID sondern, die ChildrenID angeben werden kann in data?

Danke für eure Hilfe,

Johannes