Javascript 2d to 3d object

Question

I have an array formatted like so:

[
  {
    "Level": "0",
    "Text": "My text 1",
  },
  {
    "Level": "1",
    "Text": "My text 2",
  },
  {
    "Level": "1",
    "Text": "My text 3",
  },
  {
    "Level": "2",
    "Text": "My text 4",
  },
  {
    "Level": "3",
    "Text": "My text 5",
  },
  {
    "Level": "1",
    "Text": "My text 6",
  },
  {
    "Level": "0",
    "Text": "My text 7",
  }
]

I want to convert it to be formatted like so:

[
  {
    "Text": "My text 1",
    "nodes": [
      {
        "Text": "My text 2",
      },
      {
        "Text": "My text 3",
        "nodes": [
          {
            "Text": "My text 4",
            "nodes": [
              {
                "Text": "My text 5",
              }
            ]
          }
        ]
      },
      {
        "Text": "My text 6",
      }
    ]
  },
  {
    "Text": "My text 7",
  }
]

It is fine if the "Level" key is not removed from each object. There could be 10s of thousands of objects in the array, so speed is important. I can't figure out a way to efficiently do this because the parent node needs to be tracked to know where to place the children. The "Level" key is guaranteed to be greater than or equal to 0. The "Level" key is also guaranteed to be a maximum of 1 higher than the "Level" key of the previous element in the array. In other words, 0 <= array[i].Level <= array[i+1].Level - 1. Thanks.

We can help to fix your code to do that, but we are not going to write the code for you. Maybe you need this first [Access / process (nested) objects, arrays or JSON](https://stackoverflow.com/questions/11922383/access-process-nested-objects-arrays-or-json). — Felix Kling, Jan 29 '16 at 16:15
I don't need the code. Just the logic. I can't think of a way that will work. I was originally planning to keep track of the previous node. If the current node is higher in level, append to "node". If the levels are the same, then push. But if the level is lower by more than 1, I don't know where to put it..... So this logic won't work. — Alec Fenichel, Jan 29 '16 at 16:21
For example, when I get to "My text 6". I wouldn't know where to place it because I don't know how many places back to go. — Alec Fenichel, Jan 29 '16 at 16:24
Then do not only keep track of the previous node but all ancestors. Keep a stack of nodes that represent ancestors. Then you can go back to any arbitrary ancestor and push to it. — Felix Kling, Jan 29 '16 at 16:26

score 0 · Answer 1 · answered Jan 29 '16 at 16:28

I just added the logic not tested. It may help you to extend your logic. Let me know if you need executable solution.

<script type="text\javascript">
var a=
[
  {
    "Level": "0",
    "Text": "My text 1",
  },
  {
    "Level": "1",
    "Text": "My text 2",
  },
  {
    "Level": "1",
    "Text": "My text 3",
  },
  {
    "Level": "2",
    "Text": "My text 4",
  },
  {
    "Level": "3",
    "Text": "My text 5",
  },
  {
    "Level": "1",
    "Text": "My text 6",
  },
  {
    "Level": "0",
    "Text": "My text 7",
  }
];

// first sort by level. I didn't include that code. Let me know if you want.

var newLevels=[];
var prevLevel="";
var newNode=null;


for(var index=0;index<a.length;index++)
{
    if(a[index].Level != prevLevel)
    {
        newNode = {Text : a[index].Text};

        newLevels.push(newNode);
    }
    else
    {
        newNode.nodes=[{Text: a[index].Text}];
    }

     prevLevel = a[index].Level;
}
</script>

I can't sort by level at the beginning because the order matters. Everything with level 3 does not belong together. It belongs under the last level 2 that came before it. — Alec Fenichel, Jan 29 '16 at 16:31

score 0 · Accepted Answer · answered Jan 29 '16 at 20:20

Felix Kling gave the idea.

function makeTable3D(oldTable) {
  var deferred  = q.defer();
  var parents = [];
  var table = [];

  for (var i = 0; i < oldTable.length; i++) {
    var level = parseInt(oldTable[i].Level) + 1;
    if (isNaN(level)) {
      continue;
    }

    if (parents.length < level) {
      parents.push(0);
    } else if (parents.length > level) {
      while (parents.length > level) {
        parents.pop();
      }
      parents.push(parents.pop() + 1);
    } else {
      parents.push(parents.pop() + 1);
    }

    var current = table;
    for (var j = 0; j < parents.length - 1; j++) {
      if (current[parents[j]].nodes) {
        current = current[parents[j]].nodes;
      } else {
        current = current[parents[j]];
        current.nodes = [];
        current = current.nodes;
      }
    }
    oldTable[i].Level = parseInt(oldTable[i].Level);
    current.push(oldTable[i]);
  }

  deferred.resolve(table);
  return deferred.promise;
}

score 0 · Answer 3 · answered Jan 29 '16 at 22:59

Essentially, all we need to do is to get the current level and add itself to its parent. The structure of the node is recursive:

{"Text": "some text", "nodes": []}

We can use a map, where key=Level and value=node to track the latest parent. To get parent, we simple use

map[level - 1]

We can use a dummy node to start as the parent and make its level -1. Code below:

function convert ( input )
{
    var obj = { "Text": "dummy" };

    var map = { "-1": obj };

    input.forEach(
        function ( i )
        {
            var level = parseInt( i.Level );
            var node = { "Text": i.Text };
            map[ level ] = node;
            if ( !("nodes" in map[ level - 1 ]) )
                map[ level - 1 ].nodes = [];
            map[ level - 1 ].nodes.push( node );
        }
    );
    return obj.nodes;
}

As this is one-pass, the time complexicty is O(n).

Javascript 2d to 3d object

3 Answers3