New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
@flatten-js/interval-tree
Advanced tools
@flatten-js/interval-tree - npm Package Compare versions
Comparing version 1.1.2 to 1.1.3
@@ -14,3 +14,3 @@ (function (global, factory) { | ||
| * *equal*, *less* and method *max(p1, p1)* that returns maximum in a pair. | ||
| * When interval is an object rather than pair of numbers, this object should have properties *low*, *high*, *max* | ||
| * When interval is an object rather than a pair of numbers, this object should have properties *low*, *high*, *max* | ||
| * and implement methods *less_than(), equal_to(), intersect(), not_intersect(), clone(), output()*. | ||
@@ -61,3 +61,3 @@ * Two static methods *comparable_max(), comparable_less_than()* define how to compare values in pair. <br/> | ||
| return this.low < other_interval.low || | ||
| this.low == other_interval.low && this.high < other_interval.high; | ||
| this.low === other_interval.low && this.high < other_interval.high; | ||
| } | ||
@@ -71,3 +71,3 @@ | ||
| equal_to(other_interval) { | ||
| return this.low == other_interval.low && this.high == other_interval.high; | ||
| return this.low === other_interval.low && this.high === other_interval.high; | ||
| } | ||
@@ -95,3 +95,3 @@ | ||
| * Returns new interval merged with other interval | ||
| * @param {Interval} interval - Other interval to merge with | ||
| * @param {Interval} other_interval - Other interval to merge with | ||
| * @returns {Interval} | ||
@@ -101,4 +101,6 @@ */ | ||
| return new Interval( | ||
| this.low === undefined ? other_interval.low : Math.min(this.low, other_interval.low), | ||
| this.high === undefined ? other_interval.high : Math.max(this.high, other_interval.high) | ||
| this.low === undefined ? | ||
| other_interval.low : (this.low < other_interval.low ? this.low : other_interval.low), | ||
| this.high === undefined ? | ||
| other_interval.high : (this.high > other_interval.high ? this.high : other_interval.high) | ||
| ); | ||
@@ -164,5 +166,7 @@ } | ||
| /* If not, this should by an array of two numbers */ | ||
| if (key && key instanceof Array && key.length == 2) { | ||
| if (key && key instanceof Array && key.length === 2) { | ||
| if (!Number.isNaN(key[0]) && !Number.isNaN(key[1])) { | ||
| this.item.key = new Interval(Math.min(key[0], key[1]), Math.max(key[0], key[1])); | ||
| let [low, high] = key; | ||
| if (low > high) [low, high] = [high, low]; | ||
| this.item.key = new Interval(low, high); | ||
| } | ||
@@ -199,3 +203,3 @@ } | ||
| this.item.value.equal_to(other_node.item.value) : | ||
| this.item.value == other_node.item.value; | ||
| this.item.value === other_node.item.value; | ||
| } | ||
@@ -320,3 +324,3 @@ equal_to(other_node) { | ||
| isEmpty() { | ||
| return (this.root == null || this.root == this.nil_node); | ||
| return (this.root == null || this.root === this.nil_node); | ||
| } | ||
@@ -353,3 +357,3 @@ | ||
| let search_node = new Node(key, value); | ||
| return this.tree_search(this.root, search_node) ? true : false; | ||
| return !!this.tree_search(this.root, search_node); | ||
| } | ||
@@ -393,4 +397,3 @@ | ||
| let search_node = new Node(interval); | ||
| let found = this.tree_find_any_interval(this.root, search_node); | ||
| return found; | ||
| return this.tree_find_any_interval(this.root, search_node); | ||
| } | ||
@@ -447,7 +450,7 @@ | ||
| if (this.root == null || this.root == this.nil_node) { | ||
| if (this.root == null || this.root === this.nil_node) { | ||
| this.root = insert_node; | ||
| } | ||
| else { | ||
| while (current_node != this.nil_node) { | ||
| while (current_node !== this.nil_node) { | ||
| parent_node = current_node; | ||
@@ -482,6 +485,6 @@ if (insert_node.less_than(current_node)) { | ||
| current_node = insert_node; | ||
| while (current_node != this.root && current_node.parent.color == RB_TREE_COLOR_RED) { | ||
| if (current_node.parent == current_node.parent.parent.left) { // parent is left child of grandfather | ||
| while (current_node !== this.root && current_node.parent.color === RB_TREE_COLOR_RED) { | ||
| if (current_node.parent === current_node.parent.parent.left) { // parent is left child of grandfather | ||
| uncle_node = current_node.parent.parent.right; // right brother of parent | ||
| if (uncle_node.color == RB_TREE_COLOR_RED) { // Case 1. Uncle is red | ||
| if (uncle_node.color === RB_TREE_COLOR_RED) { // Case 1. Uncle is red | ||
| // re-color father and uncle into black | ||
@@ -494,3 +497,3 @@ current_node.parent.color = RB_TREE_COLOR_BLACK; | ||
| else { // Case 2 & 3. Uncle is black | ||
| if (current_node == current_node.parent.right) { // Case 2. Current if right child | ||
| if (current_node === current_node.parent.right) { // Case 2. Current if right child | ||
| // This case is transformed into Case 3. | ||
@@ -508,3 +511,3 @@ current_node = current_node.parent; | ||
| uncle_node = current_node.parent.parent.left; // left brother of parent | ||
| if (uncle_node.color == RB_TREE_COLOR_RED) { // Case 4. Uncle is red | ||
| if (uncle_node.color === RB_TREE_COLOR_RED) { // Case 4. Uncle is red | ||
| // re-color father and uncle into black | ||
@@ -517,3 +520,3 @@ current_node.parent.color = RB_TREE_COLOR_BLACK; | ||
| else { | ||
| if (current_node == current_node.parent.left) { // Case 5. Current is left child | ||
| if (current_node === current_node.parent.left) { // Case 5. Current is left child | ||
| // Transform into case 6 | ||
@@ -538,3 +541,3 @@ current_node = current_node.parent; | ||
| if (delete_node.left == this.nil_node || delete_node.right == this.nil_node) { // delete_node has less then 2 children | ||
| if (delete_node.left === this.nil_node || delete_node.right === this.nil_node) { // delete_node has less then 2 children | ||
| cut_node = delete_node; | ||
@@ -547,3 +550,3 @@ } | ||
| // fix_node if single child of cut_node | ||
| if (cut_node.left != this.nil_node) { | ||
| if (cut_node.left !== this.nil_node) { | ||
| fix_node = cut_node.left; | ||
@@ -560,7 +563,7 @@ } | ||
| if (cut_node == this.root) { | ||
| if (cut_node === this.root) { | ||
| this.root = fix_node; | ||
| } | ||
| else { | ||
| if (cut_node == cut_node.parent.left) { | ||
| if (cut_node === cut_node.parent.left) { | ||
| cut_node.parent.left = fix_node; | ||
@@ -579,3 +582,3 @@ } | ||
| // to node in outer structure and we will have to delete by key, additional search need | ||
| if (cut_node != delete_node) { | ||
| if (cut_node !== delete_node) { | ||
| delete_node.copy_data(cut_node); | ||
@@ -586,3 +589,3 @@ delete_node.update_max(); // update max property of the cut node at the new place | ||
| if (/*fix_node != this.nil_node && */cut_node.color == RB_TREE_COLOR_BLACK) { | ||
| if (/*fix_node != this.nil_node && */cut_node.color === RB_TREE_COLOR_BLACK) { | ||
| this.delete_fixup(fix_node); | ||
@@ -596,6 +599,6 @@ } | ||
| while (current_node != this.root && current_node.parent != null && current_node.color == RB_TREE_COLOR_BLACK) { | ||
| if (current_node == current_node.parent.left) { // fix node is left child | ||
| while (current_node !== this.root && current_node.parent != null && current_node.color === RB_TREE_COLOR_BLACK) { | ||
| if (current_node === current_node.parent.left) { // fix node is left child | ||
| brother_node = current_node.parent.right; | ||
| if (brother_node.color == RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| if (brother_node.color === RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| brother_node.color = RB_TREE_COLOR_BLACK; // re-color brother | ||
@@ -607,4 +610,4 @@ current_node.parent.color = RB_TREE_COLOR_RED; // re-color father | ||
| // Derive to cases 2..4: brother is black | ||
| if (brother_node.left.color == RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color == RB_TREE_COLOR_BLACK) { // case 2: both nephews black | ||
| if (brother_node.left.color === RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color === RB_TREE_COLOR_BLACK) { // case 2: both nephews black | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -614,3 +617,3 @@ current_node = current_node.parent; // continue iteration | ||
| else { | ||
| if (brother_node.right.color == RB_TREE_COLOR_BLACK) { // case 3: left nephew red, right nephew black | ||
| if (brother_node.right.color === RB_TREE_COLOR_BLACK) { // case 3: left nephew red, right nephew black | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -632,3 +635,3 @@ brother_node.left.color = RB_TREE_COLOR_BLACK; // re-color nephew | ||
| brother_node = current_node.parent.left; | ||
| if (brother_node.color == RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| if (brother_node.color === RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| brother_node.color = RB_TREE_COLOR_BLACK; // re-color brother | ||
@@ -640,4 +643,4 @@ current_node.parent.color = RB_TREE_COLOR_RED; // re-color father | ||
| // Go to cases 2..4 | ||
| if (brother_node.left.color == RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color == RB_TREE_COLOR_BLACK) { // case 2 | ||
| if (brother_node.left.color === RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color === RB_TREE_COLOR_BLACK) { // case 2 | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -647,3 +650,3 @@ current_node = current_node.parent; // continue iteration | ||
| else { | ||
| if (brother_node.left.color == RB_TREE_COLOR_BLACK) { // case 3: right nephew red, left nephew black | ||
| if (brother_node.left.color === RB_TREE_COLOR_BLACK) { // case 3: right nephew red, left nephew black | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -669,3 +672,3 @@ brother_node.right.color = RB_TREE_COLOR_BLACK; // re-color nephew | ||
| tree_search(node, search_node) { | ||
| if (node == null || node == this.nil_node) | ||
| if (node == null || node === this.nil_node) | ||
| return undefined; | ||
@@ -687,3 +690,3 @@ | ||
| let curr = node; | ||
| while (curr && curr != this.nil_node) { | ||
| while (curr && curr !== this.nil_node) { | ||
| if (curr.less_than(search_node)) { | ||
@@ -707,5 +710,5 @@ if (curr.intersect(search_node)) { | ||
| tree_search_interval(node, search_node, res) { | ||
| if (node != null && node != this.nil_node) { | ||
| if (node != null && node !== this.nil_node) { | ||
| // if (node->left != this.nil_node && node->left->max >= low) { | ||
| if (node.left != this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| if (node.left !== this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| this.tree_search_interval(node.left, search_node, res); | ||
@@ -718,3 +721,3 @@ } | ||
| // if (node->right != this.nil_node && node->low <= high) { | ||
| if (node.right != this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| if (node.right !== this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| this.tree_search_interval(node.right, search_node, res); | ||
@@ -727,13 +730,10 @@ } | ||
| let found = false; | ||
| if (node != null && node != this.nil_node) { | ||
| // if (node->left != this.nil_node && node->left->max >= low) { | ||
| if (node.left != this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| if (node != null && node !== this.nil_node) { | ||
| if (node.left !== this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| found = this.tree_find_any_interval(node.left, search_node); | ||
| } | ||
| // if (low <= node->high && node->low <= high) { | ||
| if (!found) { | ||
| found = node.intersect(search_node); | ||
| } | ||
| // if (node->right != this.nil_node && node->low <= high) { | ||
| if (!found && node.right != this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| if (!found && node.right !== this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| found = this.tree_find_any_interval(node.right, search_node); | ||
@@ -747,3 +747,3 @@ } | ||
| let node_min = node; | ||
| while (node_min.left != null && node_min.left != this.nil_node) { | ||
| while (node_min.left != null && node_min.left !== this.nil_node) { | ||
| node_min = node_min.left; | ||
@@ -757,3 +757,3 @@ } | ||
| let node_max = node; | ||
| while (node_max.right != null && node_max.right != this.nil_node) { | ||
| while (node_max.right != null && node_max.right !== this.nil_node) { | ||
| node_max = node_max.right; | ||
@@ -769,3 +769,3 @@ } | ||
| if (node.right != this.nil_node) { | ||
| if (node.right !== this.nil_node) { | ||
| node_successor = this.local_minimum(node.right); | ||
@@ -776,3 +776,3 @@ } | ||
| parent_node = node.parent; | ||
| while (parent_node != null && parent_node.right == current_node) { | ||
| while (parent_node != null && parent_node.right === current_node) { | ||
| current_node = parent_node; | ||
@@ -798,3 +798,3 @@ parent_node = parent_node.parent; | ||
| if (y.left != this.nil_node) { | ||
| if (y.left !== this.nil_node) { | ||
| y.left.parent = x; // x becomes parent of b | ||
@@ -804,7 +804,7 @@ } | ||
| if (x == this.root) { | ||
| if (x === this.root) { | ||
| this.root = y; // y becomes root | ||
| } | ||
| else { // y becomes child of x.parent | ||
| if (x == x.parent.left) { | ||
| if (x === x.parent.left) { | ||
| x.parent.left = y; | ||
@@ -819,3 +819,3 @@ } | ||
| if (x != null && x != this.nil_node) { | ||
| if (x != null && x !== this.nil_node) { | ||
| x.update_max(); | ||
@@ -825,3 +825,3 @@ } | ||
| y = x.parent; | ||
| if (y != null && y != this.nil_node) { | ||
| if (y != null && y !== this.nil_node) { | ||
| y.update_max(); | ||
@@ -836,3 +836,3 @@ } | ||
| if (x.right != this.nil_node) { | ||
| if (x.right !== this.nil_node) { | ||
| x.right.parent = y; // y becomes parent of b | ||
@@ -842,7 +842,7 @@ } | ||
| if (y == this.root) { // x becomes root | ||
| if (y === this.root) { // x becomes root | ||
| this.root = x; | ||
| } | ||
| else { // y becomes child of x.parent | ||
| if (y == y.parent.left) { | ||
| if (y === y.parent.left) { | ||
| y.parent.left = x; | ||
@@ -857,3 +857,3 @@ } | ||
| if (y != null && y != this.nil_node) { | ||
| if (y !== null && y !== this.nil_node) { | ||
| y.update_max(); | ||
@@ -863,3 +863,3 @@ } | ||
| x = y.parent; | ||
| if (x != null && x != this.nil_node) { | ||
| if (x != null && x !== this.nil_node) { | ||
| x.update_max(); | ||
@@ -870,3 +870,3 @@ } | ||
| tree_walk(node, action) { | ||
| if (node != null && node != this.nil_node) { | ||
| if (node != null && node !== this.nil_node) { | ||
| this.tree_walk(node.left, action); | ||
@@ -883,4 +883,4 @@ // arr.push(node.toArray()); | ||
| this.tree_walk(this.root, function (node) { | ||
| if (node.color == RB_TREE_COLOR_RED) { | ||
| if (!(node.left.color == RB_TREE_COLOR_BLACK && node.right.color == RB_TREE_COLOR_BLACK)) { | ||
| if (node.color === RB_TREE_COLOR_RED) { | ||
| if (!(node.left.color === RB_TREE_COLOR_BLACK && node.right.color === RB_TREE_COLOR_BLACK)) { | ||
| res = false; | ||
@@ -898,6 +898,6 @@ } | ||
| let heightRight = 0; | ||
| if (node.color == RB_TREE_COLOR_BLACK) { | ||
| if (node.color === RB_TREE_COLOR_BLACK) { | ||
| height++; | ||
| } | ||
| if (node.left != this.nil_node) { | ||
| if (node.left !== this.nil_node) { | ||
| heightLeft = this.testBlackHeightProperty(node.left); | ||
@@ -908,3 +908,3 @@ } | ||
| } | ||
| if (node.right != this.nil_node) { | ||
| if (node.right !== this.nil_node) { | ||
| heightRight = this.testBlackHeightProperty(node.right); | ||
@@ -915,3 +915,3 @@ } | ||
| } | ||
| if (heightLeft != heightRight) { | ||
| if (heightLeft !== heightRight) { | ||
| throw new Error('Red-black height property violated'); | ||
@@ -918,0 +918,0 @@ } |
| { | ||
| "name": "@flatten-js/interval-tree", | ||
| "version": "1.1.2", | ||
| "version": "1.1.3", | ||
| "description": "Interval search tree", | ||
@@ -5,0 +5,0 @@ "author": "Alex Bol", |
@@ -31,9 +31,5 @@ # Interval Tree | ||
| Tree stores pairs ```<key,value>``` where key is an interval, and value is an object of any type. | ||
| If value omitted, tree stores only keys. | ||
| In a ```<key,value>``` tree none of the ```value``` can be | ||
| ```undefined```. | ||
| If value omitted, tree stores only keys. ```value``` cannot be ```undefined```. | ||
| Interval can be simply a pair of numbers or it can be | ||
| a user-defined object that implements ```IntervalInterface``` described in | ||
| Interval can be a pair of numbers or an object that implements ```IntervalInterface``` described in | ||
| typescript declaration file ```index.d.ts```. | ||
@@ -43,4 +39,5 @@ | ||
| We may look at rectangle as an interval between its low left and top right corners. | ||
| See **Box** class in [flatten-js](https://github.com/alexbol99/flatten-js) library as an example | ||
| of ```IntervalInterface``` implementation. | ||
| It makes possible to use interval tree in spatial queries. | ||
| See **Box** class in [flatten-js](https://github.com/alexbol99/flatten-js) library for such | ||
| implementation. | ||
@@ -82,3 +79,3 @@ ### Example | ||
| Method returns true if item {key, value} exists in the tree. <br/> | ||
| Method may be useful if need to support unique items. | ||
| ```javascript | ||
@@ -89,3 +86,3 @@ let exist = tree.exist(key, value) | ||
| ### Remove(key, value) | ||
| Removes item from the tree. Returns true if item was actually deleted, false if not found | ||
| Removes item from the tree. Returns true if item was found and deleted, false if not found | ||
| ```javascript | ||
@@ -130,3 +127,3 @@ let removed = tree.remove(key, value) | ||
| ### Intersect_any(interval) | ||
| Returns true if intersection between given and any interval stored in the tree found | ||
| Returns true if intersection found between given interval and any of intervals stored in the tree | ||
@@ -133,0 +130,0 @@ ```javascript |
@@ -8,3 +8,3 @@ /** | ||
| * *equal*, *less* and method *max(p1, p1)* that returns maximum in a pair. | ||
| * When interval is an object rather than pair of numbers, this object should have properties *low*, *high*, *max* | ||
| * When interval is an object rather than a pair of numbers, this object should have properties *low*, *high*, *max* | ||
| * and implement methods *less_than(), equal_to(), intersect(), not_intersect(), clone(), output()*. | ||
@@ -55,3 +55,3 @@ * Two static methods *comparable_max(), comparable_less_than()* define how to compare values in pair. <br/> | ||
| return this.low < other_interval.low || | ||
| this.low == other_interval.low && this.high < other_interval.high; | ||
| this.low === other_interval.low && this.high < other_interval.high; | ||
| } | ||
@@ -65,3 +65,3 @@ | ||
| equal_to(other_interval) { | ||
| return this.low == other_interval.low && this.high == other_interval.high; | ||
| return this.low === other_interval.low && this.high === other_interval.high; | ||
| } | ||
@@ -89,3 +89,3 @@ | ||
| * Returns new interval merged with other interval | ||
| * @param {Interval} interval - Other interval to merge with | ||
| * @param {Interval} other_interval - Other interval to merge with | ||
| * @returns {Interval} | ||
@@ -95,4 +95,6 @@ */ | ||
| return new Interval( | ||
| this.low === undefined ? other_interval.low : Math.min(this.low, other_interval.low), | ||
| this.high === undefined ? other_interval.high : Math.max(this.high, other_interval.high) | ||
| this.low === undefined ? | ||
| other_interval.low : (this.low < other_interval.low ? this.low : other_interval.low), | ||
| this.high === undefined ? | ||
| other_interval.high : (this.high > other_interval.high ? this.high : other_interval.high) | ||
| ); | ||
@@ -99,0 +101,0 @@ } |
@@ -7,3 +7,3 @@ /** | ||
| import Node from './node.js'; | ||
| import {RB_TREE_COLOR_RED, RB_TREE_COLOR_BLACK} from '../utils/constants.js'; | ||
| import {RB_TREE_COLOR_BLACK, RB_TREE_COLOR_RED} from '../utils/constants.js'; | ||
@@ -77,3 +77,3 @@ // const nil_node = new Node(); | ||
| isEmpty() { | ||
| return (this.root == null || this.root == this.nil_node); | ||
| return (this.root == null || this.root === this.nil_node); | ||
| } | ||
@@ -110,3 +110,3 @@ | ||
| let search_node = new Node(key, value); | ||
| return this.tree_search(this.root, search_node) ? true : false; | ||
| return !!this.tree_search(this.root, search_node); | ||
| } | ||
@@ -150,4 +150,3 @@ | ||
| let search_node = new Node(interval); | ||
| let found = this.tree_find_any_interval(this.root, search_node); | ||
| return found; | ||
| return this.tree_find_any_interval(this.root, search_node); | ||
| } | ||
@@ -204,7 +203,7 @@ | ||
| if (this.root == null || this.root == this.nil_node) { | ||
| if (this.root == null || this.root === this.nil_node) { | ||
| this.root = insert_node; | ||
| } | ||
| else { | ||
| while (current_node != this.nil_node) { | ||
| while (current_node !== this.nil_node) { | ||
| parent_node = current_node; | ||
@@ -239,6 +238,6 @@ if (insert_node.less_than(current_node)) { | ||
| current_node = insert_node; | ||
| while (current_node != this.root && current_node.parent.color == RB_TREE_COLOR_RED) { | ||
| if (current_node.parent == current_node.parent.parent.left) { // parent is left child of grandfather | ||
| while (current_node !== this.root && current_node.parent.color === RB_TREE_COLOR_RED) { | ||
| if (current_node.parent === current_node.parent.parent.left) { // parent is left child of grandfather | ||
| uncle_node = current_node.parent.parent.right; // right brother of parent | ||
| if (uncle_node.color == RB_TREE_COLOR_RED) { // Case 1. Uncle is red | ||
| if (uncle_node.color === RB_TREE_COLOR_RED) { // Case 1. Uncle is red | ||
| // re-color father and uncle into black | ||
@@ -251,3 +250,3 @@ current_node.parent.color = RB_TREE_COLOR_BLACK; | ||
| else { // Case 2 & 3. Uncle is black | ||
| if (current_node == current_node.parent.right) { // Case 2. Current if right child | ||
| if (current_node === current_node.parent.right) { // Case 2. Current if right child | ||
| // This case is transformed into Case 3. | ||
@@ -265,3 +264,3 @@ current_node = current_node.parent; | ||
| uncle_node = current_node.parent.parent.left; // left brother of parent | ||
| if (uncle_node.color == RB_TREE_COLOR_RED) { // Case 4. Uncle is red | ||
| if (uncle_node.color === RB_TREE_COLOR_RED) { // Case 4. Uncle is red | ||
| // re-color father and uncle into black | ||
@@ -274,3 +273,3 @@ current_node.parent.color = RB_TREE_COLOR_BLACK; | ||
| else { | ||
| if (current_node == current_node.parent.left) { // Case 5. Current is left child | ||
| if (current_node === current_node.parent.left) { // Case 5. Current is left child | ||
| // Transform into case 6 | ||
@@ -295,3 +294,3 @@ current_node = current_node.parent; | ||
| if (delete_node.left == this.nil_node || delete_node.right == this.nil_node) { // delete_node has less then 2 children | ||
| if (delete_node.left === this.nil_node || delete_node.right === this.nil_node) { // delete_node has less then 2 children | ||
| cut_node = delete_node; | ||
@@ -304,3 +303,3 @@ } | ||
| // fix_node if single child of cut_node | ||
| if (cut_node.left != this.nil_node) { | ||
| if (cut_node.left !== this.nil_node) { | ||
| fix_node = cut_node.left; | ||
@@ -317,7 +316,7 @@ } | ||
| if (cut_node == this.root) { | ||
| if (cut_node === this.root) { | ||
| this.root = fix_node; | ||
| } | ||
| else { | ||
| if (cut_node == cut_node.parent.left) { | ||
| if (cut_node === cut_node.parent.left) { | ||
| cut_node.parent.left = fix_node; | ||
@@ -336,3 +335,3 @@ } | ||
| // to node in outer structure and we will have to delete by key, additional search need | ||
| if (cut_node != delete_node) { | ||
| if (cut_node !== delete_node) { | ||
| delete_node.copy_data(cut_node); | ||
@@ -343,3 +342,3 @@ delete_node.update_max(); // update max property of the cut node at the new place | ||
| if (/*fix_node != this.nil_node && */cut_node.color == RB_TREE_COLOR_BLACK) { | ||
| if (/*fix_node != this.nil_node && */cut_node.color === RB_TREE_COLOR_BLACK) { | ||
| this.delete_fixup(fix_node); | ||
@@ -353,6 +352,6 @@ } | ||
| while (current_node != this.root && current_node.parent != null && current_node.color == RB_TREE_COLOR_BLACK) { | ||
| if (current_node == current_node.parent.left) { // fix node is left child | ||
| while (current_node !== this.root && current_node.parent != null && current_node.color === RB_TREE_COLOR_BLACK) { | ||
| if (current_node === current_node.parent.left) { // fix node is left child | ||
| brother_node = current_node.parent.right; | ||
| if (brother_node.color == RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| if (brother_node.color === RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| brother_node.color = RB_TREE_COLOR_BLACK; // re-color brother | ||
@@ -364,4 +363,4 @@ current_node.parent.color = RB_TREE_COLOR_RED; // re-color father | ||
| // Derive to cases 2..4: brother is black | ||
| if (brother_node.left.color == RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color == RB_TREE_COLOR_BLACK) { // case 2: both nephews black | ||
| if (brother_node.left.color === RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color === RB_TREE_COLOR_BLACK) { // case 2: both nephews black | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -371,3 +370,3 @@ current_node = current_node.parent; // continue iteration | ||
| else { | ||
| if (brother_node.right.color == RB_TREE_COLOR_BLACK) { // case 3: left nephew red, right nephew black | ||
| if (brother_node.right.color === RB_TREE_COLOR_BLACK) { // case 3: left nephew red, right nephew black | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -389,3 +388,3 @@ brother_node.left.color = RB_TREE_COLOR_BLACK; // re-color nephew | ||
| brother_node = current_node.parent.left; | ||
| if (brother_node.color == RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| if (brother_node.color === RB_TREE_COLOR_RED) { // Case 1. Brother is red | ||
| brother_node.color = RB_TREE_COLOR_BLACK; // re-color brother | ||
@@ -397,4 +396,4 @@ current_node.parent.color = RB_TREE_COLOR_RED; // re-color father | ||
| // Go to cases 2..4 | ||
| if (brother_node.left.color == RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color == RB_TREE_COLOR_BLACK) { // case 2 | ||
| if (brother_node.left.color === RB_TREE_COLOR_BLACK && | ||
| brother_node.right.color === RB_TREE_COLOR_BLACK) { // case 2 | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -404,3 +403,3 @@ current_node = current_node.parent; // continue iteration | ||
| else { | ||
| if (brother_node.left.color == RB_TREE_COLOR_BLACK) { // case 3: right nephew red, left nephew black | ||
| if (brother_node.left.color === RB_TREE_COLOR_BLACK) { // case 3: right nephew red, left nephew black | ||
| brother_node.color = RB_TREE_COLOR_RED; // re-color brother | ||
@@ -426,3 +425,3 @@ brother_node.right.color = RB_TREE_COLOR_BLACK; // re-color nephew | ||
| tree_search(node, search_node) { | ||
| if (node == null || node == this.nil_node) | ||
| if (node == null || node === this.nil_node) | ||
| return undefined; | ||
@@ -444,3 +443,3 @@ | ||
| let curr = node; | ||
| while (curr && curr != this.nil_node) { | ||
| while (curr && curr !== this.nil_node) { | ||
| if (curr.less_than(search_node)) { | ||
@@ -464,5 +463,5 @@ if (curr.intersect(search_node)) { | ||
| tree_search_interval(node, search_node, res) { | ||
| if (node != null && node != this.nil_node) { | ||
| if (node != null && node !== this.nil_node) { | ||
| // if (node->left != this.nil_node && node->left->max >= low) { | ||
| if (node.left != this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| if (node.left !== this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| this.tree_search_interval(node.left, search_node, res); | ||
@@ -475,3 +474,3 @@ } | ||
| // if (node->right != this.nil_node && node->low <= high) { | ||
| if (node.right != this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| if (node.right !== this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| this.tree_search_interval(node.right, search_node, res); | ||
@@ -484,13 +483,10 @@ } | ||
| let found = false; | ||
| if (node != null && node != this.nil_node) { | ||
| // if (node->left != this.nil_node && node->left->max >= low) { | ||
| if (node.left != this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| if (node != null && node !== this.nil_node) { | ||
| if (node.left !== this.nil_node && !node.not_intersect_left_subtree(search_node)) { | ||
| found = this.tree_find_any_interval(node.left, search_node); | ||
| } | ||
| // if (low <= node->high && node->low <= high) { | ||
| if (!found) { | ||
| found = node.intersect(search_node); | ||
| } | ||
| // if (node->right != this.nil_node && node->low <= high) { | ||
| if (!found && node.right != this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| if (!found && node.right !== this.nil_node && !node.not_intersect_right_subtree(search_node)) { | ||
| found = this.tree_find_any_interval(node.right, search_node); | ||
@@ -504,3 +500,3 @@ } | ||
| let node_min = node; | ||
| while (node_min.left != null && node_min.left != this.nil_node) { | ||
| while (node_min.left != null && node_min.left !== this.nil_node) { | ||
| node_min = node_min.left; | ||
@@ -514,3 +510,3 @@ } | ||
| let node_max = node; | ||
| while (node_max.right != null && node_max.right != this.nil_node) { | ||
| while (node_max.right != null && node_max.right !== this.nil_node) { | ||
| node_max = node_max.right; | ||
@@ -526,3 +522,3 @@ } | ||
| if (node.right != this.nil_node) { | ||
| if (node.right !== this.nil_node) { | ||
| node_successor = this.local_minimum(node.right); | ||
@@ -533,3 +529,3 @@ } | ||
| parent_node = node.parent; | ||
| while (parent_node != null && parent_node.right == current_node) { | ||
| while (parent_node != null && parent_node.right === current_node) { | ||
| current_node = parent_node; | ||
@@ -555,3 +551,3 @@ parent_node = parent_node.parent; | ||
| if (y.left != this.nil_node) { | ||
| if (y.left !== this.nil_node) { | ||
| y.left.parent = x; // x becomes parent of b | ||
@@ -561,7 +557,7 @@ } | ||
| if (x == this.root) { | ||
| if (x === this.root) { | ||
| this.root = y; // y becomes root | ||
| } | ||
| else { // y becomes child of x.parent | ||
| if (x == x.parent.left) { | ||
| if (x === x.parent.left) { | ||
| x.parent.left = y; | ||
@@ -576,3 +572,3 @@ } | ||
| if (x != null && x != this.nil_node) { | ||
| if (x !== null && x !== this.nil_node) { | ||
| x.update_max(); | ||
@@ -582,3 +578,3 @@ } | ||
| y = x.parent; | ||
| if (y != null && y != this.nil_node) { | ||
| if (y != null && y !== this.nil_node) { | ||
| y.update_max(); | ||
@@ -593,3 +589,3 @@ } | ||
| if (x.right != this.nil_node) { | ||
| if (x.right !== this.nil_node) { | ||
| x.right.parent = y; // y becomes parent of b | ||
@@ -599,7 +595,7 @@ } | ||
| if (y == this.root) { // x becomes root | ||
| if (y === this.root) { // x becomes root | ||
| this.root = x; | ||
| } | ||
| else { // y becomes child of x.parent | ||
| if (y == y.parent.left) { | ||
| if (y === y.parent.left) { | ||
| y.parent.left = x; | ||
@@ -614,3 +610,3 @@ } | ||
| if (y != null && y != this.nil_node) { | ||
| if (y !== null && y !== this.nil_node) { | ||
| y.update_max(); | ||
@@ -620,3 +616,3 @@ } | ||
| x = y.parent; | ||
| if (x != null && x != this.nil_node) { | ||
| if (x != null && x !== this.nil_node) { | ||
| x.update_max(); | ||
@@ -627,3 +623,3 @@ } | ||
| tree_walk(node, action) { | ||
| if (node != null && node != this.nil_node) { | ||
| if (node != null && node !== this.nil_node) { | ||
| this.tree_walk(node.left, action); | ||
@@ -640,4 +636,4 @@ // arr.push(node.toArray()); | ||
| this.tree_walk(this.root, function (node) { | ||
| if (node.color == RB_TREE_COLOR_RED) { | ||
| if (!(node.left.color == RB_TREE_COLOR_BLACK && node.right.color == RB_TREE_COLOR_BLACK)) { | ||
| if (node.color === RB_TREE_COLOR_RED) { | ||
| if (!(node.left.color === RB_TREE_COLOR_BLACK && node.right.color === RB_TREE_COLOR_BLACK)) { | ||
| res = false; | ||
@@ -655,6 +651,6 @@ } | ||
| let heightRight = 0; | ||
| if (node.color == RB_TREE_COLOR_BLACK) { | ||
| if (node.color === RB_TREE_COLOR_BLACK) { | ||
| height++; | ||
| } | ||
| if (node.left != this.nil_node) { | ||
| if (node.left !== this.nil_node) { | ||
| heightLeft = this.testBlackHeightProperty(node.left); | ||
@@ -665,3 +661,3 @@ } | ||
| } | ||
| if (node.right != this.nil_node) { | ||
| if (node.right !== this.nil_node) { | ||
| heightRight = this.testBlackHeightProperty(node.right); | ||
@@ -672,3 +668,3 @@ } | ||
| } | ||
| if (heightLeft != heightRight) { | ||
| if (heightLeft !== heightRight) { | ||
| throw new Error('Red-black height property violated'); | ||
@@ -679,4 +675,4 @@ } | ||
| } | ||
| }; | ||
| } | ||
| export default IntervalTree; |
@@ -8,3 +8,3 @@ /** | ||
| import Interval from './interval.js'; | ||
| import {RB_TREE_COLOR_RED, RB_TREE_COLOR_BLACK} from '../utils/constants.js'; | ||
| import {RB_TREE_COLOR_BLACK} from '../utils/constants.js'; | ||
@@ -22,5 +22,7 @@ class Node { | ||
| /* If not, this should by an array of two numbers */ | ||
| if (key && key instanceof Array && key.length == 2) { | ||
| if (key && key instanceof Array && key.length === 2) { | ||
| if (!Number.isNaN(key[0]) && !Number.isNaN(key[1])) { | ||
| this.item.key = new Interval(Math.min(key[0], key[1]), Math.max(key[0], key[1])); | ||
| let [low, high] = key | ||
| if (low > high) [low, high] = [high, low] | ||
| this.item.key = new Interval(low, high); | ||
| } | ||
@@ -57,3 +59,3 @@ } | ||
| this.item.value.equal_to(other_node.item.value) : | ||
| this.item.value == other_node.item.value; | ||
| this.item.value === other_node.item.value; | ||
| } | ||
@@ -105,4 +107,4 @@ equal_to(other_node) { | ||
| } | ||
| }; | ||
| } | ||
| export default Node; |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
No alert changes
Worsened metrics
- Total package byte prevSize
- decreased by-0.17%
147975
- Number of lines in readme file
- decreased by-1.4%
212
No dependency changes