74 lines
1.8 KiB
JavaScript
74 lines
1.8 KiB
JavaScript
// Tiny wrapper around function-red-black-tree that overrides the [inspect.custom] symbol so when we print it (during debugging) we just see the (key=>value)-pairs instead of the tree structure.
|
|
|
|
import createRBTree from "functional-red-black-tree";
|
|
import { inspect } from "node:util";
|
|
|
|
function defaultPrintf(depth, options, inspect) {
|
|
const entries = [];
|
|
this.tree.forEach((key, val) => { entries.push(`${inspect(key)} => ${inspect(val)}`); });
|
|
return `RBTree(${this.tree.length}) {${entries.join(', ')}}`;
|
|
}
|
|
|
|
export class RBTreeWrapper {
|
|
constructor(tree, printf = defaultPrintf) {
|
|
this.tree = tree;
|
|
this[inspect.custom] = printf;
|
|
}
|
|
|
|
static new(compareFn) {
|
|
return new RBTreeWrapper(createRBTree(compareFn))
|
|
}
|
|
|
|
// only for debugging:
|
|
keys() {
|
|
return this.tree.keys;
|
|
}
|
|
|
|
// only for debugging:
|
|
entries() {
|
|
return this.tree.keys.map(key => [key, this.tree.get(key)]);
|
|
}
|
|
}
|
|
|
|
// Can be used as drop-in replacement for Map
|
|
// Why create a mutable adapter for a purely-functional data structure?
|
|
// Because the builtin Map does not allow custom comparison functions and this one does.
|
|
export class MutableRBTree {
|
|
constructor(tree, printf = defaultPrintf) {
|
|
this.tree = tree;
|
|
this[inspect.custom] = printf;
|
|
}
|
|
|
|
static new(cmp) {
|
|
return new MutableRBTree(createRBTree(cmp));
|
|
}
|
|
|
|
set(key, value) {
|
|
this.tree = this.tree.remove(key).insert(key, value);
|
|
}
|
|
|
|
delete(key) {
|
|
this.tree = this.tree.remove(key);
|
|
}
|
|
|
|
get(key) {
|
|
return this.tree.get(key);
|
|
}
|
|
|
|
has(key) {
|
|
return this.tree.get(key) !== undefined;
|
|
}
|
|
|
|
clear() {
|
|
this.tree = createRBTree(this.tree._compare);
|
|
}
|
|
|
|
*[Symbol.iterator]() {
|
|
const iter = this.tree.begin;
|
|
while (iter !== undefined && iter.valid) {
|
|
yield [iter.key, iter.value];
|
|
iter.next();
|
|
}
|
|
}
|
|
}
|
|
|