andlrc andlrc - 5 months ago 8
Javascript Question

Sorting array recursive

I have an array like this:

var a = [
{id: 1, pid: 0},
{id: 2, pid: 1},
{id: 3, pid: 1},
{id: 4, pid: 2},
{id: 5, pid: 2},
{id: 6, pid: 3},
{id: 7, pid: 3}
]


And a map object like this:

var map = {
"1": {id: 1, pid: 0},
"2": {id: 2, pid: 1},
"3": {id: 3, pid: 1},
"4": {id: 4, pid: 2},
"5": {id: 5, pid: 2},
"6": {id: 6, pid: 3},
"7": {id: 7, pid: 3}
}


I am trying to sort it to match this pattern:

var result = [
{"id": 1, "pid": 0},
{"id": 2, "pid": 1},
{"id": 4, "pid": 2},
{"id": 5, "pid": 2},
{"id": 3, "pid": 1},
{"id": 6, "pid": 3},
{"id": 7, "pid": 3}
]


As you can see this is a nested tree structure. And I want to get
pid
under the matching
id
and the lowest
id
at the top.

Is there any way to sort an array like this using only one iteration? - if not, it would be nice to see an example on how to get around it.

So far I only have:

a.sort(function(q, w) { return q.pid - w.pid; });


And I'm thinking of using my map to find my parent using
pid
->
id
and then sort on that key. It's okay to store extra properties on my objects as well.

Answer

Assuming that there is a single root with pid 0:

var children = {}
var root = null;
a.forEach(function(e) {
    children[e.id] = [];
});

a.forEach(function(e) {
    if (e.pid === 0) {
        root = e;
    }
    else {
        children[e.pid].push(e);
    }
});

var sorted = [];

function preorder(e) {
    sorted.push(e);
    if (children.hasOwnProperty(e.id)) {
        children[e.id].forEach(preorder);
    }
}
preorder(root);

Result:

[
  {"id":1,"pid":0},
    {"id":2,"pid":1},
    {"id":4,"pid":2},
      {"id":5,"pid":2},
    {"id":3,"pid":1},
      {"id":6,"pid":3},
      {"id":7,"pid":3}
]
Comments