Comment construire un arbre à partir d'une liste à plat avec une indentation en JavaScript ?

Question

Je lutte toujours lorsque je suis confronté à ce problème, et cela demande un sérieux travail. Je suis actuellement en train d'essayer de résoudre ce problème et cela va probablement me prendre quelques jours. Je voulais voir si vous aviez un système ou une manière simple de résoudre ce problème.

En gros, imaginez que vous ayez une liste plate de nœuds DOM avec une indentation de padding left par étapes de 15px. Visuellement, cela forme un arbre comme un navigateur de fichiers. Mais structurellement dans le DOM, c'est implémenté comme une liste plate. Comment pouvez-vous alors itérer à travers la liste et construire un arbre?

A
AA
AB
ABA
ABB
ABBA
ABBB
ABBC
ABC
AC
B
C
...

Cela devrait ensuite devenir un arbre JSON comme ceci:

[ 
  {
    title: 'A',
    children: [
      {
        title: 'AA',
        children: []
      },
      {
        title: 'AB',
        children: [
          {
            title: 'ABA',
            children: []
          },
          {
            title: 'ABB',
            children: [
              {
                title: 'ABBA',
                children: []
              },
              {
                title: 'ABBB',
                children: []
              },
              {
                title: 'ABBC',
                children: []
              }
            ]
          },
          {
            title: 'ABC',
            children: []
          }
        ]
      },
      {
        title: 'AC'
      }
    ]
  },
  {
    title: 'B',
    children: []
  },
  {
    title: 'C',
    children: []
  }
]

Comment faire cela? Je suis perdu:

let tree = []
let path = [0]

let items = list('div')

items.forEach(item => {
  let left = parseInt(item.style[`padding-left`] || 0) % 15
  let set = tree
  let p = path.concat()
  while (left) {
    let x = p.shift()
    set[x] = set[x] || { children: [] }
    set = set[x].children
    left--
  }
})

function list(s) {
  return Array.prototype.slice.call(document.querySelectorAll(s))
}

Answer 1

C'est une pile car c'est séquentiel. Quelque chose comme ça?

Nous supposons que la structure des dossiers est entièrement "développée", donc le parent de chaque dossier (sauf le plus bas, pour lequel le parent est la racine) doit avoir été examiné avant celui actuel. Le parent doit également avoir une assignation de padding-left "inférieure".

ptrs est une pile à laquelle nous ajoutons une référence vers le prochain dossier examiné. Le dossier en haut (à la fin) de la pile est le dernier dossier que nous avons examiné. Si ces dossiers en haut de la pile ont une assignation de "padding-left" supérieure ou égale, ils ne pourraient pas être le parent du dossier actuel; et nous ne pouvons pas avoir plus d'enfants de ceux-ci après le dossier actuel, donc nous les supprimons (dépilons) jusqu'à trouver le dernier dossier placé qui avait un "padding-left" inférieur.

function getData(s){
  const left = +s.match(/\d+/)[0];
  const title = s.match(/[A-Z]+/)[0];
  return [left, title];
}

function f(divs){
  const tree = {
    title: 'root',
    children: []
  };
  const ptrs = [[0, tree]]; // pile
  for (let str of divs){
    const [left, title] = getData(str);
    while (ptrs.length && ptrs[ptrs.length-1][0] >= left)
      ptrs.pop();
    parent = ptrs.length ? ptrs[ptrs.length-1][1] : tree;
    const obj = {title: title, children: []};
    parent.children.push(obj);
    ptrs.push([left, obj]);
  }
  return tree;
}

var divs = [
  "A",
  "AA",
  "AB",
  "ABA",
  "ABB",
  "ABBA",
  "ABBB",
  "ABBC",
  "ABC",
  "AC",
  "B",
  "C"
]

console.log(f(divs));

Answer 2

Exercice intéressant. Voici une autre approche qui est un peu plus verbeuse que la solution précédente mais qui fonctionne également avec des nœuds DOM plutôt qu'avec du HTML en chaîne

const buildTree = (sélecteur) => {
    const elems = [...document.querySelectorAll(sélecteur)]
              .map((el,i)=>({el, title: el.textContent, idx:i, inset: parseInt(el.style.paddingLeft)}));

    const getChildren = ({inset:pInset, idx:start}) => {
      const nextParentIdx = elems.findIndex(({inset, idx}, i)=> inset <= pInset && i >start);
      const desc = elems.slice(start, nextParentIdx+1 )
                  .filter(({inset})=>inset-pInset === 15);
      return desc.map(getItem); 
    }

    const getItem = (o)=>{
      return {title: o.title, children: getChildren(o)}
    }

    return elems.filter(({inset})=>!inset).map(getItem)
}

console.log(JSON.stringify(buildTree('div'),null, 4))

.as-console-wrapper {   max-height: 100%!important;top:0;}

A
AA
AB
ABA
ABB
ABBA
ABBB
ABBC
ABC
AC
B
C