How to build a menu list object recursively in Jav

Question

With an array of

['/social/swipes/women', '/social/swipes/men', '/upgrade/premium'];

I'd like to construct an map object that looks like:

{
    'social': {
        swipes: {
            women: null,
            men: null
        }
    },
    'upgrade': {
        premium: null
    }
}

const menu = ['/social/swipes/women', '/social/likes/men', '/upgrade/premium'];
const map = {};

const addLabelToMap = (root, label) => {
  if(!map[root]) map[root] = {};
  if(!map[root][label]) map[root][label] = {};
}

const buildMenuMap = menu => {
  menu
    // make a copy of menu
    // .slice returns a copy of the original array
    .slice()
    // convert the string to an array by splitting the /'s
    // remove the first one as it's empty
    // .map returns a new array
    .map(item => item.split('/').splice(1))
    // iterate through each array and its elements
    .forEach((element) => {
      let root = map[element[0]] || "";

      for (let i = 1; i < element.length; i++) {
        const label = element[i];
        addLabelToMap(root, label)
        // set root to [root][label]
        //root = ?
        root = root[label];
      }
    });
}

buildMenuMap(menu);

console.log(map);

But I'm unsure how to switch the value of root.

What do I set root to so that it recursively calls addLabelToMap with

'[social]', 'swipes' => '[social][swipes]', 'women' => '[social][swipes]', 'men'?

I've used root = root[element] but it's giving an error.

Alternative solutions would be great, but I'd like to understand why this isn't working fundamentally.

Answer 1

This problem is about creating the object and maintaining it's state while looping through input array and splitting string based upon /.

This can be accomplished using Array.reduce where we start with empty object and while looping through input we start filling it and for last word in every string we assign the value null to object property.

let input = ['/social/swipes/women', '/social/swipes/men', '/upgrade/premium'];

let output = input.reduce((o, d) => {
  let keys = d.split('/').filter(d => d)
  
  keys.reduce((k, v, i) => {
    k[v] = (i != keys.length - 1)
             ? k[v] || {} 
             : null
    
    return k[v]
  }, o)
  
  return o
}, {})

console.log(output)

Answer 2

Try this as a holistic solution:

const menu = ['/social/swipes/women', '/social/swipes/men', '/upgrade/premium'];

const deepMerge = (target, source) => {
  // Iterate through `source` properties and if an `Object` set property to merge of `target` and `source` properties
  for (let key of Object.keys(source)) {
    if (source[key] instanceof Object && key in target) Object.assign(source[key], deepMerge(target[key], source[key]))
  }

  // Join `target` and modified `source`
  Object.assign(target || {}, source)
  return target
};

const buildMenuMap = menu => {
  return menu
    .map(item => item.split('/').splice(1))

    // The `root` value is the object that we will be merging all directories into
    .reduce((root, directory) => {

      // Iterates backwards through each directory array, stacking the previous accumulated object into the current one
      const branch = directory.slice().reverse().reduce((acc, cur) => { const obj = {}; obj[cur] = acc; return obj;},null);

      // Uses the `deepMerge()` method to stitch together the accumulated `root` object with the newly constructed `branch` object.
      return deepMerge(root, branch);
    }, {});
};

buildMenuMap(menu);

Note: The deep merge solution was taken from @ahtcx on GitHubGist

Answer 3

You can simplify your code using Array.reduce, Object.keys & String.substring

buildMenuMap

The function takes the array as input and reduce it into an object where for each entry in array, the object is updated with corresponding hierarchy using addLabelToMap function. Each entry is converted into an array of levels (c.substring(1).split("/")).

addLabelToMap

The function takes 2 inputs

• obj - the current root object / node
• ar - array of child hierarchy

and returns the updated object

Logic

• function pops the first value (let key = ar.shift()) as key and add / update in the object (obj[key] = obj[key] || {};).
• If there is child hierarchy of current object (if(ar.length)), recursively call the function to update the object till the end (addLabelToMap(obj[key], ar)).
• Else (no further child hierarchy), check whether the object has some hierarchy (else if(!Object.keys(obj[key]).length)) because of other entries in array. If there is no hierarchy, i.e. it is a leaf, hence, set the value to null (obj[key] = null). Note, if there will never be case where there is an entry in array like /social/swipes/men/young along with existing, the else if block can be simplified to a simple else block.
• The object has been update, return the final updated object

let arr = ['/social/swipes/women', '/social/swipes/men', '/upgrade/premium'];

function addLabelToMap(obj, ar) {
  let key = ar.shift();
  obj[key] = obj[key] || {}; 
  if(ar.length) addLabelToMap(obj[key], ar);
  else if(!Object.keys(obj[key]).length) obj[key] = null;
  return obj;
}

function buildMenuMap(ar) {
  return ar.reduce((a,c) => addLabelToMap(a,c.substring(1).split("/")), {});
}

console.log(buildMenuMap(arr));

Answer 4

It is as easy as:

 root = root[label];

if you change your helper function to:

 const addLabelToMap = (root, label) => {
    if(!root[label]) root[label] =  {};
 }

---

I'd write it as:

 const buildMenuMap = menus => {
   const root = {};

   for(const menu of menus) {
     const keys = menu.split("/").slice(1);
     const prop = keys.pop();
     const obj = keys.reduce((curr, key) => curr[key] || (curr[key] = {}), root);
     obj[prop] = null;
  }

  return root;
}

Answer 5

You can solve this also with a recursive function in a concise way like this:

let obj={}, input = ['/social/swipes/women', '/social/swipes/men', '/upgrade/premium'];

const makeObj = (arr, obj={}) => {
  let prop = arr.shift()
  prop in obj ? null : Object.assign(obj, {[prop]: {}})
  arr.length ? makeObj(arr, obj[prop]) : obj[prop] = null
  return obj
}

input.forEach(x => makeObj(x.split('/').filter(Boolean), obj))

console.log(obj)

The idea is for each of the paths to pass them to a makeObj function which will decorate an object with the paths recursively until it reaches the end of the path array. This is another alternative to the common Array.reduce approach.

Answer 6

I just debugged your code to see what was wrong and I urge you to do the same. You make two (obvious) mistakes:

Firstly, In the very first iteration, here the value of map is just an empty object {}, the value of root gets initialised to "" and label is swipes.

.forEach((element) => {
  let root = map[element[0]] || "";
  ...
  root = root[label];
}

So then you get root[label] is undefined and so the new root is undefined.

Second, you are using map everywhere as it is.

const addLabelToMap = (root, label) => {
  if(!map[root]) map[root] = {};
  if(!map[root][label]) map[root][label] = {};
}

Instead you should be taking it as a parameter, for you to be able to do a recursion.

const addLabelToMap = (root, label) => {
  if(!root[label]) root[label] = {};
}

To debug you code, create a simple HTML file with the js in the script tags and then serve it from your local machine using python -m http.server. You can then add a debug point and go through your code step by step.