Das deutsche Python-Forum

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},
]

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'}
        ]
    }
]

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)

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}]}]

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