Create nested object from array javascript-CodePudding

I have a SharePoint list that I am manipulating in javascript via REST. I need to convert the array from REST into a nested object. I am building a navigation menu based on the structure. The array consists of ID, Title, Parent, and Level. The level is either Top, Mid, or Bot, and the Parent lists the Title of whichever entry is its parent.

let orgs = [{
    id: "0",
    title: "A",
    parent: "",
    level: "Top"
  },{
    id: "1",
    title: "Org A1",
    parent: "A",
    level: "Middle"
  },
  {
    id: "2",
    title: "Org A2",
    parent: "A",
    level: "Middle"
  },
  {
    id: "3",
    title: "Org A3",
    parent: "A",
    level: "Middle"
  },
  {
    id: "5",
    title: "Org A1-A",
    parent: "Org A1",
    level: "Bottom"
  },
  {
    id: "6",
    title: "Org A1-B",
    parent: "Org A1",
    level: "Bottom"
  },
  {
    id: "7",
    title: "Org A2-A",
    parent: "Org A2",
    level: "Bottom"
  },
  {
    id: "8",
    title: "Org A2-B",
    parent: "Org A2",
    level: "Bottom"
  },  
  {
    id: "9",
    title: "Org A3-A",
    parent: "Org A3",
    level: "Bottom"
  },
  {
    id: "10",
    title: "Org A3-B",
    parent: "Org A3",
    level: "Bottom"
  }
];

I am trying to iterate over the array and add the title for the children to the appropriate parent. The goal structure for the object is:

const orgObj = {
  Title: "Org A",
  mid: [{
    Title: "Org A1",
    bot: [{
      Title: "Org A1-A"
    }, {
      Title: "Org A1-B"
    }]
  }, {
    Title: "Org A2",
    bot: [{
      Title: "Org A2-A"
    }, {
      Title: "Org A2-B"
    }]
  }, {
    Title: "Org A3",
    bot: [{
      Title: "Org A3-A"
    }, {
      Title: "Org A3-B"
    }]
  }]
};

I was trying to use map function but I can't get the results to work. I've been at this for a few days on and off and cannot seem to get it to work. I don't have access to the code I've tried so far at my current location, but I will try to update when I can get it. In my head, this shouldn't be complicated.

CodePudding user response：

You could use the following algorithm which will construct the tree for you in linear time O(n).

I am using Maps quite heavily here to keep the runtime linear.

First, I create a Map which maps each title to the corresponding data. I need this later so I can quickly lookup the data for any parent an org might have. The result will be this:

Map(10) {
  'A' => { id: '0', title: 'A', parent: '', level: 'Top' },
  'Org A1' => { id: '1', title: 'Org A1', parent: 'A', level: 'Middle' },
  'Org A2' => { id: '2', title: 'Org A2', parent: 'A', level: 'Middle' },
  'Org A3' => { id: '3', title: 'Org A3', parent: 'A', level: 'Middle' },
  'Org A1-A' => { id: '5', title: 'Org A1-A', parent: 'Org A1', level: 'Bottom' },
  'Org A1-B' => { id: '6', title: 'Org A1-B', parent: 'Org A1', level: 'Bottom' },
  'Org A2-A' => { id: '7', title: 'Org A2-A', parent: 'Org A2', level: 'Bottom' },
  'Org A2-B' => { id: '8', title: 'Org A2-B', parent: 'Org A2', level: 'Bottom' },
  'Org A3-A' => { id: '9', title: 'Org A3-A', parent: 'Org A3', level: 'Bottom' },
  'Org A3-B' => { id: '10', title: 'Org A3-B', parent: 'Org A3', level: 'Bottom' }
}

Then I also create a mapping between level and prop name to account for that you don't have a uniform children prop but mid or bot depending on the level of the parent.

Now the actual tree construction begins. I loop through all the orgs again using reduce() and start of with an empty JavaScript object. For each item I create the target object (newObj) which just holds the Title and get the parent using the Map from above. If there is no parent this is the top-most element.

If it is not the parent, I can lookup the reference to the parent object within the orgChart object using my quickRefs Map. Then I have the reference to the parent node within the tree. Now I need to get the name of the children property mid or bot based on the level of the parent.

Now using that property name I can assign the parent node this new property with the value being the new child object. If the parent already has a child object I can simply push another child object onto that array, if not I need to create a new array and push the child object onto that.

