How to create a nested list of parent/child objects using a function?
I'm new to Python and Django and I've encountered a problem I can't solve on my own for quite a long time.
I have a database that consists of a number objects and each object has one parent (except the first, the 'root' object) and no / one / several children. I need to create a fuction that takes some object and returns this object and recursively its descendants like this:
arr = ['States',
['Kansas', ['Lawrence', 'Topeka', ['Some Topeka Street', ['Some House on Some Topeka Street']]],
'Illinois', ['Chicago', 'Springfield']]]
I want to get this kind of data structure and use it on Django's unordered list filter.
As far as I know about algorithms I should make up a function that somehow should work like this:
def make_nested_list(item):
if not item.children: # basic case
# do something
else:
for child in item.children: # recursive case
# do something
make_nested_list(child) # function calls itself
# maybe do something here
# and finally return self-nested list
return result
Everything I try turns out to be a mess. How can I do that?
Assuming that your item
objects have name
attributes, here is what you could do:
def list_nodes(siblings):
for node in siblings:
yield node.name
if node.children:
yield list(list_nodes(node.children))
So the argument to this function is a list of nodes. If you just have one root object, then first put it in a list, and pass that as argument:
result = list(list_nodes([root]))
Here is the test I performed, which includes the creation of mock data:
from collections import namedtuple
Node = namedtuple("Node", "name, children")
root = Node("States", [
Node("Kansas", [
Node("Lawrence", []),
Node("Topeka", [])
]),
Node("Illinois", [])
])
print(root)
def list_nodes(siblings):
for node in siblings:
yield node.name
if node.children:
yield list(list_nodes(node.children))
result = list(list_nodes([root]))
print(result)
This outputs (with some formatting applied):
Node(name='States', children=[
Node(name='Kansas', children=[
Node(name='Lawrence', children=[]),
Node(name='Topeka', children=[])
]),
Node(name='Illinois', children=[])
])
['States', ['Kansas', ['Lawrence', 'Topeka'], 'Illinois']]