根据字符串属性将对象数组转换为嵌套对象数组？

Question

我在尝试将平面对象数组转换为基于名称属性的嵌套对象数组时遇到问题。

将 input 数组转换为类似于 desiredOutput 数组结构的最佳方法是什么？

var input = [
    { 
        name: 'foo', 
        url: '/somewhere1',
        templateUrl: 'foo.tpl.html',
        title: 'title A', 
        subtitle: 'description A' 
    },
    { 
        name: 'foo.bar', 
        url: '/somewhere2', 
        templateUrl: 'anotherpage.tpl.html', 
        title: 'title B', 
        subtitle: 'description B' 
    },
    { 
        name: 'buzz.fizz',
        url: '/another/place',
        templateUrl: 'hello.tpl.html',  
        title: 'title C',  
        subtitle: 'description C' 
    },
    { 
        name: 'foo.hello.world', 
        url: '/',
        templateUrl: 'world.tpl.html',
        title: 'title D',   
        subtitle: 'description D' 
    }
]

var desiredOutput = [
    {
        name: 'foo',
        url: '/somewhere1',
        templateUrl: 'foo.tpl.html',
        data: {
            title: 'title A',
            subtitle: 'description A'
        },
        children: [
            {
                name: 'bar',
                url: '/somewhere2', 
                templateUrl: 'anotherpage.tpl.html',
                data: {
                    title: 'title B', 
                    subtitle: 'description B'
                }
            },
            {
                name: 'hello',
                data: {},
                children: [
                    {
                        name: 'world',
                        url: '/',
                        templateUrl: 'world.tpl.html',
                        data: {
                            title: 'title D',   
                            subtitle: 'description D'
                        }
                    }
                ]
            }
        ]
    },
    {
        name: 'buzz',
        data: {},
        children: [
            {
                name: 'fizz',
                url: '/',
                templateUrl: 'world.tpl.html',
                data: {
                    title: 'title C',   
                    subtitle: 'description C'
                }
            }
        ]
    }
]

请注意，无法保证输入数组中对象的顺序。此代码将在 Node.js 环境中运行，我愿意使用 lodash 等库来实现所需的输出。

非常感谢任何帮助。

Answer 1

此解决方案仅使用本机 JS 方法。它可以肯定地进行优化，但我将其保留原样以使其更容易跟进（或者我希望如此）。我还注意不要修改原始输入，因为 JS 通过引用传递对象。

var input = [{
  name: 'foo',
  url: '/somewhere1',
  templateUrl: 'foo.tpl.html',
  title: 'title A',
  subtitle: 'description A'
}, {
  name: 'foo.bar',
  url: '/somewhere2',
  templateUrl: 'anotherpage.tpl.html',
  title: 'title B',
  subtitle: 'description B'
}, {
  name: 'buzz.fizz',
  url: '/another/place',
  templateUrl: 'hello.tpl.html',
  title: 'title C',
  subtitle: 'description C'
}, {
  name: 'foo.hello.world',
  url: '/',
  templateUrl: 'world.tpl.html',
  title: 'title D',
  subtitle: 'description D'
}];

// Iterate over input array elements
var desiredOutput = input.reduce(function createOuput(arr, obj) {
  var names = obj.name.split('.');
  // Copy input element object as not to modify original input
  var newObj = Object.keys(obj).filter(function skipName(key) {
    return key !== 'name';
  }).reduce(function copyObject(tempObj, key) {
    if (key.match(/url$/i)) {
      tempObj[key] = obj[key];
    }
    else {
      tempObj.data[key] = obj[key];
    }

    return tempObj;
  }, {name: names[names.length - 1], data: {}});

  // Build new output array with possible recursion
  buildArray(arr, names, newObj);

  return arr;
}, []);

document.write('<pre>' + JSON.stringify(desiredOutput, null, 4) + '</pre>');

// Helper function to search array element objects by name property
function findIndexByName(arr, name) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (arr[i].name === name) {
      return i;
    }
  }

  return -1;
}

// Recursive function that builds output array
function buildArray(arr, paths, obj) {
  var path = paths.shift();
  var index = findIndexByName(arr, path);

  if (paths.length) {
    if (index === -1) {
      arr.push({
        name: path,
        children: []
      });

      index = arr.length - 1;
    }

    if (!Array.isArray(arr[index].children)) {
      arr[index].children = [];
    }

    buildArray(arr[index].children, paths, obj);
  } else {
    arr.push(obj);
  }

  return arr;
}

Answer 2

使用 Lodash（因为到底为什么要在没有实用程序库的情况下操作复杂数据）。这里是 the fiddle.

function formatRoute(route) {
    return _.merge(_.pick(route, ['url', 'templateUrl']), {
        name: route.name.split('.'),
        data: _.pick(route, ['title', 'subtitle']),
        children: []
    });
}

