Generate a nested list from flatten data in Python

Question

Hi,

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.

Answer 1

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.

Answer 2

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.

Answer 3

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)