@flatten-js/interval-tree - npm Package Compare versions

Comparing version 1.1.2 to 1.1.3

dist/main.cjs

@@ -12,3 +12,3 @@ 'use strict';
  * *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()*.
@@ -59,3 +59,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;
     }
@@ -69,3 +69,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;
     }
@@ -93,3 +93,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}
@@ -99,4 +99,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)
         );
@@ -162,5 +164,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);
             }
@@ -197,3 +201,3 @@ }
             this.item.value.equal_to(other_node.item.value) :
-            this.item.value == other_node.item.value;
+            this.item.value === other_node.item.value;
     }
@@ -318,3 +322,3 @@ equal_to(other_node) {
     isEmpty() {
-        return (this.root == null || this.root == this.nil_node);
+        return (this.root == null || this.root === this.nil_node);
     }
@@ -351,3 +355,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);
     }
@@ -391,4 +395,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);
     }
@@ -445,7 +448,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;
@@ -480,6 +483,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
@@ -492,3 +495,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.
@@ -506,3 +509,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
@@ -515,3 +518,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
@@ -536,3 +539,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;
@@ -545,3 +548,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;
@@ -558,7 +561,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;
@@ -577,3 +580,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);
@@ -584,3 +587,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);
@@ -594,6 +597,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
@@ -605,4 +608,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
@@ -612,3 +615,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
@@ -630,3 +633,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
@@ -638,4 +641,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
@@ -645,3 +648,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
@@ -667,3 +670,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;
@@ -685,3 +688,3 @@
         let curr = node;
-        while (curr && curr != this.nil_node) {
+        while (curr && curr !== this.nil_node) {
             if (curr.less_than(search_node)) {
@@ -705,5 +708,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);
@@ -716,3 +719,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);
@@ -725,13 +728,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);
@@ -745,3 +745,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;
@@ -755,3 +755,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;
@@ -767,3 +767,3 @@ }
 
-        if (node.right != this.nil_node) {
+        if (node.right !== this.nil_node) {
             node_successor = this.local_minimum(node.right);
@@ -774,3 +774,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;
@@ -796,3 +796,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
@@ -802,7 +802,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;
@@ -817,3 +817,3 @@ }
 
-        if (x != null && x != this.nil_node) {
+        if (x != null && x !== this.nil_node) {
             x.update_max();
@@ -823,3 +823,3 @@ }
         y = x.parent;
-        if (y != null && y != this.nil_node) {
+        if (y != null && y !== this.nil_node) {
             y.update_max();
@@ -834,3 +834,3 @@ }
 
-        if (x.right != this.nil_node) {
+        if (x.right !== this.nil_node) {
             x.right.parent = y;        // y becomes parent of b
@@ -840,7 +840,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;
@@ -855,3 +855,3 @@ }
 
-        if (y != null && y != this.nil_node) {
+        if (y !== null && y !== this.nil_node) {
             y.update_max();
@@ -861,3 +861,3 @@ }
         x = y.parent;
-        if (x != null && x != this.nil_node) {
+        if (x != null && x !== this.nil_node) {
             x.update_max();
@@ -868,3 +868,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);
@@ -881,4 +881,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;
@@ -896,6 +896,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);
@@ -906,3 +906,3 @@ }
         }
-        if (node.right != this.nil_node) {
+        if (node.right !== this.nil_node) {
             heightRight = this.testBlackHeightProperty(node.right);
@@ -913,3 +913,3 @@ }
         }
-        if (heightLeft != heightRight) {
+        if (heightLeft !== heightRight) {
             throw new Error('Red-black height property violated');
@@ -916,0 +916,0 @@ }

dist/main.mjs

@@ -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)
         );
@@ -158,5 +160,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);
             }
@@ -193,3 +197,3 @@ }
             this.item.value.equal_to(other_node.item.value) :
-            this.item.value == other_node.item.value;
+            this.item.value === other_node.item.value;
     }
@@ -314,3 +318,3 @@ equal_to(other_node) {
     isEmpty() {
-        return (this.root == null || this.root == this.nil_node);
+        return (this.root == null || this.root === this.nil_node);
     }
@@ -347,3 +351,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);
     }
@@ -387,4 +391,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);
     }
@@ -441,7 +444,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;
@@ -476,6 +479,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
@@ -488,3 +491,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.
@@ -502,3 +505,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
@@ -511,3 +514,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
@@ -532,3 +535,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;
@@ -541,3 +544,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;
@@ -554,7 +557,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;
@@ -573,3 +576,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);
@@ -580,3 +583,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);
@@ -590,6 +593,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
@@ -601,4 +604,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
@@ -608,3 +611,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
@@ -626,3 +629,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
@@ -634,4 +637,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
@@ -641,3 +644,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
@@ -663,3 +666,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;
@@ -681,3 +684,3 @@
         let curr = node;
-        while (curr && curr != this.nil_node) {
+        while (curr && curr !== this.nil_node) {
             if (curr.less_than(search_node)) {
@@ -701,5 +704,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);
@@ -712,3 +715,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);
@@ -721,13 +724,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);
@@ -741,3 +741,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;
@@ -751,3 +751,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;
@@ -763,3 +763,3 @@ }
 
-        if (node.right != this.nil_node) {
+        if (node.right !== this.nil_node) {
             node_successor = this.local_minimum(node.right);
@@ -770,3 +770,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;
@@ -792,3 +792,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
@@ -798,7 +798,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;
@@ -813,3 +813,3 @@ }
 
-        if (x != null && x != this.nil_node) {
+        if (x != null && x !== this.nil_node) {
             x.update_max();
@@ -819,3 +819,3 @@ }
         y = x.parent;
-        if (y != null && y != this.nil_node) {
+        if (y != null && y !== this.nil_node) {
             y.update_max();
@@ -830,3 +830,3 @@ }
 
-        if (x.right != this.nil_node) {
+        if (x.right !== this.nil_node) {
             x.right.parent = y;        // y becomes parent of b
@@ -836,7 +836,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;
@@ -851,3 +851,3 @@ }
 
-        if (y != null && y != this.nil_node) {
+        if (y !== null && y !== this.nil_node) {
             y.update_max();
@@ -857,3 +857,3 @@ }
         x = y.parent;
-        if (x != null && x != this.nil_node) {
+        if (x != null && x !== this.nil_node) {
             x.update_max();
@@ -864,3 +864,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);
@@ -877,4 +877,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;
@@ -892,6 +892,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);
@@ -902,3 +902,3 @@ }
         }
-        if (node.right != this.nil_node) {
+        if (node.right !== this.nil_node) {
             heightRight = this.testBlackHeightProperty(node.right);
@@ -909,3 +909,3 @@ }
         }
-        if (heightLeft != heightRight) {
+        if (heightLeft !== heightRight) {
             throw new Error('Red-black height property violated');
@@ -912,0 +912,0 @@ }

dist/main.umd.js

@@ -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 @@ }

package.json

 {
   "name": "@flatten-js/interval-tree",
-  "version": "1.1.2",
+  "version": "1.1.3",
   "description": "Interval search tree",
@@ -5,0 +5,0 @@ "author": "Alex Bol",

README.md

@@ -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

src/classes/interval.js

@@ -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 @@ }

src/classes/intervalTree.js

@@ -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;

src/classes/node.js

@@ -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;

No alert changes

Worsened metrics

Total package byte prevSize

147975

-0.17%

Number of lines in readme file

212

-1.4%

No dependency changes