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

Comparing version 1.0.13 to 1.0.14

dist/main.cjs.js

@@ -365,3 +365,3 @@ 'use strict';
      * If no values stored in the tree, returns array of keys which intersect given interval
-     * @param {Interval} interval - search interval, or array [low, high]
+     * @param {Interval} interval - search interval, or tuple [low, high]
      * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output
@@ -378,2 +378,13 @@ * @returns {Array}
     /**
+     * Returns true if intersection between given and any interval stored in the tree found
+     * @param {Interval} interval - search interval or tuple [low, high]
+     * @returns {boolean}
+     */
+    intersect_any(interval) {
+        let search_node = new Node(interval);
+        let found = this.tree_find_any_interval(this.root, search_node);
+        return found;
+    }
+
+    /**
      * Tree visitor. For each node implement a callback function. <br/>
@@ -647,2 +658,21 @@ * Method calls a callback function with two parameters (key, value)
 
+    tree_find_any_interval(node, search_node) {
+        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)) {
+                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)) {
+                found = this.tree_find_any_interval(node.right, search_node);
+            }
+        }
+        return found;
+    }
+
     local_minimum(node) {
@@ -649,0 +679,0 @@ let node_min = node;

dist/main.esm.js

@@ -361,3 +361,3 @@ /**
      * If no values stored in the tree, returns array of keys which intersect given interval
-     * @param {Interval} interval - search interval, or array [low, high]
+     * @param {Interval} interval - search interval, or tuple [low, high]
      * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output
@@ -374,2 +374,13 @@ * @returns {Array}
     /**
+     * Returns true if intersection between given and any interval stored in the tree found
+     * @param {Interval} interval - search interval or tuple [low, high]
+     * @returns {boolean}
+     */
+    intersect_any(interval) {
+        let search_node = new Node(interval);
+        let found = this.tree_find_any_interval(this.root, search_node);
+        return found;
+    }
+
+    /**
      * Tree visitor. For each node implement a callback function. <br/>
@@ -643,2 +654,21 @@ * Method calls a callback function with two parameters (key, value)
 
+    tree_find_any_interval(node, search_node) {
+        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)) {
+                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)) {
+                found = this.tree_find_any_interval(node.right, search_node);
+            }
+        }
+        return found;
+    }
+
     local_minimum(node) {
@@ -645,0 +675,0 @@ let node_min = node;

dist/main.umd.js

@@ -367,3 +367,3 @@ (function (global, factory) {
          * If no values stored in the tree, returns array of keys which intersect given interval
-         * @param {Interval} interval - search interval, or array [low, high]
+         * @param {Interval} interval - search interval, or tuple [low, high]
          * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output
@@ -380,2 +380,13 @@ * @returns {Array}
         /**
+         * Returns true if intersection between given and any interval stored in the tree found
+         * @param {Interval} interval - search interval or tuple [low, high]
+         * @returns {boolean}
+         */
+        intersect_any(interval) {
+            let search_node = new Node(interval);
+            let found = this.tree_find_any_interval(this.root, search_node);
+            return found;
+        }
+
+        /**
          * Tree visitor. For each node implement a callback function. <br/>
@@ -649,2 +660,21 @@ * Method calls a callback function with two parameters (key, value)
 
+        tree_find_any_interval(node, search_node) {
+            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)) {
+                    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)) {
+                    found = this.tree_find_any_interval(node.right, search_node);
+                }
+            }
+            return found;
+        }
+
         local_minimum(node) {
@@ -651,0 +681,0 @@ let node_min = node;

index.d.ts

@@ -1,6 +0,6 @@
-// Type definitions for flatten-interval-tree library v1.0.2
+// Type definitions for flatten-interval-tree library
 // Project: https://github.com/alexbol99/flatten-js
 // Definitions by: Alex Bol
 
-type Comparable = any;      // any object that implements operators '<' and '==' and  method'max'
+type Comparable = any;      // any object that implements operators '<' and '==' and  method 'max'
 type Value<T> = T;
@@ -77,2 +77,3 @@ type NumericTuple = [number,number];
     search(interval: Interval | NumericTuple, outputMapperFn?: (value: Value<T>, key: Interval) => MappedItem) : SearchOutput<T>;
+    intersect_any(interval: Interval | NumericTuple) : boolean;
     forEach(callbackfn: (key: Interval, value: Value<T>) => void, thisArg?: any ) : void;
@@ -79,0 +80,0 @@ map(callbackFn: (value: Value<T>, key?: Interval) => any, thisArg?: any ): IntervalTree<T>;

package.json

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

README.md

@@ -124,3 +124,9 @@ # Interval Tree
 
+### Intersect_any(interval)
+Returns true if intersection between given and any interval stored in the tree found
 
+```javascript
+let found = tree.intersect_any(interval)
+```
+
 ### Size
@@ -127,0 +133,0 @@ Returns number of items stored in the tree (getter)

src/classes/intervalTree.js

@@ -122,3 +122,3 @@ /**
      * If no values stored in the tree, returns array of keys which intersect given interval
-     * @param {Interval} interval - search interval, or array [low, high]
+     * @param {Interval} interval - search interval, or tuple [low, high]
      * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output
@@ -135,2 +135,13 @@ * @returns {Array}
     /**
+     * Returns true if intersection between given and any interval stored in the tree found
+     * @param {Interval} interval - search interval or tuple [low, high]
+     * @returns {boolean}
+     */
+    intersect_any(interval) {
+        let search_node = new Node(interval);
+        let found = this.tree_find_any_interval(this.root, search_node);
+        return found;
+    }
+
+    /**
      * Tree visitor. For each node implement a callback function. <br/>
@@ -404,2 +415,21 @@ * Method calls a callback function with two parameters (key, value)
 
+    tree_find_any_interval(node, search_node) {
+        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)) {
+                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)) {
+                found = this.tree_find_any_interval(node.right, search_node);
+            }
+        }
+        return found;
+    }
+
     local_minimum(node) {
@@ -406,0 +436,0 @@ let node_min = node;

test/intervalTree.js

@@ -266,2 +266,42 @@ /**
     })
+    it('May search interval and return true if intersection with any interval found. Issue #26', function () {
+        let tree = new IntervalTree();
+        let intervals = [[7,8],[1,4],[11,12],[1,1],[5,7]];
+        for (let i=0; i < intervals.length; i++) tree.insert(intervals[i],"val"+i);
+        expect(tree.intersect_any([2,3])).to.be.true;
+        expect(tree.intersect_any([4,4])).to.be.true;
+        expect(tree.intersect_any([4,10])).to.be.true;
+        expect(tree.intersect_any([9,10])).to.be.false;
+        expect(tree.intersect_any([-1,0])).to.be.false;
+        expect(tree.intersect_any([15,20])).to.be.false;
+    });
+    it('May search interval and return true if intersection with any interval found. Issue #26', function () {
+        let tree = new IntervalTree();
+        let intervals = [[7,8],[1,4],[11,12],[1,1],[5,7]];
+        for (let i=0; i < intervals.length; i++) tree.insert(intervals[i],"val"+i);
+        expect(tree.intersect_any([2,3])).to.be.true;
+        expect(tree.intersect_any([4,4])).to.be.true;
+        expect(tree.intersect_any([4,10])).to.be.true;
+        expect(tree.intersect_any([9,10])).to.be.false;
+        expect(tree.intersect_any([-1,0])).to.be.false;
+        expect(tree.intersect_any([15,20])).to.be.false;
+    });
+    it('May test if any of great composers lived in second half of XX century', function () {
+        const composers = [
+            {name: "Ludwig van Beethoven", period: [1770,1827]},
+            {name: "Johann Sebastian Bach", period: [1685, 1750]},
+            {name: "Wolfgang Amadeus Mozart", period: [1756, 1791]},
+            {name: "Johannes Brahms", period: [1833, 1897]},
+            {name: "Richard Wagner", period: [1813, 1883]},
+            {name: "Claude Debussy", period: [1862, 1918]},
+            {name: "Pyotr Ilyich Tchaikovsky", period: [1840, 1893]},
+            {name: "Frédéric Chopin", period: [1810, 1849]},
+            {name: "Joseph Haydn", period: [1732, 1809]},
+            {name: "Antonio Vivaldi", period: [1678, 1741]}
+        ];
+        const tree = new IntervalTree();
+        for (let composer of composers)
+            tree.insert(composer.period, composer.name);
+        expect(tree.intersect_any( [1950, 2000])).to.be.false;
+    });
 });

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

1691136

increased by0.72%

Lines of code

4379

increased by3.62%

Number of lines in readme file

185

increased by3.35%

No dependency changes