Generate a nested list from flatten data in Python

Question

To generate a Table of Content, I have these data available in a Python list:

data = [
    {title: 'Section 1', level: 1, page_number: 1},
    {title: 'Section 1.1', level: 2, page_number: 2},
    {title: 'Section 1.2', level: 2, page_number: 3},
    {title: 'Section 2', level: 1, page_number: 4},
    {title: 'Section 2.1', level: 2, page_number: 5},
    {title: 'Section 3', level: 1, page_number: 6},
]

From this, I'd like to obtain this kind of nested structure, much more compatible with the use of a template engine:

toc = [
    {title: 'Section 1', page_number: 1, sub: [
        {title: 'Section 1.1', page_number: 2, sub: []},
        {title: 'Section 1.2', page_number: 3, sub: []},
    ]},
    {title: 'Section 2', page_number: 4, sub: [
        {title: 'Section 2.1', page_number: 5, sub: []},    
    ]},
    {title: 'Section 3', page_number: 6, sub: []},
]

Hints on how to achieve this? I tried with a recursive function but it's getting much tricky for my limited brain.

Any help much appreciated.

EDIT: Added fact that a section entry can have eventually no child. Sorry for the miss.

No need for recursion, a loop and a stack like list structure would work just as well. — Ofir
– Ofir, Commented Jun 28, 2010 at 8:38

unbeli · Accepted Answer · 2010-06-28 08:45:25Z

4

Assuming chapters come in order, meaning child chapter is always after the parent, and there are no missing parent (skipped levels):

import pprint

data = [
    {'title': 'Section 1', 'level': 1, 'page_number': 1},
    {'title': 'Section 1.1', 'level': 2, 'page_number': 2},
    {'title': 'Section 1.2', 'level': 2, 'page_number': 3},
    {'title': 'Section 2', 'level': 1, 'page_number': 4},
    {'title': 'Section 2.1', 'level': 2, 'page_number': 42},
    {'title': 'Section 2.1.1', 'level': 3, 'page_number': 42},
    {'title': 'Section 3', 'level': 1, 'page_number': 42},
]

toc = []
stack = [toc]
for d in data:
    d['sub'] = []   
    while d['level'] < len(stack):
        stack.pop()
    while d['level']  > len(stack):
        stack.append(stack[-1][-1]['sub'])
    stack[-1].append(d)


pprint.pprint(toc)

Result:

[{'level': 1,
  'page_number': 1,
  'sub': [{'level': 2, 'page_number': 2, 'sub': [], 'title': 'Section 1.1'},
          {'level': 2, 'page_number': 3, 'sub': [], 'title': 'Section 1.2'}],
  'title': 'Section 1'},
 {'level': 1,
  'page_number': 4,
  'sub': [{'level': 2,
           'page_number': 42,
           'sub': [{'level': 3,
                    'page_number': 42,
                    'sub': [],
                    'title': 'Section 2.1.1'}],
           'title': 'Section 2.1'}],
  'title': 'Section 2'},
 {'level': 1, 'page_number': 42, 'sub': [], 'title': 'Section 3'}]

EDIT: changed it to have empty 'sub' items where there are no children. See the other variant in edit history.

edited Jun 28, 2010 at 8:45

answered Jun 28, 2010 at 8:36

unbeli

30.4k5 gold badges58 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

NiKo Over a year ago

Ah, I should have specified in the statement that sections can have no child as well... but great stuff here, food for thought for sure

NiKo Over a year ago

Hey, you're fast. Okay so it works as expected now, many thanks :)

unbeli Over a year ago

@NiKo the difference is not that a section can have no children (that was clear), but rather if you want to have an empty 'sub' entry in that case. My first code didn't put empty 'sub's, this one does.

Duncan · Accepted Answer · 2010-06-28 08:47:38Z

2

Does this do what you want?

TITLE, LEVEL, PAGE_NUMBER, SUB = 'title', 'level', 'page_number', 'sub'
data = [
    {TITLE: 'Section 1', LEVEL: 1, PAGE_NUMBER: 1},
    {TITLE: 'Section 1.1', LEVEL: 2, PAGE_NUMBER: 2},
    {TITLE: 'Section 1.1.1', LEVEL: 3, PAGE_NUMBER: 2},
    {TITLE: 'Section 1.2', LEVEL: 2, PAGE_NUMBER: 3},
    {TITLE: 'Section 2', LEVEL: 1, PAGE_NUMBER: 4},
    {TITLE: 'Section 2.1', LEVEL: 2, PAGE_NUMBER: 5},
]

levels = [ { SUB: [] } ]
for section in data:
    section = dict(section)
    current = section[LEVEL]
    section[SUB] = []
    levels[current-1][SUB].append(section)
    del levels[current:]
    levels.append(section)

toc = levels[0][SUB]
from pprint import pprint
pprint(toc)

answered Jun 28, 2010 at 8:47

Duncan

96.4k15 gold badges129 silver badges160 bronze badges

1 Comment

Duncan Over a year ago

It's still a stack, just looked at slightly differently. I think the main difference is that you only save the sub list in each level where I saved the whole section. Whether that matters might be an interesting question.

tobiw · Accepted Answer · 2010-06-28 08:45:55Z

0

You could walk through each entry in your list and build a new list from there. Whenever there is a "Section x.y", you'll add it under sub.

newData = []
curParent = None
for d in data:
  # child
  if d['title'].find('.') > 0:
    assert curParent # Make sure we have a valid parent dictionary
    curParent['sub'].append({'title': d['title'], 'page_number': d['page_number'])
  # parent
  else:
    curParent = {'title': d['title'], 'page_number': d['page_number'], 'sub': []}
    newData.append(curParent)

That should work for 2 or 3 levels, if you need many more than a different approach might be better. Also, the find('.') might not work with other titles, but either use the level field (which seems redundant in your example) or regular expressions.

answered Jun 28, 2010 at 8:45

tobiw

4513 silver badges8 bronze badges

2 Comments

NiKo Over a year ago

Yes, I can have many nested levels. Plus I don't really want to rely on the presence of a dot in the section title ;)

tobiw Over a year ago

Downvoting every answer that doesn't fit perfectly isn't very nice. It's not like I deliberately wrote something wrong, it was just another approach than the other ones.

Collectives™ on Stack Overflow

Generate a nested list from flatten data in Python

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related