I've hit a brick wall in a project I'm messing around with. I've got an adjacency list in a database where I've got a series of nested categories.
It's in the format of Id,Category,Parent_Id and works quite well.
I'd like to display it as a table so that people can add and alter categories without too much confusion. This is where I'm failing. I can't for the life of me work out how to get it displaying correctly.
When I query the database, I end up with a series of nested tuples similar to this:
((1L, 'First', None), (2L, 'Second', None), (3L, 'Third', None), (4L, 'Fourth', 1L), (5L, 'Fifth', 4L), (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None))
The data gets changed a bit, so there's no guarantee of order. I assume I need some sort of recursive function to turn it into a table, but I just can't get my head around it. Just something like this would be nice:
First | Fourth | Fifth
Second
Third | Sixth
Eighth | Seventh
Can anyone give me some pointers on how to achieve this? It's almost impossible to get outside modules onto the box I'm working on and it's only running python 2.5, so any help would be greatly appreciated.
edit: Before posting I'd come up with the following code:
list = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L),
(6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None),
(2L, 'Second', None), (5L, 'Fifth', 4L))
levels = []
levels.append([_[0] for _ in list if _[2] is None])
for x in xrange(0,len(list[0])):
levels.append([])
for item in list:
levels[-1].append(item[0]) if item[2] in levels[-2] else None
if sum([len(_) for _ in levels]) == len(list): break
From that I get nested lists for each level:
>>> levels
[[1L, 3L, 8L, 2L], [4L, 6L, 7L], [5L]]
From here I get a little lost. I assume to turn this into a table, I need as many lists as there will be rows in the finished table. I can find the longest list in the nest of lists to give the amount of rows, it's working in two dimensions to fill the table out that's had me stumped.
The actual output is a non-thing. I can print the table in a way that suits me without much effort. It's the thinking to create the table that's hurting me. I know it's possible to do with SQL queries such as in Suggest SQL Query to retrieve all leaf nodes from Adjacency List Model, I was just hoping there was a way to do it in Python so I could learn more about handling this sort of data set.
Not quite sure about the format of the expected output however here is an approach:
data = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L),
(6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), (2L, 'Second', None), (5L, 'Fifth', 4L))
def get_tuple_by_id(tuple_id):
for item in data:
if item[0] == tuple_id:
return item
def arrange_data(items):
new_list = ()
for an_item in items:
parent_id = an_item[2]
if parent_id:
parent = get_tuple_by_id(parent_id)
new_tuple = an_item + (parent[1],)
new_list += (new_tuple,)
else:
new_list += (an_item,)
return sorted(new_list, key=lambda x: x[0])
def render(items):
print '{name:15}{parent}'.format(name='name', parent='parent')
print '{name:15}{parent}'.format(name='--------', parent='-------')
for item in items:
print '{name:15}{parent}'.format(name=item[1], parent=item[3] if item[2] else '')
ad = arrange_data(data)
render(ad)
Output:
name parent
-------- -------
First
Second
Third
Fourth First
Fifth Fourth
Sixth Third
Seventh Eighth
Eighth
Install table renderer: pip install prettytable
from prettytable import PrettyTable
data = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L),
(6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), (2L, 'Second', None), (5L, 'Fifth', 4L))
def get_tuple_by_id(tuple_id):
for item in data:
if item[0] == tuple_id:
return item
def arrange_data(items):
new_list = ()
for an_item in items:
parent_id = an_item[2]
if parent_id:
parent = get_tuple_by_id(parent_id)
new_tuple = an_item + (parent[1],)
new_list += (new_tuple,)
else:
new_list += (an_item,)
return sorted(new_list, key=lambda x: x[0])
ad = arrange_data(data)
t = PrettyTable(['Category', 'Level'])
for item in ad:
t.add_row([item[1], 1 if item[2] else 0])
print t
Result:
+----------+-------+
| Category | Level |
+----------+-------+
| First | 0 |
| Second | 0 |
| Third | 0 |
| Fourth | 1 |
| Fifth | 1 |
| Sixth | 1 |
| Seventh | 1 |
| Eighth | 0 |
+----------+-------+
Note: If you data in be nested multiple level then some modification can also achieve that. At the moment it's only considering 0 or 1 level nesting only.
from prettytable import PrettyTable
data = (
(1L, 'First', None),
(2L, 'Second', None),
(3L, 'Third', None),
(4L, 'Fourth', 1L),
(5L, 'Fifth', 4L),
(6L, 'Sixth', 3L),
(7L, 'Seventh', 8L),
(8L, 'Eighth', None),
(9L, 'Ninth', 5L),
(10L, 'Tenth', 9L),
(11L, 'Eleventh', 10L),
(12L, 'Twelfth', 11L))
def get_tuple_by_id(tuple_id, level=1):
for item in data:
if item[0] == tuple_id:
parent_id = item[2]
if parent_id:
level += 1
return get_tuple_by_id(parent_id, level)
else:
return (item, level)
def arrange_data(items):
new_list = ()
for an_item in items:
parent_id = an_item[2]
if parent_id:
parent, level = get_tuple_by_id(parent_id)
print an_item, level
new_tuple = an_item + (level,)
new_list += (new_tuple,)
else:
an_item += (0,)
new_list += (an_item,)
return sorted(new_list, key=lambda x: x[0])
ad = arrange_data(data)
t = PrettyTable(['Category', 'Level'])
for item in ad:
t.add_row([item[1], item[3]])
print t
Output:
+----------+-------+
| Category | Level |
+----------+-------+
| First | 0 |
| Second | 0 |
| Third | 0 |
| Fourth | 1 |
| Fifth | 2 |
| Sixth | 1 |
| Seventh | 1 |
| Eighth | 0 |
| Ninth | 3 |
| Tenth | 4 |
| Eleventh | 5 |
| Twelfth | 6 |
+----------+-------+
More about recursive function in case you are interested: https://en.wikipedia.org/wiki/Recursion_(computer_science)