Sorting a multi-dimensional object with hierarchical groups in Javascript (Node.js)
Problem
I have an hierarchical Object on which I sort children by walking over the parents and sort the children. This works. But now, I need to optionally break the hierarchy and create new virtual restraints.
In order to illustrate this, let's take an example of a Man, who has x Wifes. With each wife, he has y Kids. I can sort kids per wife, or wifes per man.
Man01 Wife01a Kid01aA
Kid01aB
Wife01b Kid01bC
Kid01bD
Man02 Wife02c Kid02cE
Kid02cF
Wife02d Kid02dG
Kid02dH
Let's just give them names:
Murphy Winnie Kurt
Kara
Wendy Klaus
Klea
Marley Wonda Kasper
Kyra
Wilma Kevin
Karla
And think about sorting them alphabetically within their parents:
Marley Wilma Karla
Kevin
Wonda Kasper
Kyra
Murphy Wendy Klaus
Klea
Winnie Kara
Kurt
But now, we want to be able to sort the kids that belong to a man, or wifes in general, or kids in general?
Marley Wilma Karla
Wonda Kasper
Wilma Kevin
Wonda Kyra
Murphy Winnie Kara
Wendy Klaus
Wendy Klea
Winnie Kurt
This is an immensly simplified fictional object. In reality, in stead of sorting alphabetically, I do a multi-column-sort over many many properties.
It's fine to output the results to a table, but processing itself already takes a lot of time and memory. I don't want to complicate that further.
If that was no issue, I would just flatten the object as a table in an array, chain every multi-column sort into a super multi-column sort, and regroup starting at the closest common ancestor that was left intact with loops.
But I am trying to solve this in a more efficient way, without converting the object to a full-blown table-array.
- How do I tacle this?
actually looping over each and every one of them twice?
- Perhaps there is a 'well-known' solution for this kind of sorting that I just don't know about yet?
- Maybe there is wizardry available creating table-like records using references for all 'virtual' parents, grouping these references back into hierarchy afterwards without looping over them?
Here's an example of the kind of Object I am referring to:
By Object
, I mean, quite literally {}
, although the object contains arrays []
of objects {}
when it has multiple members.
{
"men" : [
{
"name" : "Murphy",
// a lot of properties
"wifes" : [
{
"name" : "Winnie",
// a lot of properties
"kids" : [
{
"name" : "Kurt",
// a lot of properties
}, {}, {} // etc...
]
}, {}, {} // etc...
]
}, {}, {} // etc...
]
}
Note that in this case my example is wrong, because Man, Wife and Kid are all humans. But in reality there are different object with dissimilar properties. I should have chosen Universe, Planet, Soil or something, assuming there are multiple universes. ;)
Solution
we want to be able to sort the kids that belong to a man
Then I would arrange them like this:
Marley Karla Wilma
Kasper Wonda
Kevin Wilma
Kyra Wonda
Murphy Kara Winnie
Klaus Wendy
Klea Wendy
Kurt Winnie
Of course, since there is only one mother per child there is no much difference, but for your actual data this might be different.
Yet, you can already see now that you just have to sort each of the kids
arrays per man.
So, in general, instead of flattening to a large table array, multi-column sorting that, and regrouping the results as you suggested, you should do the grouping first and sort the groups afterwards - a bit like a bucket sort.
var men = data["men"];
men.forEach(function (man) {
var kids = {};
var wifes = man["wifes"];
for (var i=0; i
// });
// you might integrate this loop in the above, but it's independent:
man["kids"].forEach(function(kid) {
kid["mothers"].sort( /* some mother comparison */ );
})
});
// now every man has a sorted "kids" array with each kid having a sorted "mothers" array
Discussion
View additional discussion.