Allow to store references and eventually delete them

Question

Allow to store references and eventually delete them

make-github-pseudonymous-again opened this issue 4 years ago · 3 comments

make-github-pseudonymous-again commented 4 years ago

const node = tree.add(x);
...
tree.unlink(node);

This is currently not possible because, among other potential problems, rotations swap keys of references to save operations.

Answer 1 · 2021-03-31T17:56:50.000Z

According to the command rg '\.key.*=.*\.key', the only other place where this happens is in RedBlackTree#_delete.

Answer 2 · 2021-04-01T09:10:58.000Z

Note that this requires keeping track of the RedBlackTree#root in all these operations.

Answer 3 · 2021-04-05T19:26:42.000Z

PS: We could have used a WeakMap to point to the current node even though keys have been swapped. But this could lead to a two-fold increase of space usage because it prevents garbage collection of unlinked nodes whose keys has been swapped at some point.