From 78ab026ffacbfd14992c2bfda1b9e290ace25cbf Mon Sep 17 00:00:00 2001 From: Terry Truong Date: Mon, 17 Oct 2022 22:01:28 +1100 Subject: Add rbtree.ts --- package.json | 1 + src/rbtree.ts | 398 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ vite.config.ts | 6 +- 3 files changed, 402 insertions(+), 3 deletions(-) create mode 100644 src/rbtree.ts diff --git a/package.json b/package.json index 00b3e1b..abcc393 100644 --- a/package.json +++ b/package.json @@ -12,6 +12,7 @@ "author": "Terry Truong", "license": "MIT", "dependencies": { + "bintrees": "^1.0.2", "pinia": "^2.0.22", "vue": "^3.2.37" }, diff --git a/src/rbtree.ts b/src/rbtree.ts new file mode 100644 index 0000000..b857086 --- /dev/null +++ b/src/rbtree.ts @@ -0,0 +1,398 @@ +// Copied from node_modules/bintrees/lib/, and adapted to use ES6, classes, and typescript + +class Node { + data: T; + left: Node | null; + right: Node | null; + red: boolean; + constructor(data: T){ + this.data = data; + this.left = null; + this.right = null; + this.red = true; + } + get_child(dir: boolean){ + return dir ? this.right : this.left; + } + set_child(dir: boolean, val: Node | null){ + if (dir) { + this.right = val; + } + else { + this.left = val; + } + } +} + +class Iterator { + _tree: RBTree; + _ancestors: Node[]; + _cursor: Node | null; + constructor(tree: RBTree){ + this._tree = tree; + this._ancestors = []; + this._cursor = null; + } + data(): T | null { + return this._cursor !== null ? this._cursor.data : null; + } + // if null-iterator, returns first node + // otherwise, returns next node + next(): T | null{ + if (this._cursor === null) { + let root = this._tree._root; + if (root !== null) { + this._minNode(root); + } + } + else { + if(this._cursor.right === null) { + // no greater node in subtree, go up to parent + // if coming from a right child, continue up the stack + let save; + do { + save = this._cursor; + if (this._ancestors.length) { + this._cursor = this._ancestors.pop()!; + } + else { + this._cursor = null; + break; + } + } while (this._cursor.right === save); + } + else { + // get the next node from the subtree + this._ancestors.push(this._cursor); + this._minNode(this._cursor.right); + } + } + return this._cursor !== null ? this._cursor.data : null; + }; + // if null-iterator, returns last node + // otherwise, returns previous node + prev(): T | null { + if(this._cursor === null) { + let root = this._tree._root; + if(root !== null) { + this._maxNode(root); + } + } + else { + if(this._cursor.left === null) { + let save; + do { + save = this._cursor; + if(this._ancestors.length) { + this._cursor = this._ancestors.pop()!; + } + else { + this._cursor = null; + break; + } + } while(this._cursor.left === save); + } + else { + this._ancestors.push(this._cursor); + this._maxNode(this._cursor.left); + } + } + return this._cursor !== null ? this._cursor.data : null; + }; + _minNode(start: Node) { + while(start.left !== null) { + this._ancestors.push(start); + start = start.left; + } + this._cursor = start; + }; + _maxNode(start: Node) { + while(start.right !== null) { + this._ancestors.push(start); + start = start.right; + } + this._cursor = start; + }; +} + +export class RBTree { + _root: Node | null; + size: number; + _comparator: (a: T, b: T) => number; + constructor(comparator: (a: T, b: T) => number){ + this._root = null; + this._comparator = comparator; + this.size = 0; + } + // removes all nodes from the tree + clear(){ + this._root = null; + this.size = 0; + } + // returns node data if found, null otherwise + find(data: T): T | null{ + let res = this._root; + while (res !== null) { + let c = this._comparator(data, res.data); + if(c === 0) { + return res.data; + } + else { + res = res.get_child(c > 0); + } + } + return null; + } + // returns iterator to node if found, null otherwise + findIter(data: T): Iterator | null { + let res = this._root; + let iter = this.iterator(); + while(res !== null) { + let c = this._comparator(data, res.data); + if(c === 0) { + iter._cursor = res; + return iter; + } + else { + iter._ancestors.push(res); + res = res.get_child(c > 0); + } + } + return null; + }; + // Returns an iterator to the tree node at or immediately after the item + lowerBound(item: T): Iterator { + let cur = this._root; + let iter = this.iterator(); + let cmp = this._comparator; + while(cur !== null) { + let c = cmp(item, cur.data); + if(c === 0) { + iter._cursor = cur; + return iter; + } + iter._ancestors.push(cur); + cur = cur.get_child(c > 0); + } + for(let i=iter._ancestors.length - 1; i >= 0; --i) { + cur = iter._ancestors[i]; + if(cmp(item, cur.data) < 0) { + iter._cursor = cur; + iter._ancestors.length = i; + return iter; + } + } + iter._ancestors.length = 0; + return iter; + }; + // Returns an iterator to the tree node immediately after the item + upperBound(item: T): Iterator { + let iter = this.lowerBound(item); + let cmp = this._comparator; + while(iter.data() !== null && cmp(iter.data()!, item) === 0) { + iter.next(); + } + return iter; + }; + // returns null if tree is empty + min(): T | null { + let res = this._root; + if(res === null) { + return null; + } + while(res.left !== null) { + res = res.left; + } + return res.data; + }; + // returns null if tree is empty + max(): T | null { + let res = this._root; + if(res === null) { + return null; + } + while(res.right !== null) { + res = res.right; + } + return res.data; + }; + // returns a null iterator + // call next() or prev() to point to an element + iterator() { + return new Iterator(this); + }; + // calls cb on each node's data, in order + each(cb: (x: T) => boolean) { + let it=this.iterator(), data; + while((data = it.next()) !== null) { + if(cb(data) === false) { + return; + } + } + }; + // calls cb on each node's data, in reverse order + reach(cb: (x: T) => boolean) { + var it=this.iterator(), data; + while((data = it.prev()) !== null) { + if(cb(data) === false) { + return; + } + } + }; + // returns true if inserted, false if duplicate + insert(data: T): boolean { + let ret = false; + if(this._root === null) { + // empty tree + this._root = new Node(data); + ret = true; + this.size++; + } + else { + let head = new Node(undefined) as Node; // fake tree root + let dir = false; + let last = false; + // setup + let gp: Node | null = null; // grandparent + let ggp = head; // grand-grand-parent + let p: Node | null = null; // parent + let node: Node | null = this._root; + ggp.right = this._root; + // search down + while(true) { + if(node === null) { + // insert new node at the bottom + node = new Node(data); + p!.set_child(dir, node); + ret = true; + this.size++; + } + else if(is_red(node.left) && is_red(node.right)) { + // color flip + node.red = true; + node.left!.red = false; + node.right!.red = false; + } + // fix red violation + if(is_red(node) && is_red(p)) { + let dir2 = ggp.right === gp; + if(node === p!.get_child(last)) { + ggp.set_child(dir2, single_rotate(gp!, !last)); + } + else { + ggp.set_child(dir2, double_rotate(gp!, !last)); + } + } + let cmp = this._comparator(node.data, data); + // stop if found + if(cmp === 0) { + break; + } + last = dir; + dir = cmp < 0; + // update helpers + if(gp !== null) { + ggp = gp; + } + gp = p; + p = node; + node = node.get_child(dir); + } + // update root + this._root = head.right; + } + // make root black + this._root!.red = false; + return ret; + }; + // returns true if removed, false if not found + remove(data: T): boolean { + if(this._root === null) { + return false; + } + let head = new Node(undefined) as Node; // fake tree root + let node = head; + node.right = this._root; + let p: Node | null = null; // parent + let gp: Node | null = null; // grand parent + let found: Node | null = null; // found item + let dir = true; + while(node.get_child(dir) !== null) { + let last = dir; + // update helpers + gp = p; + p = node; + node = node.get_child(dir)!; + let cmp = this._comparator(data, node.data); + dir = cmp > 0; + // save found node + if (cmp === 0) { + found = node; + } + // push the red node down + if (!is_red(node) && !is_red(node.get_child(dir))) { + if(is_red(node.get_child(!dir))) { + let sr = single_rotate(node, dir); + p.set_child(last, sr); + p = sr; + } + else if(!is_red(node.get_child(!dir))) { + let sibling = p.get_child(!last); + if(sibling !== null) { + if(!is_red(sibling.get_child(!last)) && !is_red(sibling.get_child(last))) { + // color flip + p.red = false; + sibling.red = true; + node.red = true; + } + else { + let dir2 = gp!.right === p; + if(is_red(sibling.get_child(last))) { + gp!.set_child(dir2, double_rotate(p, last)); + } + else if(is_red(sibling.get_child(!last))) { + gp!.set_child(dir2, single_rotate(p, last)); + } + // ensure correct coloring + let gpc = gp!.get_child(dir2)!; + gpc.red = true; + node.red = true; + gpc.left!.red = false; + gpc.right!.red = false; + } + } + } + } + } + // replace and remove if found + if (found !== null) { + found.data = node.data; + p!.set_child(p!.right === node, node.get_child(node.left === null)); + this.size--; + } + // update root and make it black + this._root = head.right; + if(this._root !== null) { + this._root.red = false; + } + return found !== null; + }; +} + +function is_red(node: Node | null): boolean { + return node !== null && node.red; +} + +function single_rotate(root: Node, dir: boolean): Node { + let save = root.get_child(!dir)!; + root.set_child(!dir, save.get_child(dir)); + save.set_child(dir, root); + root.red = true; + save.red = false; + return save; +} + +function double_rotate(root: Node, dir: boolean): Node { + root.set_child(!dir, single_rotate(root.get_child(!dir)!, !dir)); + return single_rotate(root, dir); +} diff --git a/vite.config.ts b/vite.config.ts index 895d557..6baaeb0 100644 --- a/vite.config.ts +++ b/vite.config.ts @@ -7,9 +7,9 @@ export default defineConfig({ base: '/', server: { proxy: {'/data': 'http://localhost:8000', '/hist_data': 'http://localhost:8000'}, - watch: { - ignored: ['**/backend', '**/public'], - }, + watch: { + ignored: ['**/backend', '**/public'], + }, }, build: { sourcemap: true, -- cgit v1.2.3