How to fix this algorithm to for create nested sections in an AST

Question

I am struggling to create an algorithm, which takes an array of sibling elements (abstract representations of DOM nodes) and returns that array enhanced with nesting. The nesting rule is quite simple: Every heading starts a new section, which spans until the next heading of the same level (or end of the list). Every section can have more nested sections in it, with the same rule.

Background: I am trying to convert AST from my CMS to a structure presented in Chris Coyers post about the interactive sticky table of contents. Currently, i am using only headings to create a similar effect, (e.g. scotch.io), but the effect is not so slick.

I was able to create some nesting, but my brain doesn't enjoy recursive algorithm like this much, and I've got stuck with at least one bug – one part of nesting is padded with a needless array (note the first "heading3" and so on).

What I've got so far:

let list = ["heading1", "1", "1", "heading2", "1-1", "1-1", "heading3", "1-1-1", "heading3", "1-1-2", "1-1-2", "heading2", "1-2", "1-2", "heading1", "heading2", "2-1", "heading2", "2-2", "heading1", "3", "heading1", "4", "4", "4"]

let findFirstHeading = (list, level) => list.findIndex(el => new RegExp(`heading${level}`).test(el))

let splitIntoSections = (list, level) => {
  let startIndex = findFirstHeading(list, level)
  // Note: while this might seem overcomplicated, it is due to prevent bug, when findIndex returns -1, then adding startIndex + 1 will give a faulty value.
  let endIndex =
    findFirstHeading(list.slice(startIndex + 1), level) === -1 ?
    -1 :
    findFirstHeading(list.slice(startIndex + 1), level) + startIndex + 1
        
  let precedingList = list.slice(0, startIndex)
  let restOfList = endIndex > -1 ? list.slice(endIndex) : null

  return restOfList ? [...precedingList,
    splitIntoSections(list.slice(startIndex, endIndex), level + 1),
    ...splitIntoSections(restOfList, level)
  ] : [list]
}

console.log(JSON.stringify(splitIntoSections(list, 1), null, 2))

Expected result:

[
  [
    "heading1",
    "1",
    "1",
    [
      "heading2",
      "1-1",
      "1-1",
      [
        "heading3",
        "1-1-1"
      ],
      [
        "heading3",
        "1-1-2",
        "1-1-2"
      ]
    ],
    [
      "heading2",
      "1-2",
      "1-2"
    ]
  ],
  [
    "heading1",
    [
      "heading2",
      "2-1"
    ],
    [
      "heading2",
      "2-2"
    ]
  ],
  [
    "heading1",
    "3"
  ],
  [
    "heading1",
    "4",
    "4",
    "4"
  ]
]

Any help would be greatly appreciated. Thank you.

Answer 1

Generally when writing a recursive algorithm, I avoid copies or sub-copies of the source array, and instead opt for an index to track the current position in the source array, primarily to avoid the performance hit of array copying. And typically I find that it is a cleaner function interface to have the main function require the minimal parameters, and embed within this main function the actual recursive function along with the initialization of any variables required by the recursive function.

I've embedded a couple of comments in the code below to assist in understanding the recursion logic.

function nest( array ) {
  
  function recurse( currentLevel ) {
    let result = [];
    while ( index < array.length ) {
      let value = array[ index ];
      if ( value.slice( 0, 7 ) == 'heading' ) {
        let newLevel = +value.slice( 7 );
        if ( currentLevel < newLevel ) {
          // If the new heading is deeper than the current heading, then push
          // the heading value as a new child array to the result, and recursively
          // continue adding to this new child array.
          index++;    // Advance past the 'headingX' as it's added to the child array.
          result.push( [ value, ...recurse( newLevel ) ] );
        } else {
          // Otherwise, if the new heading is less than or equal, then close out
          // the current array, adding it to parent array.  And don't advance past
          // this 'headingX' as the parent recurse function will pick it up.
          return result;
        }
      } else {
        // Otherwise, if not 'headingX' simply add the value to the result.
        result.push( value );
        index++;
      }
    }
    return result;
  }
  
  let index = 0;
  return recurse( 0 );
}
  
  
let list = ["heading1", "1", "1", "heading2", "1-1", "1-1", "heading3", "1-1-1", "heading3", "1-1-2", "1-1-2", "heading2", "1-2", "1-2", "heading1", "heading2", "2-1", "heading2", "2-2", "heading1", "3", "heading1", "4", "4", "4"];

console.log( nest( list ) );