andlrc - 1 year ago 36

Javascript Question

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`

`id`

`id`

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`

Answer Source

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}
]
```