tree.ts

tree.ts

import _ from 'lodash'

export interface Node {
  level: number
}

/**
 * Creates a tree based on an materialized ordered path structure
 * It's important the the `Nodes` are in the right order, otherwise it will fail.
 * @param tree
 */
export const createTreeFromFlatStructure = <T extends Node[]>(tree: T) => {
  const currentPath = []
  let currentLevel = 0
  let currentIndex = 0
  const resultingTree = []

  for (const item of tree) {
    const level = item.level

    if (level > currentLevel) {
      currentPath.push(currentIndex)
      // reset, as we start on a new level with 0
      currentIndex = 0
    }
    if (level < currentLevel) {
      // we go back to the level we came from
      // we have to loop as long as the level matches again the current level, otherwise we reference the wrong
      // nodes.
      // Eg. the following case:
      // 1.2.3.4.5.6
      // 1
      while (currentPath.length > level) {
        currentIndex = currentPath.pop() || 0
      }
    }
    // we are not interested on the root (as our tree base is already root)
    const [, ...childPath] = currentPath

    // in case we are on the root
    if (level === 1) {
      resultingTree.push({ ...item, children: [] })
      // otherwise we deeply mutate the tree
    } else {
      const pathInArray = childPath
        // because we count from 0, we have to map here
        .map((p) => p - 1)
        .join('.')
        .replace(/(\d+)/g, '[$1]')
        .replace(/\./g, '.children')
      if (!_.has(resultingTree, pathInArray + '.children')) {
        _.set(resultingTree, pathInArray + '.children', [])
      }
      _.get(resultingTree, pathInArray + '.children').push({
        ...item,
        children: [],
      })
    }
    currentLevel = level
    currentIndex++
  }
  return resultingTree
}