从路径字符串优化嵌套数组

Question

考虑到这个简单的对象数组：

var allPaths = [
  {path: "/", component: 'cmp-1'},
  {path: "/my-cool-list/", component: 'cmp-2'},
  {path: "/my-cool-list/this-is-card-1", component: 'cmp-3'},
  {path: "/my-cool-list/this-is-card-2", component: 'cmp-4'},
  {path: "/blog/", component: 'cmp-5'},
  {path: "/blog/2017/01/this-is-card-3", component: 'cmp-6'},
  {path: "/blog/2017/02/this-is-card-4", component: 'cmp-7'},
  {path: "/recettes/", component: 'cmp-8'},
  {path: "/recettes/this-is-card-5", component: 'cmp-9'},
  {path: "/recettes/this-is-card-6", component: 'cmp-10'}
]

有必要生产这一产出：

[
  {
    path: "/", component: 'cmp-1'
  },
  {
    path: "/my-cool-list",
    component: 'cmp-2',
    children: [
      {path: "/this-is-card-1", component: 'cmp-3'},
      {path: "/this-is-card-2", component: 'cmp-4'}
    ]
  },

  {
    path: "/blog",
    component: 'cmp-5',
    children: [
      {
        path: "/2017",
        children: [
          {
            path: "/01",
            children: [
              {path: "/this-is-card-3", component: 'cmp-6'}
            ]
          },
          {
            path: "/02",
            children: [
              {path: "/this-is-card-4", component: 'cmp-7'}
            ]
          }
        ]
      }
    ]
  },

  {
    path: "/recettes",
    component: 'cmp-8',
    children: [
      {path: "/this-is-card-5", component: 'cmp-9'},
      {path: "/this-is-card-6", component: 'cmp-10'}
    ]
  },
]

我发现这样做的一种方法是：

1. 遍历allPaths中的每个对象
2. 为每个路径创建一个有效的输出(例如，如果只提供此路径)
3. 将结果对象推到名为tree的数组中
4. ...rinse和重复..。
5. 然后将产生的tree深度合并成一个唯一的。

代码看起来类似于这个小提琴在这里

let tree = []

// Recursive Tree Builder
const buildTree = (pathArray, ...others) => {
    var currentToken = pathArray.shift()
    var arr = []
    if (pathArray.length>0) {
       arr.push( {path: '/'+currentToken, children: []} )
       arr[0].children = buildTree(pathArray, ...others)
    } else {
       arr.push( Object.assign( {path: '/'+currentToken}, others[0] ))
    }
    return arr;  
}

// For each object in `allPaths`, build a tree
allPaths.map( page => {
   let {path, ...rest} = page    
   let res = buildTree(path.split('/').slice(1), rest)
   tree.push(res[0])
})

// external code to deeply merge each objects in `tree` (external library: no need to put the code here but you got the point)

我想应该有一种方法可以懒洋洋地构造最终输出，而不需要在结束时进行另一次合并操作:就像在没有中间存储+另一个操作的情况下构建最终的树一样。

为了进一步缩小问题的范围，我试图在飞行中建立树，但当我试图将一个条目推到树中的精确位置时，我被卡住了。例如，保持对tree[0].children[0].children[0].children[0] ...的引用会使我感到困扰，因为我不知道我会发现相关的路径有多深，或者children是否会在这个级别上存在。

一个伪代码(我想)是：

1. 逐个遍历allPaths对象

(假设遍历的第一个对象具有类似于/blog/level-2__的路径)

1. 在tree中搜索path中的第1层(例如：/blog/level-2中的/blog )
2. 没找到？然后，在树中推送对象。
3. 这条路径还有进一步的层次(如/blog/level-2中的)？
4. .......yes？深入一层(/level-2)到children，并从第3步重复
5. .......no？重置级别为0。中断

现在，我很难实现那些级别的跟踪，因为：-我不知道如何轻松地查询给定路径的tree：/blog/level-2可能在tree[2].children[14]或tree[32].children[57]，我很难查询它，但是还要存储这些信息供以后使用。

有什么想法吗？

Answer 1

好吧我自己想出来的。

const appendToTree = (tree, obj) => {
  // extract path from object
  let {path, ...rest} = obj

  // turn path into array of params
  let URLparams = path.split('/').slice(1)

  // recursive calls could send empty array
  if (URLparams.length === 0) return tree

  // take out first element in array: removes it from the array as well
  let currentURLparam = URLparams.shift()
  // reset path to what's left in URLparams after shift
    path = '/' + URLparams.join('/')

  let currentPosition = 0, 
      currentNode = {},
      found = false

loopTree:  // find corresponding param in tree
  for(currentPosition; currentPosition < tree.length; currentPosition++) {
    if (tree[currentPosition].path === '/'+currentURLparam) {
       currentNode = tree[currentPosition]
       found = true
       break loopTree
    }
  }

  if(  found ) {  // found a matching path
    // get a reference to children or create an empty one
    currentNode['children'] = currentNode.children || []
    // repeat all, but with current reference and val which has been shifted before
    return appendToTree(currentNode.children, {path, ...rest})
  } else {  // not matching path found: insert it
    if (URLparams.length > 0) {  // still have URL params left ?
       // push current page object into array
       // Here we could force any default props to index levels
       let pos = tree.push({path: '/'+currentURLparam, children: []}) - 1
       // we still have params to process, so we proceed another iteration
       return appendToTree(tree[pos].children, {path, ...rest})
    } else { // no URL params left, this is the last one in stack
       tree.push({path: '/'+currentURLparam, ...rest})
       return tree
    }
  }
}



const buildTree = (tree, pages) => {
  // Traverse all pages objects and append each to provided tree
  pages.map(page => {
    appendToTree(tree, page)
  })
  return tree
}

然后，我们只需要打电话：

buildTree([], allPaths)

当我们遍历...it中的每个对象时，allPaths将正确地动态创建一棵树。为了解决我的问题，我使用了递归。