Let's say I have list of such objects:

[
    {
        "name": "test",
        "type": "sometype.type/test"
    },
    {
        "name": "test2",
        "type": "differenttype"
    },
    {
        "name": "test3",
        "type": "sometype.type/test/newtype"
    },
    {
        "name": "test4",
        "type": "sometype.type/test/newtype"
    }
]

And I want to get this result out of that list:

{
    "name": "harcodedvalue",
    "type": "harcodedvalue",
    "children": [
        {
            "name": "test2",
            "type": "differenttype",
            "children": []
        },
        {
            "name": "test",
            "type": "sometype.type/test"
            "children": [
                {
                    "name": "test3",
                    "type": "sometype.type/test/newtype",
                    "children": []
                },
                {
                    "name": "test4",
                    "type": "sometype.type/test/newtype",
                    "children": []
                },
            ]
        }
    ]
}

How to achieve that? What are steps to efficiently solve this problem? Imagine there could be like 10 levels of subtypes.

CodePudding user response：

You need to sort the input elements by their type and keep track of the eligible parents.
You then iterate over the sorted input and then look at the stack of the ancestors. If the last one is parent of the new one, you add the new node as a child.
If not, you look up one level.

const input = [
  { name: "test", type: "sometype.type/test" },
  { name: "test2", type: "differenttype" },
  { name: "test3", type: "sometype.type/test/newtype" },
  { name: "test4", type: "sometype.type/test/newtype" },
];

// hardcoded root element
const root = {
  name: "hardcoded",
  type: "hardcoded",
  children: [],
};

// stack of the ancestors. The first element is always the root.
const ancestors = [root];

// returns true if node is a child of parent.
function isParent(parent, node) {
  return node.type.startsWith(parent.type) && node.type !== parent.type;
}

// tries to find the correct parent in the ancestors stack
function findParent(node) {
  let i = ancestors.length - 1;
  while (true) {
    const parent = ancestors[i];
    if (isParent(parent, node) || i === 0) {
      // we found the parent: we add node into the stack and return the parent
      ancestors.push(node);
      return parent;
    }
    ancestors.pop();
    i--;
  }
}

input.sort((a, b) => (a.type > b.type ? 1 : a.type < b.type ? -1 : 0));

for (const item of input) {
  const node = { name: item.name, type: item.type, children: [] };
  const parent = findParent(node);
  parent.children.push(node);
}

console.log(root);

Please note you could have a lot of edge cases, if, for instance, you have many elements with the same type. In my implementation, all the nodes with the same type are grouped under the last eligible parent.