Creating a specific tree structure from materialized path

Question

I have "Entities" and "Entity Templates". The top level entity is tied to an Entity Template which is the "templateId1". From there an entity is tied to another entity in a path by using its id. I'm trying to end up with the following data structure in an efficient way:

const entities = [
  {
    id: 'xi32',
    name: 'Some name',
    path: ',templateId1,'
  },
  {
    id: 'x382',
    name: 'Some name 2',
    path: ',templateId1,xi32,'
  },
  {
    id: '2oxwo',
    name: 'Some name 3',
    path: ',templateId1,xi32,x382,'
  },
  {
    id: '2',
    name: '2',
    path: ',templateId1,'
  },
  {
    id: '2-2',
    name: '2-2',
    path: ',templateId1,2,'
  },
  {
    id: '3-3',
    name: '3-3',
    path: ',templateId1,3,'
  },
  {
    id: '3-3-3',
    name: '3-3-3',
    path: ',templateId1,3,3-3,'
  },
  {
    id: '3-3-3-3',
    name: '3-3-3-3',
    path: ',templateId1,3,3-3,3-3-3,'
  },
  {
    id: '3',
    name: '3',
    path: ',templateId1,'
  }
];

const desiredResult = [
      {
        id: 'xi32',
        name: 'Some name',
        path: ',templateId1,',
        children: [
          {
            id: 'x382',
            name: 'Some name 2',
            path: ',templateId1,xi32,',
            children: [
              {
                id: '2oxwo',
                name: 'Some name 3',
                path: ',templateId1,xi32,x382,',
                children: null
              }
            ]
          }
        ]
      },
      {
        id: '2',
        name: '2',
        path: ',templateId1,',
        children: [
          {
            id: '2-2',
            name: '2-2',
            path: ',templateId1,2,',
            children: null
          }
        ]
      },
      {
        id: '3',
        name: '3',
        path: ',templateId1,',
        children: [
          {
            id: '3-3',
            name: '3-3',
            path: ',templateId1,3,',
            children: [
              {
                id: '3-3-3',
                name: '3-3-3',
                path: ',templateId1,3,3-3,',
                children: [
                  {
                    id: '3-3-3-3',
                    name: '3-3-3-3',
                    path: ',templateId1,3,3-3,3-3-3,',
                    children: null
                  }
                ]
              }
            ]
          }
        ]
      }
    ];

Initial inspiration for the structure came from the MongoDB documentation:

https://docs.mongodb.com/manual/tutorial/model-tree-structures-with-materialized-paths/

I had a slightly different use case with the "Entity Template" being the top level parent, but within the "Entities" the use case is the same. Any insight is much appreciated.

Answer 1

I have done this... I have added a sort to prevent any key disorder.

const data = 
      [ { id: '1',     name: '1',     path: ',templateId1,'      } 
      , { id: '2',     name: '2',     path: ',templateId1,'      } 
      , { id: '2-1',   name: '2-1',   path: ',templateId1,2,'    } 
      , { id: '1-1',   name: '1-1',   path: ',templateId1,1,'    } 
      , { id: '1-1-1', name: '1-1-1', path: ',templateId1,1,1-1,'} 
      ]
let result  = []
  , parents = [ {children: result} ]
  ;
for (let elData of data.sort((a,b)=>a.id.localeCompare(b.id)))
  {
  let newEl = { ...elData, children: null }
    , level = (elData.id.match(/-/g)||'').length // count number of '-' 
    ;
  if (parents[level].children===null)
    { parents[level].children = [] }
  parents[level].children.push( newEl ) 
  parents[++level] = newEl
  }
  
console.log(JSON.stringify(result,0,2 )  )  // for testing

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

Answer 2

Finally I managed to code this, with a lot of debugging because there are a lot of traps.

the idea is to make the json in several passes, counting each time the number of remaining elements.

if this number does not decrease from one pass to another, then the pgm sends an error and stops.

for each element to add we calculate the supposed parent getParentKey() which returns a table of the list of all its parents

You must then find the direct parent in the table, using this list, starting with the root, if the parent does not exist then the element is kept in a table and will be retried next.

const entities = 
      [ { id: 'xi32',    name: 'Some name',   path: ',templateId1,'            } 
      , { id: 'x382',    name: 'Some name 2', path: ',templateId1,xi32,'       } 
      , { id: '2oxwo',   name: 'Some name 3', path: ',templateId1,xi32,x382,'  } 
      , { id: '2',       name: '2',           path: ',templateId1,'            } 
      , { id: '2-2',     name: '2-2',         path: ',templateId1,2,'          } 
      , { id: '3-3',     name: '3-3',         path: ',templateId1,3,'          } 
      , { id: '3-3-3',   name: '3-3-3',       path: ',templateId1,3,3-3,'      } 
      , { id: '3-3-3-3', name: '3-3-3-3',     path: ',templateId1,3,3-3,3-3-3,'} 
      , { id: '3',       name: '3',           path: ',templateId1,'            } 
      ]; 
const Result  = []
  ;
let unDone = []
  , source = entities
  ;
let cpt = 0  // just for stoping infinite loop on error
  ;
do
  {
  unDone = setResult( source, unDone.length )
  source = unDone;
  if (++cpt > 10) throw 'mince! something is rotten in the state of Denmark...'
  }
while
  (unDone.length>0)
  ;   
/* --------------------------------------------------------*/
console.log( 'result===', JSON.stringify(Result,0,2 ) )
/* --------------------------------------------------------*/

function setResult( arrayIn, nb_rej )
  {
  let orphans = [];
  for (let elData of arrayIn)
    {
    let newEl = { ...elData, children: null }  
      , parAr = getParentKey(elData.path)

    if (parAr.length===0)
      { Result.push(newEl) }
    else
      {
      let resParent = Result;
      do
        {
        let rech = parAr.pop()
          , fPar = resParent.find(treeElm=>(treeElm.id===rech.id && treeElm.path===rech.path))
          ;
        if (fPar) 
          {
          if (fPar.children===null)
            fPar.children = []
            ;
          resParent = fPar.children
          }
        else  //  throw `parent element not found : id:'${rech.id}', path:'${rech.path}'`  ;
          {
          orphans.push( { ...elData }   )
          resParent = null
          parAr.length = 0
          }  
        }
      while
        (parAr.length>0)
        ;
      if (resParent) resParent.push(newEl);
      }
    }
  if ( orphans.length>0 && orphans.length == nb_rej )
    throw ` ${nb_rej} children element(s) without parent !'`;

  return orphans
  }

function getParentKey( path )
  {                          // return array of parent element
  let rep = []
    , par = path
    , lev, bKey, xCom, idK;
  do
    {
    bKey = par.substring(0, par.lastIndexOf(','))  // remove last ','
    lev  = bKey.match(/,/g).length -1
    if (lev>0)
      {
      xCom = bKey.lastIndexOf(',')
      par  = bKey.substring(0, xCom) +',' 
      idK  = bKey.substring(++xCom)
      rep.push({ path:par, id:idK })
    } }
  while
    (lev>0)
  return rep
  }

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