function getNameLength(route) {
    return route.name.length;
}

function buildTree(tree, route) {
    var path = _.slice(route.name, 0, -1);

    insertAtPath(tree, path, _.merge({}, route, {
        name: _.last(route.name)
    }));

    return tree;
}

function insertAtPath(children, path, route) {
    var head = _.first(path);

    var match = _.find(children, function (child) {
        return child.name === head;
    });

    if (path.length === 0) {
        children.push(route);
    }
    else {
        if (!match) {
            match = {
                name: head,
                data: {},
                children: []
            };
            children.push(match);
        }

        insertAtPath(match.children, _.rest(path), route);
    }
}


// Map the routes into their correct formats.
var routes = _.sortBy(_.map(input, formatRoute), getNameLength);

// Now we can reduce this well formatted array into the desired format.
var out = _.reduce(routes, buildTree, []);

它的工作原理是重塑初始输入，以便将名称拆分为数组并添加数据/子属性。然后它减少 buildTree 上的数据，它使用变异函数 ( :( ) 将当前项目插入到给定路径的 reduce 中。

奇怪的 if (!match) 部分确保添加缺失的片段，如果它们没有在初始数据集中用 URL 等明确指定

实际完成工作的最后两行可能应该在一个小函数中，它可以用一些 JSDoc 来完成。很遗憾我没有完全递归，我依靠数组变异将路由对象插入树深处。

不过应该很简单。

Answer 3

这是我的 Lodash-based 尝试。

首先，我发现_.set可以理解deeply-nestedobject符号，所以我用它来构建树编码parent-child关系：

var tree = {};
input.forEach(o => _.set(tree, o.name, o));

这会产生：

{
    "foo": {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "title": "title A",
        "subtitle": "description A",
        "bar": {
            "name": "foo.bar",
            "url": "/somewhere2",
            "templateUrl": "anotherpage.tpl.html",
            "title": "title B",
            "subtitle": "description B"
        },
        "hello": {
            "world": {
                "name": "foo.hello.world",
                "url": "/",
                "templateUrl": "world.tpl.html",
                "title": "title D",
                "subtitle": "description D"
            }
        }
    },
    "buzz": {
        "fizz": {
            "name": "buzz.fizz",
            "url": "/another/place",
            "templateUrl": "hello.tpl.html",
            "title": "title C",
            "subtitle": "description C"
        }
    }
}

这实际上是令人痛苦的 so-close-yet-so-far 来自所需的输出。但是 children 的名称与 title 等其他属性一起显示为属性。

然后是编写递归函数的费力过程，该函数采用这棵中间树并按照您希望的方式重新格式化它：

它首先需要找到 children 属性，并将它们移动到 children 属性数组中。
然后它必须处理这样一个事实，对于长链，foo.hello.world中的hello这样的中间节点没有任何数据，所以它必须插入data: {}和name 个属性。
最后，它会清理剩下的内容：将标题和副标题放在 data 属性中，并清理仍然 fully-qualified 的所有 name。

代码：

var buildChildrenRecursively = function(tree) {
  var children = _.keys(tree).filter(k => _.isObject(tree[k]));
  if (children.length > 0) {

    // Step 1 of reformatting: move children to children
    var newtree = _.omit(tree, children);
    newtree.children = children.map(k => buildChildrenRecursively(tree[k]));

    // Step 2 of reformatting: deal with long chains with missing intermediates
    children.forEach((k, i) => {
      if (_.keys(newtree.children[i]).length === 1) {
        newtree.children[i].data = {};
        newtree.children[i].name = k;
      }
    });

    // Step 3 of reformatting: move title/subtitle to data; keep last field in name
    newtree.children = newtree.children.map(function(obj) {
      if ('data' in obj) {
        return obj;
      }
      var newobj = _.omit(obj, 'title,subtitle'.split(','));
      newobj.data = _.pick(obj, 'title,subtitle'.split(','));
      newobj.name = _.last(obj.name.split('.'));
      return newobj;
    });

    return (newtree);
  }
  return tree;
};

var result = buildChildrenRecursively(tree).children;

输出：

[
    {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "children": [
            {
                "name": "bar",
                "url": "/somewhere2",
                "templateUrl": "anotherpage.tpl.html",
                "data": {
                    "title": "title B",
                    "subtitle": "description B"
                }
            },
            {
                "children": [
                    {
                        "name": "world",
                        "url": "/",
                        "templateUrl": "world.tpl.html",
                        "data": {
                            "title": "title D",
                            "subtitle": "description D"
                        }
                    }
                ],
                "data": {},
                "name": "hello"
            }
        ],
        "data": {
            "title": "title A",
            "subtitle": "description A"
        }
    },
    {
        "children": [
            {
                "name": "fizz",
                "url": "/another/place",
                "templateUrl": "hello.tpl.html",
                "data": {
                    "title": "title C",
                    "subtitle": "description C"
                }
            }
        ],
        "data": {},
        "name": "buzz"
    }
]

胜利者获得战利品。

Answer 4

此解决方案不使用递归，它使用指向对象图中前一项的引用指针。

请注意，此解决方案确实使用了 lodash。此处的 JSFiddle 示例 http://jsfiddle.net/xpb75dsn/1/

var input = [
    {
        name: 'foo',
        url: '/somewhere1',
        templateUrl: 'foo.tpl.html',
        title: 'title A',
        subtitle: 'description A'
    },
    {
        name: 'foo.bar',
        url: '/somewhere2',
        templateUrl: 'anotherpage.tpl.html',
        title: 'title B',
        subtitle: 'description B'
    },
    {
        name: 'buzz.fizz',
        url: '/another/place',
        templateUrl: 'hello.tpl.html',
        title: 'title C',
        subtitle: 'description C'
    },
    {
        name: 'foo.hello.world',
        url: '/',
        templateUrl: 'world.tpl.html',
        title: 'title D',
        subtitle: 'description D'
    }
];

var nameList = _.sortBy(_.pluck(input, 'name'));
var structure = {};

var mapNav = function(name, navItem) {
    return {
        name : name,
        url : navItem.url,
        templateUrl : navItem.templateUrl,
        data : { title : navItem.title, subtitle : navItem.subtitle },
        children : []
    };
};

_.map(nameList, function(fullPath) {
    var path = fullPath.split('.');
    var parentItem = {};
    _.forEach(path, function(subName, index) {
        var navItem = _.find(input, { name : fullPath });
        var item = mapNav(subName, navItem);
        if (index == 0) {
            structure[subName] = item;
        } else {
            parentItem.children.push(item);
        }
        parentItem = item;
    });
});


var finalStructure = Object.keys(structure).map(function(key) {
    return structure[key];
});

console.log(finalStructure);

Answer 5

这是一个完全 recursion-free 使用 lodash 的方法。当我想到 _.set 和 _.get 有多好时，我想到了它，我意识到我可以用 children 的序列替换 object "paths"。

首先，构建一个 object/hash table，键等于 input 数组的 name 属性：

var names = _.object(_.pluck(input, 'name'));
// { foo: undefined, foo.bar: undefined, buzz.fizz: undefined, foo.hello.world: undefined }

（不要尝试 JSON.stringify 这个 object！因为它的值都是未定义的，它的计算结果是 {}…）

接下来，对每个元素应用两个转换：(1) 将标题和副标题清理为 sub-property data，以及 (2) 这有点棘手，找到所有中间值buzz 和 foo.hello 之类的路径在 input 中未表示，但在 children 中表示。将此 array-of-arrays 展平并按 name 字段中 . 的数量对它们进行排序。

var partial = _.flatten(
    input.map(o =>
              {
                var newobj = _.omit(o, 'title,subtitle'.split(','));
                newobj.data = _.pick(o, 'title,subtitle'.split(','));
                return newobj;
              })
        .map(o => {
          var parents = o.name.split('.').slice(0, -1);
          var missing =
              parents.map((val, idx) => parents.slice(0, idx + 1).join('.'))
                  .filter(name => !(name in names))
                  .map(name => {
                    return {
                      name,
                      data : {},
                    }
                  });

          return missing.concat(o);
        }));
partial = _.sortBy(partial, o => o.name.split('.').length);

这段代码可能看起来令人生畏，但看到它输出的内容应该会让您相信它非常简单：它只是一个平面数组，包含原始 input 加上所有不在 input 中的中间路径，按 name 中的点数排序，每个点都有一个新的 data 字段。

[
    {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "data": {
            "title": "title A",
            "subtitle": "description A"
        }
    },
    {
        "name": "buzz",
        "data": {}
    },
    {
        "name": "foo.bar",
        "url": "/somewhere2",
        "templateUrl": "anotherpage.tpl.html",
        "data": {
            "title": "title B",
            "subtitle": "description B"
        }
    },
    {
        "name": "buzz.fizz",
        "url": "/another/place",
        "templateUrl": "hello.tpl.html",
        "data": {
            "title": "title C",
            "subtitle": "description C"
        }
    },
    {
        "name": "foo.hello",
        "data": {}
    },
    {
        "name": "foo.hello.world",
        "url": "/",
        "templateUrl": "world.tpl.html",
        "data": {
            "title": "title D",
            "subtitle": "description D"
        }
    }
]

我们几乎可以自由回家了。最后剩下的魔法需要存储一些全局状态。我们将遍历这个平面 partial 数组，将 name 字段替换为 _.get 和 _.set 可以使用的包含 children 和数字索引的路径:

foo 被映射到 children.0
buzz 至 children.1、
foo.bar 到 children.0.children.0，等等

当我们迭代（不是递归地！）构建这个路径序列时，我们使用 _.set 将上面 partial 的每个元素注入到其适当的位置。

代码：

var name2path = {'empty' : ''};
var out = {};
partial.forEach(obj => {
  var split = obj.name.split('.');
  var par = name2path[split.slice(0, -1).join('.') || "empty"];
  var path = par + 'children.' + (_.get(out, par + 'children') || []).length;
  name2path[obj.name] = path + '.';
  _.set(out, path, obj);
});
out = out.children;

这个 object/hash name2path 将名称转换为 _.settable 路径：它是用一个键 empty 初始化的，迭代添加到它.在这个代码是运行:

之后看看这个 name2path 是什么很有帮助

{
    "empty": "",
    "foo": "children.0.",
    "buzz": "children.1.",
    "foo.bar": "children.0.children.0.",
    "buzz.fizz": "children.1.children.0.",
    "foo.hello": "children.0.children.1.",
    "foo.hello.world": "children.0.children.1.children.0."
}

注意迭代如何递增索引以在 children 属性数组中存储多个条目。

最终结果out：

[
    {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "data": {
            "title": "title A",
            "subtitle": "description A"
        },
        "children": [
            {
                "name": "foo.bar",
                "url": "/somewhere2",
                "templateUrl": "anotherpage.tpl.html",
                "data": {
                    "title": "title B",
                    "subtitle": "description B"
                }
            },
            {
                "name": "foo.hello",
                "data": {},
                "children": [
                    {
                        "name": "foo.hello.world",
                        "url": "/",
                        "templateUrl": "world.tpl.html",
                        "data": {
                            "title": "title D",
                            "subtitle": "description D"
                        }
                    }
                ]
            }
        ]
    },
    {
        "name": "buzz",
        "data": {},
        "children": [
            {
                "name": "buzz.fizz",
                "url": "/another/place",
                "templateUrl": "hello.tpl.html",
                "data": {
                    "title": "title C",
                    "subtitle": "description C"
                }
            }
        ]
    }
]

嵌入的代码段仅包含代码，没有中间 JSON 来分散您的注意力。

这比我之前提交的更好吗？我认为是这样：这里的簿记要少得多，不透明的 "busy code" 少得多，结构 high-level 多。我认为缺少递归有帮助。我认为最后的 forEach 可能会被替换为 reduce，但我没有尝试，因为算法的其余部分是如此 vector-based 和迭代，我不想发散从那个。

很抱歉把所有东西都留在了 ES6 中，我非常喜欢它:)

