从物化路径创建特定的树结构

Question

我有 "Entities" 和 "Entity Templates"。顶级实体与 "templateId1" 实体模板相关联。从那里一个实体通过使用它的 id 绑定到路径中的另一个实体。我试图以一种有效的方式结束以下数据结构：

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
                  }
                ]
              }
            ]
          }
        ]
      }
    ];

该结构的最初灵感来自 MongoDB 文档：

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

我有一个稍微不同的用例，"Entity Template" 是顶级父级，但在 "Entities" 中用例是相同的。非常感谢任何见解。

Answer 1

我已经做到了... 我添加了一种防止任何键乱的排序。

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

最后我设法编写了这个代码，调试了很多，因为有很多陷阱。

想法是 json 分几次通过，每次都计算剩余元素的数量。

如果这个数字没有从一次通过到另一次减少，那么 pgm 发送错误并停止。

对于每个要添加的元素，我们计算假定的父元素 getParentKey()，其中 returns 是其所有父元素列表的 table

然后您必须使用此列表在 table 中找到直接父级，从根开始，如果父级不存在，则该元素将保留在 table 中并将接下来重试。

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; }

从物化路径创建特定的树结构

Creating a specific tree structure from materialized path

javascript

arrays

mongodb

materialized-path-pattern