Algorithm - Numbering for TOC (Table of Contents)

Question

I want to implement a VBA function to number Excel rows based upon the grouping depth of the row.

But I think a general algorithm for generating TOCs is more interesting.

The problem is:

Given a list of "indented" lines such as

One
 Two
  Three
   Four
 Five
Six

(the "indentation level" may be assumed to be known and part of the input data)

To generate the following output:

1.    One
1.1    Two
1.1.1   Three
1.1.1.1  Four
1.2    Five
2.    Six

Of course my code is up and running ... and also hidden under THWoS (The Heavy Weight of Shame)

Answer 1

Use a stack for the numbers. Loop through each row keeping track of the indentation level of the previous row as well (for the first row, imagine it's -1), and:

1. If the current indentation level is greater than the previous indentation level, push as many ones as the difference is onto the stack (the difference would usually be just one, but this works even if someone puts a level 3 heading under a level 1 heading, for instance)
2. If the current indentation level is equal to the previous indentation level, increment the top number on the stack
3. If the current indentation level is less than the previous indentation level, pop and discard as many numbers as the difference is and then increment the top number on the stack.

For each row, the current title number is the numbers on the stack concatenated together with a . to separate them.

No indentation is indentation level 0.

Answer 2

This algorithm assumes that indentation level never increases by more than 1 unit. If it does, then you must set all the "skipped" levels to 1.

#use a vector instead, if your language supports it
numbering = {0, 0, 0, 0, 0, 0, 0}

for line in lines:
    level = indentLevel(line) #starting from 0

    numbering[level] = numbering[level] + 1
    numbering[level + 1] = 0 #create it if it doesn't exist
    for n = 0 to level - 1
        print numbering[n], ".",
    print numbering[level], " ", line