var input = [{
  name: 'foo',
  url: '/somewhere1',
  templateUrl: 'foo.tpl.html',
  title: 'title A',
  subtitle: 'description A'
}, {
  name: 'foo.bar',
  url: '/somewhere2',
  templateUrl: 'anotherpage.tpl.html',
  title: 'title B',
  subtitle: 'description B'
}, {
  name: 'buzz.fizz',
  url: '/another/place',
  templateUrl: 'hello.tpl.html',
  title: 'title C',
  subtitle: 'description C'
}, {
  name: 'foo.hello.world',
  url: '/',
  templateUrl: 'world.tpl.html',
  title: 'title D',
  subtitle: 'description D'
}];

var names = _.object(_.pluck(input, 'name'));

var partial = _.flatten(
  input.map(o => {
    var newobj = _.omit(o, 'title,subtitle'.split(','));
    newobj.data = _.pick(o, 'title,subtitle'.split(','));
    return newobj;
  })
  .map(o => {
    var parents = o.name.split('.').slice(0, -1);
    var missing =
      parents.map((val, idx) => parents.slice(0, idx + 1).join('.'))
      .filter(name => !(name in names))
      .map(name => {
        return {
          name,
          data: {},
        }
      });

    return missing.concat(o);
  }));
partial = _.sortBy(partial, o => o.name.split('.').length);

var name2path = {
  'empty': ''
};
var out = {};

partial.forEach(obj => {
  var split = obj.name.split('.');
  var par = name2path[split.slice(0, -1).join('.') || "empty"];
  var path = par + 'children.' + (_.get(out, par + 'children') || []).length;
  name2path[obj.name] = path + '.';
  _.set(out, path, obj);
});
out = out.children;

根据字符串属性将对象数组转换为嵌套对象数组？

Convert an array of objects into a nested array of objects based on string property?

javascript

arrays

tree

javascript-objects

lodash