Convert array of objects to nested object based on values-CodePudding

How can i convert an array of objects into nested objects based on the values between start and end?

Assume that i have an array like this:

const array = [
  {
      "content": "_88888888888  ~*8888888888*~  *8888888*_",
      "start": 5,
      "end": 37
  },
  {
      "content": "~*88888*~",
      "start": 18,
      "end": 27
  },
  {
      "content": "*88888*",
      "start": 19,
      "end": 26
  },
  {
      "content": "*88888*",
      "start": 29,
      "end": 36
  }
]

I want to convert it that:

const array = [
  {
      "content": "_88888888888  ~*88888*~  *88888*_",
      "start": 5,
      "end": 37,
      "children": [
        {
          "content": "~*88888*~",
          "start": 18,
          "end": 27,
          "children": [
            {
              "content": "*8888888888*",
              "start": 19,
              "end": 26
            },
          ]
        },
        {
          "content": "*88888*",
          "start": 29,
          "end": 36
        }
      ]
  }
]

As you can see, in expected result, every child values have parent object that matchs start and end value.

CodePudding user response：

I would iterate the array objects in order of descending span-width. Create a dummy root node with an infinite span. Then insert each object in that tree:

First find out if there is a child of the current tree node that could become a parent of the object. If so make that child the current one, and repeat.
Once there is no such child, append the object to the children collection of the current node.

Here is an implementation:

const array = [{"content": "_88888888888  ~*8888888888*~  *8888888*_","start": 5,"end": 37},{"content": "~*88888*~","start": 18,"end": 27},{"content": "*88888*","start": 19,"end": 26},{"content": "*88888*","start": 29,"end": 36}];

const root = {
    start: -Infinity,
    end: Infinity,
    children: []
};

// Iterate in order of descending span width
for (let obj of [...array].sort((a, b) => (b.end - b.start) - (a.end - a.start))) {
    let child = root, 
        children;
    // Find and drill down    
    do {
        children = (child.children ??= []);
        child = children.find(child => child.start <= obj.start && child.end >= obj.end);
    } while (child);
    // Insert
    children.push({...obj});
}

console.log(root.children);

CodePudding user response：

As with most arbitrary-nesting scenarios, we can do this with a dose of recursion.

const excluding = (os) => (xs) =>
  xs .filter ((x) => ! os .includes (x))
  
const minBy = (fn) => (xs) =>
  xs .reduce (
    ({m, c}, x, _, __, v = fn (x)) => v < m ? {m: v, c: x} : {m, c}, 
    {m: Infinity}
  ) .c

const restructure = (
  xs, 
  o = minBy (x => x .start) (xs), 
  kids = xs .filter ((x) => x !== o && x .start >= o .start && x .end <= o .end)
) => xs .length ? [
  {...o, ...(kids .length ? {children: restructure (kids)} : {})},
  ... restructure (excluding ([o, ...kids]) (xs)) 
] : []

const array = [{content: "_88888888888  ~*8888888888*~  *8888888*_", start: 5, end: 37}, {content: "~*88888*~", start: 18, end: 27}, {content: "*88888*", start: 19, end: 26}, {content: "*88888*", start: 29, end: 36}]

console .log (restructure (array))

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

We start with the helper functions, excluding, which filters a list to include all those not in another list (similar to a set difference function), and minBy, which finds the minimum element of a list, based on the result of the function supplied.

Our main function finds the first element by start value, finds all the descendants of that element (based on comparing start and end values), recurs on those descendants to create a children node, and recurs on the remaining elements to find subsequent elements of the output.

This is subtly different from Trincot's answer. Here the elements at the same level are sorted by increasing start values. That answer sorts them by decreasing range size.