Consider the following array of objects:
[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]
Some of the objects contain a ptr property, referencing the v property value of an object that it should directly preceed. Two objects will never attempt to directly preceed the same object, and there will never be a loop (e.g. a->b->c->a) in the array.
Therefore, here are two possible valid rearrangements of the objects:
[
{v: 'e'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'c', ptr: 'b'},
{v: 'b'},
]
[
{v: 'c', ptr: 'b'},
{v: 'b'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'e'}
]
It doesn't matter at all where objects appear in the output, if there is no ptr property referencing it. All that matters is that certain objects directly preceed others where the ptr property requests it.
What is a reasonably efficient algorithm to perform this kind of rearrangement?
Although the data is guaranteed to not contain loops, the rearrangement should be careful not to get into an infinite loop where it keeps rearranging the objects forever.
Note that although these examples use strings for v and ptr, the actual application will involve DOM elements as the values for v and ptr references. Therefore, the solution should only be able to compare v and ptr properties for equality.
Figure out which objects have another object pointing to them. Then, for each object that doesn't have another object pointing to it, add that object and everything in the following ptr chain to the output:
let val_to_obj = new Map();
let has_predecessor = new Set();
for (let obj of arr) {
val_to_obj.set(obj.v, obj);
if ('ptr' in obj) {
has_predecessor.add(obj.ptr);
}
}
let res = [];
for (let obj of arr) {
if (has_predecessor.has(obj.v)) {
continue;
}
while (obj !== undefined) {
res.push(obj);
obj = val_to_obj.get(obj.ptr);
}
}