How to loop through this nested object?

Question

I have a dynamically generated JavaScript object which consist of nested objects and arrays. I couldn't find a proper way to list all nested objects, since that particular object is created dynamically.

Here is the object:

var tagdata = {
  "Sentence": [{
      "NP": [{
          "NMP": "cat"
        }, {
          "NMP": "dog"
        }]
    }, {
      "VP": [{
          "KPD": "tree"
        }, {
          "NP": [{
              "NMP": "ball"
            }, {
              "NMP": "bat"
            }]
        },{
          "NP": [{
              "NMP": "ground"
            }, {
              "NMP": "time"
            }]
        }]
    }]
};

The output I require looks like this:

[{ key: 1, text: 'Sentence' },
 { key: 2, text: 'NP', parent: 1 },
 { key: 3, text: 'VP', parent: 1 },
 { key: 4, text: 'NMP', parent: 2 },
 { key: 5, text: 'NMP', parent: 2 },
 { key: 6, text: 'KPD', parent: 3 },
 { key: 7, text: 'NP', parent: 3 },
 { key: 8, text: 'NP', parent: 3 },
 { key: 9, text: 'cat', parent: 4 },
 { key: 10, text: 'dog', parent: 5 },
 { key: 11, text: 'tree', parent: 6 },
 { key: 12, text: 'NMP', parent: 7 },
 { key: 13, text: 'NMP', parent: 7 },
 { key: 14, text: 'NMP', parent: 8 },
 { key: 15, text: 'NMP', parent: 8 },
 { key: 16, text: 'ball', parent: 12},
 { key: 17, text: 'bat', parent: 13},
 { key: 18, text: 'ground', parent: 14},
 { key: 19, text: 'time', parent: 15},]

This data is to be used in a tree, so the order might be different, but the key:parent relationship should be maintained. Here is the code I've tried with:

let newtags=[{key:1,text:'Sentence'}];
tagdata["Sentence"].map( (elem,x) => {    
  newtags.push({key:x,text:Object.keys(elem)[0],parent:x});
  if(Object.keys(elem)[0].length !== 0){
    var y=x+1;
    newtags.push({key:y,text:Object.values(elem)[0][x],parent:y});
  }    
});

console.log(newtags);

Answer 1

Your code works for the first level, but in your attempt to go one level deeper you will assign duplicate key values (y=x+1 when x will have that value in the next iteration of the .map() method as well).

What you need here is a recursive function, one that calls itself to deal with nested levels in the same way as any other level.

You could use this ES6, functional programming solution for that:

function listItems(obj) {
    var key = 0;
    return (function recurse(obj, parent = undefined) {
        return Object(obj) !== obj ? { key: ++key, text: obj, parent }
            :   Array.isArray(obj) ? Object.keys(obj).reduce( (acc, text) =>
                    acc.concat(recurse(obj[text], parent)), [])
            :   Object.keys(obj).reduce( (acc, text) =>
                    acc.concat({ key: ++key, text, parent },
                                recurse(obj[text], key)), []);
    })(obj);
}

// Sample data
var tagdata = {
  "Sentence": [{
      "NP": [{ "NMP": "cat" }, { "NMP": "dog" }]
    }, {
      "VP": [{
          "KPD": "tree"
        }, {
          "NP": [{ "NMP": "ball" }, { "NMP": "bat" }]
        },{
          "NP": [{ "NMP": "ground" }, { "NMP": "time" }]
        }]
    }]
};

// Extract the objects and output:
console.log(listItems(tagdata));

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

Answer 2

I think this does what you want. It uses a recursive algorithm that handles the case where you have an array separately from the case where you have an object. The base case of just a string is handled in processChild.

let state = [];

function processChild(child, parent) {
  if (Array.isArray(child)) {
    return processArray(child, parent);
  }

  if (typeof(child) == 'object') {
    return processObject(child, parent);
  }

  let tag = {
    key: state.length + 1,
    text: child,
  };
  if (parent) {
    tag.parent = parent;
  }
  state.push(tag);
}

function processObject(object, parent) {
  parent = parent || 0;

  let keys = Object.keys(object);
  for (let i = 0; i < keys.length; i++) {
    //console.log(keys[i]);
    let tagIndex = state.length + 1;
    let text = keys[i];
    let tag = {
      key: tagIndex,
      text: text,
    };
    if (parent) {
      tag.parent = parent;
    }

    state.push(tag);

    let child = object[keys[i]];
    processChild(child, tagIndex);
  }
}

function processArray(array, parent) {
  parent = parent || 0;
  for (let i = 0; i < array.length; i++) {
    //console.log(array[i]);
    let child = array[i];
    //console.log('Child', child);
    processChild(child, parent);
  }
}

function process(){
  let initialState = JSON.parse(input.innerHTML);
  processChild(initialState);
  code.innerHTML = JSON.stringify(state).replace(/},/g,'},\n');
}

#input{
  width: 100%;
  height: 200px;
}

<textarea id="input">
  {
  "Sentence": [{
    "NP": [{
      "NMP": "cat"
    }, {
      "NMP": "dog"
    }]
  }, {
    "VP": [{
      "KPD": "tree"
    }, {
      "NP": [{
        "NMP": "ball"
      }, {
        "NMP": "bat"
      }]
    }, {
      "NP": [{
        "NMP": "ground"
      }, {
        "NMP": "time"
      }]
    }]
  }]
}
</textarea>
<button onClick="process()">Process</button>
<pre id="code"></pre>

Answer 3

Just for fun, a non-recursive approach.

• One array keeps track of the eventual results (results)
• One array keeps track of data-to-process
• When nested data is found, it is wrapped in a "to-do item" and added to the todo array
• Repeat until no items left

var tagData = [{Sentence:[{NP:[{NMP:"cat"},{NMP:"dog"}]},{VP:[{KPD:"tree"},{NP:[{NMP:"ball"},{NMP:"bat"}]},{NP:[{NMP:"ground"},{NMP:"time"}]}]}]}];

var isNode = n => Array.isArray(n);
var isLeaf = n => !isNode(n);
var todoItem = parent => node => ({ parent, node });

var flatten = function(arr) {
  var result = [],
      todo = arr.map(todoItem(0)),
      current, node, parent, key, innerNode;

  while (todo.length) {
    ({node, parent} = todo.pop());
    key = result.length + 1;

    Object.keys(node).forEach(k => {
      innerNode = node[k];
      result.push({ key, parent, text: k });

      if (isLeaf(innerNode)) {
        result.push({ 
          key: key + 1,
          parent: key,
          text: innerNode
        });
      } else {
        todo = todo.concat(
          innerNode.map(todoItem(key)));
      }
    });
  };

  return result;
};

// Print output
console.log(
  flatten(tagData)
  .map(o => [
    "key: " + (o.key < 10 ? " " : "") + o.key,
    "parent: " + (o.parent < 10 ? " " : "") + o.parent,
    o.text
  ].join(" | "))
);

.as-console-wrapper {
  min-height: 100%;
}