Обход дерева со страничным свойством sortIndex

Question

Я строю древовидную структуру на основе списка, полученного из списка db.Model под названием Страницы.

Каждая запись на странице имеет свойство parentKey, которое является db.SelfReferenceProperty() и db.IntegerProperty(), называемое sortIndex.

Получаю список и вызываю метод для перемещения по списку и создаю nedled dict как мое дерево. Причина, по которой я извлекаю весь список, - это то, что я хочу пропустить несколько запросов.

pages = Pages.gql('ORDER BY sortIndex').fetch(1000) 
build_tree(pages) 

И build_tree:

def build_tree(nodes, *args): 
    # create empty tree to fill 
    tree = {} 
    build_tree_recursive(tree, None, nodes, *args) 

    return tree 

def build_tree_recursive(tree, parent, nodes, *args): 
    # find root children, first level nodes have no parentKey 
    if parent is None: 
     children = [n for n in nodes if n.parentKey == None] 
    # find children 
    else: 
     children = [n for n in nodes if n.parentKey is not None and n.parentKey.key() == parent] 

    # build a subtree for each child 
    for child in children: 
     # start new subtree 
     key = child.key() 
     # Use page entry key as unique dict key 
     tree[key] = { 'page' : child, 'children' : {}} 
     # call recursively to build a subtree for current node 
     build_tree_recursive(tree[key]['children'], key, nodes) 

Проблема заключается в том, что список прибудет-х переставить и не следует Det ORDER BY. Я думаю, это связано с тем, что каждая страница помещается в список, когда найден правильный родитель. Но даже первый уровень (страницы с parentKey == None) возвращается в неправильном порядке.

Я попытался установить префикс с использованием счетчика циклов на дереве [str (i) + '_' + str (key)], но все равно не вернулся в правильном порядке.

Итак, вопрос, как получить их в надлежащем порядке?

EDIT [Решено]:

Ниже

Answer 1

Чтобы сохранить порядок в списке пересылается как пары, чтобы build_tree я переехал в другой угол. Я использую список вместо и порядок остается прежним:

def build_tree(nodes, *args): 
    # create empty tree to fill 
    t = {} 
    # First group all pages w/ same parent 
    for node in nodes: 
     if node.parentKey is None: 
      key = 'root' 
     else: 
      key = node.parentKey.key() 

     if not t.has_key(key): 
      t[key] = [] 

     t[key].append({ 'page' : node, 'children' : []}) 

    pageTree = t['root'] 
    # Iterate over there 
    build_page_tree(pageTree, t) 

    return pageTree 

def build_page_tree(pageTree, nodes): 
    #Loop over selected list 
    for parent, node in nodes.iteritems(): 
     # We don't need to loop over first level node 
     if parent is not 'root': 
      # Loop over current level in page tree 
      for item in pageTree: 
       # Match keys 
       if item['page'].key() == parent: 
        # Save node as child 
        item['children'] = node 
        # Only need to loop over childs if they are present 
        build_page_tree(item['children'], nodes)