I need to write a function that sorts this array based on dialog_node key and previous_sibling keys. The previous_sibling of the next object matches the dialog_node value of the previous object in the array. I don't need to keep the same logic in the function, this is just what I tried for sorting. The first item that should be at top of the list won't necessarily be at the beginning of the array.
export function orderDialogNodes(nodes) {
// Create a mapping of dialog_node to its corresponding index in the array
const nodeIndexMap = {};
nodes.forEach((node, index) => {
nodeIndexMap[node.dialog_node] = index;
});
// Sort the array based on the previous_sibling property
nodes.sort((a, b) => {
const indexA = nodeIndexMap[a.previous_sibling];
const indexB = nodeIndexMap[b.previous_sibling];
return indexA - indexB;
});
return nodes;
}
const inputArray = [
{
type: "folder",
title: "Q&A Total Rewards",
dialog_node: "node_2_1702794723026",
previous_sibling: "node_1_1702793119621",
},
{
type: "folder",
title: "Q&A Payroll Taxes",
dialog_node: "node_3_1702794877277",
previous_sibling: "node_2_1702794723026",
},
{
type: "folder",
title: "Q&A Contacts",
dialog_node: "node_1_1702793119621",
previous_sibling: "node_10_1704313850082",
},
{
type: "folder",
title: "Feedback Capture Flow",
dialog_node: "node_3_1702952290373",
previous_sibling: "node_76_7439096406",
},
{
type: "folder",
title: "Q&A Benefits",
dialog_node: "node_33_6664725040",
previous_sibling: "node_3_1702794877277",
},
{
type: "folder",
title: "Q&A Perf Mgmt",
dialog_node: "node_54_3521545375",
previous_sibling: "node_33_6664725040",
},
{
type: "folder",
title: "Q&A Workday How To",
dialog_node: "node_7_1702794820202",
previous_sibling: "node_54_3521545375",
},
{
type: "folder",
title: "Q&A Learning",
dialog_node: "node_7_1702794902054",
previous_sibling: "node_7_1702794820202",
},
{
type: "folder",
title: "Q&A Levels",
dialog_node: "node_76_7439096406",
previous_sibling: "node_9_1702956631016",
},
{
type: "folder",
title: "Q&A Promo",
dialog_node: "node_9_1702956631016",
previous_sibling: "node_7_1702794902054",
},
];
const orderedArray = orderDialogNodes(inputArray);
console.log(orderedArray);
I think you can't use Array::sort() here, since you can't directly compare non-siblings and the sort algorithm sometimes ask to compare non-siblings. The indices in the original array are also useless since they can be random.
So a more natural way would be a build a linked list and then convert it to an array:
const list = {};
inputArray.forEach(item => {
(list[item.dialog_node] ??= {}).item = item;
const prev = list[item.previous_sibling];
if(!prev){
list[item.previous_sibling] = {next:list[item.dialog_node]};
} else {
prev.next = list[item.dialog_node];
}
});
let head = Object.values(list).find(item => !item.item);
const result = [];
while(head = head.next) result.push(head.item);
console.log(result);<script>
const inputArray=[{type:"folder",title:"Q&A Total Rewards",dialog_node:"node_2_1702794723026",previous_sibling:"node_1_1702793119621"},{type:"folder",title:"Q&A Payroll Taxes",dialog_node:"node_3_1702794877277",previous_sibling:"node_2_1702794723026"},{type:"folder",title:"Q&A Contacts",dialog_node:"node_1_1702793119621",previous_sibling:"node_10_1704313850082"},{type:"folder",title:"Feedback Capture Flow",dialog_node:"node_3_1702952290373",previous_sibling:"node_76_7439096406"},{type:"folder",title:"Q&A Benefits",dialog_node:"node_33_6664725040",previous_sibling:"node_3_1702794877277"},{type:"folder",title:"Q&A Perf Mgmt",dialog_node:"node_54_3521545375",previous_sibling:"node_33_6664725040"},{type:"folder",title:"Q&A Workday How To",dialog_node:"node_7_1702794820202",previous_sibling:"node_54_3521545375"},{type:"folder",title:"Q&A Learning",dialog_node:"node_7_1702794902054",previous_sibling:"node_7_1702794820202"},{type:"folder",title:"Q&A Snap Levels",dialog_node:"node_76_7439096406",previous_sibling:"node_9_1702956631016"},{type:"folder",title:"Q&A Promo",dialog_node:"node_9_1702956631016",previous_sibling:"node_7_1702794902054"},];
</script>UPDATE Initially I was intended to keep track of the list's head, but failed, so I find it after building a list. So now I've added tracking of all possible heads and find the head in this head list.
I've optimized the original to match the new version so no Object.values() is used to avoid an intermediate array. So keeping track of heads is noticeably faster. I've also tried a 2-way linked list, but the speed the same as with the tracking heads regardless of the input's size (which is strange, because time complexity is different).
` Chrome/121
-------------------------------------------------------
track heads 1.00x | x10000 396 401 403 413 427
find head 1.67x | x10000 660 667 682 690 702
-------------------------------------------------------
https://github.com/silentmantra/benchmark `
const inputArray=[];
let count = 1000;
let prev;
while(count--){
const id = 'node_' + Math.random().toString().slice(2);
prev = inputArray[inputArray.length] = {dialog_node:id, previous_sibling: prev?.dialog_node};
}
// @benchmark find head
{
const list = {};
inputArray.forEach(item => {
const node = list[item.dialog_node] ??= {};
node.item = item;
(list[item.previous_sibling] ??= {}).next = node;
});
let head;
for(const k in list){
if(!list[k].item){
head = list[k];
break;
}
}
const result = [];
while(head = head.next) result.push(head.item);
result;
}
// @benchmark track heads
{
const list = {}, heads = [];
inputArray.forEach(item => {
const node = list[item.dialog_node] ??= {};
node.item = item;
(list[item.previous_sibling] ??= heads[heads.length] = {}).next = node;
});
let head = heads.find(item => !item.item);
const result = [];
while(head = head.next) result.push(head.item);
result;
}
/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));