Make a python nested list for use in Django's unordered_list

Question

I've got a Django model with a self-referencing foreign key, so my model (as a class in its most basic form) looks like:

class MyObj(object):
    def __init__(self, id, ttl, pid):
        self.id = id
        self.name = ttl
        self.parentid = pid

So a sample of my data might look like:

nodes = []
nodes.append(MyObj(1,'a',0))
nodes.append(MyObj(2,'b',0))
nodes.append(MyObj(3,'c',1))
nodes.append(MyObj(4,'d',1))
nodes.append(MyObj(5,'e',3))
nodes.append(MyObj(6,'f',2))

I've got to a point where I can convert this into a nested dictionary:

{'a': {'c': {'e': {}}, 'd': {}}, 'b': {'f': {}}}

using Converting tree list to hierarchy dict as a guide, but I need it in a form that I can use for Django's unordered_list filter.

So my question is, how can I get from (either) a nested dictionary to a nested list/tuple or straight from the source data to a nested list? I can't seem to get a recursive function to nest the lists correctly (as in a list I can't reference "sub trees" by name)

eval(string_rep_of_dictionary.replace(':',',').replace('{','[').replace('}',']')) seems to just about get me there but that seems a horrible solution?

Sven Marnach · Accepted Answer · 2011-02-21T12:00:00.553

1

Try

lists = {}
for n in nodes:
    b = lists.setdefault(n.id, [])
    lists.setdefault(n.parentid, []).extend([n.name, b])
print lists[0]

or, using collections.defaultdict

lists = collections.defaultdict(list)
for n in nodes:
    lists[n.parentid] += [n.name, lists[n.id]]
print lists[0]

both of which will print

['a', ['c', ['e', []], 'd', []], 'b', ['f', []]]

Edit:To get rid of the empty lists, iterate through the nodes for a second time:

for n in nodes:
    if not lists[n.id]:
        lists[n.parentid].remove(lists[n.id])

edited Feb 21 '11 at 12:00

answered Feb 20 '11 at 19:39

Sven Marnach

574,206
118
941
841

That's excellent, I wasn't aware of setdefault. Now I just need to figure out how to get rid of the empty leaf nodes... It looks like unordered_list doesn't ignore empty nodes. – Rich Feb 21 '11 at 11:49

score 0 · Answer 2 · answered Feb 20 '11 at 20:06

def nested_dict_to_list(d):
    result = []
    for key, value in d.iteritems():
        try:
            value = nested_dict_to_list(value)
        except AttributeError:
            pass
        result += [key, value]
    return result


test = {'a': {'c': {'e': {}}, 'd': {}}, 'b': {'f': {}}}
desired_result = ['a', ['c', ['e', []], 'd', []], 'b', ['f', []]]

nested_dict_to_list(test) == desired_result
# True

Make a python nested list for use in Django's unordered_list

2 Answers2