Last but not least I need to insert the reference to the new object into my quickRefs Map, so if I later encounter an object which is a child of the now inserted item I can directly assign children to that object as described above.

const input = [
  {
    id: "0",
    title: "A",
    parent: "",
    level: "Top",
  },
  {
    id: "1",
    title: "Org A1",
    parent: "A",
    level: "Middle",
  },
  {
    id: "2",
    title: "Org A2",
    parent: "A",
    level: "Middle",
  },
  {
    id: "3",
    title: "Org A3",
    parent: "A",
    level: "Middle",
  },
  {
    id: "5",
    title: "Org A1-A",
    parent: "Org A1",
    level: "Bottom",
  },
  {
    id: "6",
    title: "Org A1-B",
    parent: "Org A1",
    level: "Bottom",
  },
  {
    id: "7",
    title: "Org A2-A",
    parent: "Org A2",
    level: "Bottom",
  },
  {
    id: "8",
    title: "Org A2-B",
    parent: "Org A2",
    level: "Bottom",
  },
  {
    id: "9",
    title: "Org A3-A",
    parent: "Org A3",
    level: "Bottom",
  },
  {
    id: "10",
    title: "Org A3-B",
    parent: "Org A3",
    level: "Bottom",
  },
];

// store titles to their data so we can find a parent object in constant time
const map = input.reduce((all, cur) => (all.set(cur.title, cur), all), new Map());

// mapping for the property names
// if the parent is level "Top", we need to use "mid"
// if the parent is level "Middle", we need to use "bot"
const mapLevelToPropName = {
  Top: "mid",
  Middle: "bot",
}

// stores references to objects within the object, so they can be accessed in constant time
const quickRefs = new Map();
const output = input.reduce((orgChart, org) => {
  const parent = map.get(org.parent);
  const newObj = {
    Title: org.title
  }
  if(parent === undefined) {
    // top most org
    orgChart = newObj
  }
  else {
    // some org in the middle which has a parent
    // get the reference to the parent within the JS object using the quickRefs map
    const refToParentObj = quickRefs.get(org.parent)
    // determine the name of the "children" property based on the level of the parent
    const propName = mapLevelToPropName[parent.level];
    // check if there already are childrens (mid, bot)
    // if yes: append another one to array
    if(refToParentObj[propName]) refToParentObj[propName].push(newObj);
    // if no: add new object within an array
    else refToParentObj[propName] = [newObj];
  }
  // add a reference to the new object into the quickRefs map so 
  // when we find a child we can just grab that reference and add the child 
  quickRefs.set(org.title, newObj);
  return orgChart;
}, {})

console.log(JSON.stringify(output, null, 2));

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

This implementation assumes that child orgs only ever appear after parent orgs within the input array, but will work for deeply nested structures (although the "mid", "bot" functionality might not be suitable for this).

CodePudding user response：

Here's one way to do it...

let orgs = [{
  id: "0",
  title: "Org A",
  parent: "",
  level: "Top"
},{
  id: "1",
  title: "Org A1",
  parent: "Org A",
  level: "Middle"
},
{
  id: "2",
  title: "Org A2",
  parent: "Org A",
  level: "Middle"
},
{
  id: "3",
  title: "Org A3",
  parent: "Org A",
  level: "Middle"
},
{
  id: "5",
  title: "Org A1-A",
  parent: "Org A1",
  level: "Bottom"
},
{
  id: "6",
  title: "Org A1-B",
  parent: "Org A1",
  level: "Bottom"
},
{
  id: "7",
  title: "Org A2-A",
  parent: "Org A2",
  level: "Bottom"
},
{
  id: "8",
  title: "Org A2-B",
  parent: "Org A2",
  level: "Bottom"
},  
{
  id: "9",
  title: "Org A3-A",
  parent: "Org A3",
  level: "Bottom"
},
{
  id: "10",
  title: "Org A3-B",
  parent: "Org A3",
  level: "Bottom"
}
];

let roots = {};

orgs.forEach(org => {
  if (org.parent) {
    let parent = orgs.find(o => o.title === org.parent)
    if (parent.level === 'Top') {
      if (!parent.mid) parent.mid = [];
      parent.mid.push(org);
    } else if (parent.level === 'Middle') {
      if (!parent.bot) parent.bot = [];
      parent.bot.push(org);
    }
  } else {
    roots[org.title] = org;
  }
})

console.log(JSON.stringify(Object.values(roots), null, 2));