I'm building a tree structure based on a list retrieved from a db.Model
called Pages.
Each Page entry has a parentKey property that's a db.SelfReferenceProperty()
and a db.IntegerProperty()
called sortIndex.
I fetch the list and call a method to travers over the list and make a nestled dict as my tree. The reason I fetch the entire list is that I want to skip multiple queries.
pages = Pages.gql('ORDER BY sortIndex').fetch(1000)
build_tree(pages)
And the 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)
The problem is that the list get's rearranged and don't follow det ORDER BY. I think this is due to that each Page is put in the list when a proper parent is found. But even the first level (Pages that has parentKey == None
) get's returned in the wrong order.
I've tried setting a prefix using a loop counter on tree[str(i) + '_' + str(key)] but still didn't return in a proper order.
So the question how to get them in an proper order?
EDIT [Solved]:
To preserve the order of the list sent as a param to build_tree I moved to a different angle. I use list instead and the order stays the same:
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)