5
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ You are not working on a tree, but on a directed acyclic graph. \$\endgroup\$ – dfhwze Jun 3 '19 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.