I've written a function which takes input such as this:
lines: [
{ id: 1, name: "1" },
{ id: 2, name: "2" },
{ id: 9, superIds: [1, 2], name: "Shared…" },
{ id: 3, superIds: [2], name: "2.1" },
{ id: 4, superIds: [2], name: "2.2" },
{ id: 5, superIds: [3], name: "2.1.1" },
{ id: 6, superIds: [5], name: "2.1.1.1" },
{ id: 7, superIds: [4], name: "2.2.1" },
{ id: 8, superIds: [2], name: "2.3" },
{ id: 10, superIds: [9], name: "Shared.1" },
{ id: 11, superIds: [8], name: "2.3.1" }
]
And transforms it to output such as this:
1
Shared…
Shared.1
2
Shared… (ref)
2.1
2.1.1
2.1.1.1
2.2
2.2.1
2.3
2.3.1
The way that's done is this.
*recurse(superId, instanceSuperIds, level) {
for (const line of lines) { // `lines` is the input above
const index = (line.superIds || [undefined]).indexOf(superId);
const instanceSuperId = instanceSuperIds[line.id];
if (index !== -1) {
if (instanceSuperId ? superId === instanceSuperId : index === 0) {
yield { /*...*/line, level, isInstance: true };
yield *recurse(line.id, instanceSuperIds, level + 1);
} else {
yield { /*...*/line, level, isInstance: false };
}
}
}
}
const instanceSuperIds = [];
instanceSuperIds[9] = 1;
console.time();
for (const line of this.recurse(undefined, instanceSuperIds, 0)) {
console.debug(Array(line.level * 2).join(" "), line.line.name + (!line.isInstance && " (ref)" || ""));
}
console.timeEnd();
Right now this is 132 loop iterations. Of course this number won't get any smaller as the number of lines grows.
Is there an obvious optimalization I am missing? (This feels like basic CS will have answers, but I don't have basic CS.)