Convert array of objects to nested object based on values

Question

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.

Welcome to Stack Overflow! Please take the tour, visit the help center and read up on asking good questions. After doing some research and searching for related topics on SO, try it yourself. If you're stuck, post a minimal reproducible example of your attempt and note exactly where you're stuck. People will be glad to help. — Scott Sauyet
– Scott Sauyet, Commented Apr 4, 2022 at 12:21
Consider using an Interval Tree Also, I think your question would be more concise if you replaced the word object with the word interval or range. Particularly in your title. — Wyck
– Wyck, Commented Apr 4, 2022 at 13:38

trincot · Accepted Answer · 2022-04-04 13:13:21Z

1

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

answered Apr 4, 2022 at 13:13

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Scott Sauyet Over a year ago

Interesting. I've noticed that although we write with very different code styles, we often write similar algorithms. Here my solution is entirely different (besides the minor difference in output ordering.)

Scott Sauyet · Accepted Answer · 2022-04-04 19:45:52Z

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.

Collectives™ on Stack Overflow

Convert array of objects to nested object based on values

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related