Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
@flatten-js/interval-tree
Advanced tools
@flatten-js/interval-tree - npm Package Compare versions
Comparing version 1.0.21 to 1.1.0
@@ -395,5 +395,6 @@ 'use strict'; | ||
| /** Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| /** | ||
| * Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| map(callback) { | ||
@@ -405,2 +406,20 @@ const tree = new IntervalTree(); | ||
| /** | ||
| * @param {Interval} interval - optional if the iterator is intended to start from the beginning or end | ||
| * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output | ||
| * @returns {Iterator} | ||
| */ | ||
| *iterate(interval, outputMapperFn = (value, key) => value === key ? key.output() : value) { | ||
| let node; | ||
| if (interval) { | ||
| node = this.tree_search_nearest_forward(this.root, new Node(interval)); | ||
| } else if (this.root) { | ||
| node = this.local_minimum(this.root); | ||
| } | ||
| while (node) { | ||
| yield outputMapperFn(node.item.value, node.item.key); | ||
| node = this.tree_successor(node); | ||
| } | ||
| } | ||
| recalc_max(node) { | ||
@@ -638,2 +657,17 @@ let node_current = node; | ||
| tree_search_nearest_forward(node, search_node) { | ||
| let best; | ||
| let curr = node; | ||
| while (curr && curr != this.nil_node) { | ||
| if (curr.less_than(search_node)) { | ||
| if (curr.intersect(search_node) && (!best || curr.less_than(best))) best = curr; | ||
| curr = curr.right; | ||
| } else { | ||
| if (!best || curr.less_than(best)) best = curr; | ||
| curr = curr.left; | ||
| } | ||
| } | ||
| return best || null; | ||
| } | ||
| // Original search_interval method; container res support push() insertion | ||
@@ -836,3 +870,3 @@ // Search all intervals intersecting given one | ||
| return height; | ||
| }; | ||
| } | ||
| } | ||
@@ -839,0 +873,0 @@ |
@@ -391,5 +391,6 @@ /** | ||
| /** Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| /** | ||
| * Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| map(callback) { | ||
@@ -401,2 +402,20 @@ const tree = new IntervalTree(); | ||
| /** | ||
| * @param {Interval} interval - optional if the iterator is intended to start from the beginning or end | ||
| * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output | ||
| * @returns {Iterator} | ||
| */ | ||
| *iterate(interval, outputMapperFn = (value, key) => value === key ? key.output() : value) { | ||
| let node; | ||
| if (interval) { | ||
| node = this.tree_search_nearest_forward(this.root, new Node(interval)); | ||
| } else if (this.root) { | ||
| node = this.local_minimum(this.root); | ||
| } | ||
| while (node) { | ||
| yield outputMapperFn(node.item.value, node.item.key); | ||
| node = this.tree_successor(node); | ||
| } | ||
| } | ||
| recalc_max(node) { | ||
@@ -634,2 +653,17 @@ let node_current = node; | ||
| tree_search_nearest_forward(node, search_node) { | ||
| let best; | ||
| let curr = node; | ||
| while (curr && curr != this.nil_node) { | ||
| if (curr.less_than(search_node)) { | ||
| if (curr.intersect(search_node) && (!best || curr.less_than(best))) best = curr; | ||
| curr = curr.right; | ||
| } else { | ||
| if (!best || curr.less_than(best)) best = curr; | ||
| curr = curr.left; | ||
| } | ||
| } | ||
| return best || null; | ||
| } | ||
| // Original search_interval method; container res support push() insertion | ||
@@ -832,5 +866,5 @@ // Search all intervals intersecting given one | ||
| return height; | ||
| }; | ||
| } | ||
| } | ||
| export { Interval, Node, IntervalTree as default }; |
@@ -397,5 +397,6 @@ (function (global, factory) { | ||
| /** Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| /** | ||
| * Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| map(callback) { | ||
@@ -407,2 +408,20 @@ const tree = new IntervalTree(); | ||
| /** | ||
| * @param {Interval} interval - optional if the iterator is intended to start from the beginning or end | ||
| * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output | ||
| * @returns {Iterator} | ||
| */ | ||
| *iterate(interval, outputMapperFn = (value, key) => value === key ? key.output() : value) { | ||
| let node; | ||
| if (interval) { | ||
| node = this.tree_search_nearest_forward(this.root, new Node(interval)); | ||
| } else if (this.root) { | ||
| node = this.local_minimum(this.root); | ||
| } | ||
| while (node) { | ||
| yield outputMapperFn(node.item.value, node.item.key); | ||
| node = this.tree_successor(node); | ||
| } | ||
| } | ||
| recalc_max(node) { | ||
@@ -640,2 +659,17 @@ let node_current = node; | ||
| tree_search_nearest_forward(node, search_node) { | ||
| let best; | ||
| let curr = node; | ||
| while (curr && curr != this.nil_node) { | ||
| if (curr.less_than(search_node)) { | ||
| if (curr.intersect(search_node) && (!best || curr.less_than(best))) best = curr; | ||
| curr = curr.right; | ||
| } else { | ||
| if (!best || curr.less_than(best)) best = curr; | ||
| curr = curr.left; | ||
| } | ||
| } | ||
| return best || null; | ||
| } | ||
| // Original search_interval method; container res support push() insertion | ||
@@ -838,3 +872,3 @@ // Search all intervals intersecting given one | ||
| return height; | ||
| }; | ||
| } | ||
| } | ||
@@ -841,0 +875,0 @@ |
@@ -9,3 +9,5 @@ // Type definitions for flatten-interval-tree library | ||
| type MappedItem = any; | ||
| type OutputMapperFn<T> = (value: Value<T>, key: Interval) => MappedItem | ||
| export type SearchOutput<T> = Array<Value<T>> | Array<Interval> | Array<MappedItem> | ||
| export type IterableOutput<T> = Iterable<Value<T>> | Iterable<Interval> | Iterable<MappedItem> | ||
@@ -80,3 +82,4 @@ interface IntervalInterface { | ||
| remove(key: Interval | NumericTuple, value?: Value<T>) : Node<T>; | ||
| search(interval: Interval | NumericTuple, outputMapperFn?: (value: Value<T>, key: Interval) => MappedItem) : SearchOutput<T>; | ||
| search(interval: Interval | NumericTuple, outputMapperFn?: OutputMapperFn<T>) : SearchOutput<T>; | ||
| iterate(interval?: Interval | NumericTuple, outputMapperFn?: OutputMapperFn<T>) : IterableOutput<T> | ||
| intersect_any(interval: Interval | NumericTuple) : boolean; | ||
@@ -83,0 +86,0 @@ forEach(callbackfn: (key: Interval, value: Value<T>) => void, thisArg?: any ) : void; |
| { | ||
| "name": "@flatten-js/interval-tree", | ||
| "version": "1.0.21", | ||
| "version": "1.1.0", | ||
| "description": "Interval search tree", | ||
@@ -14,3 +14,4 @@ "author": "Alex Bol", | ||
| "require": [ | ||
| "@babel/register" | ||
| "@babel/register", | ||
| "@babel/polyfill" | ||
| ], | ||
@@ -43,3 +44,3 @@ "sourceMap": false, | ||
| "@babel/cli": "^7.2.3", | ||
| "@babel/core": "^7.2.2", | ||
| "@babel/core": "^7.22.9", | ||
| "@babel/node": "^7.2.2", | ||
@@ -50,6 +51,6 @@ "@babel/preset-env": "^7.3.1", | ||
| "chai": "^4.2.0", | ||
| "coveralls": "^3.0.3", | ||
| "coveralls": "^3.1.1", | ||
| "jsdoc": "^3.6.2", | ||
| "minami": "^1.2.3", | ||
| "mocha": "^8.2.0", | ||
| "mocha": "^10.1.0", | ||
| "nyc": "^15.1.0", | ||
@@ -56,0 +57,0 @@ "rollup": "^3.25.1" |
@@ -78,3 +78,3 @@ # Interval Tree | ||
| ### Exist(key,value) | ||
| ### Exist(key, value) | ||
| Method returns true if item {key, value} exists in the tree. <br/> | ||
@@ -175,2 +175,25 @@ Method may be useful if need to support unique items. | ||
| ### Iterate([interval, outputMapperFn]) | ||
| Returns an iterator (and iterable). <br/> | ||
| Call `next` on the iterator to navigate to successor tree nodes and return the corresponding values. <br/> | ||
| In the absence of a starting interval, the iterator will start with the lowest interval. <br/> | ||
| ```javascript | ||
| let iterator = tree.iterate(); | ||
| let next = iterator.next().value; | ||
| ``` | ||
| Optional *outputMapperFn(value, key)* enables to map search results into custom defined output. <br/> | ||
| Example: | ||
| ```javascript | ||
| let iterator = tree.iterate([5,5], (value, key) => key); | ||
| let next_key = iterator.next().value; | ||
| ``` | ||
| Supports `for .. of` syntax. <br/> | ||
| Example: | ||
| ```javascript | ||
| for (let key of tree.iterate([5,5], (value, key) => key)) { | ||
| if (key[0] > 8) break; | ||
| console.log(key); | ||
| } | ||
| ``` | ||
| ## Documentation | ||
@@ -177,0 +200,0 @@ Documentation may be found here: [https://alexbol99.github.io/flatten-interval-tree](https://alexbol99.github.io/flatten-interval-tree/) |
@@ -160,5 +160,6 @@ /** | ||
| /** Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| /** | ||
| * Value Mapper. Walk through every node and map node value to another value | ||
| * @param callback(value,key) - function to be called for each tree item | ||
| */ | ||
| map(callback) { | ||
@@ -170,2 +171,20 @@ const tree = new IntervalTree(); | ||
| /** | ||
| * @param {Interval} interval - optional if the iterator is intended to start from the beginning | ||
| * @param outputMapperFn(value,key) - optional function that maps (value, key) to custom output | ||
| * @returns {Iterator} | ||
| */ | ||
| *iterate(interval, outputMapperFn = (value, key) => value === key ? key.output() : value) { | ||
| let node; | ||
| if (interval) { | ||
| node = this.tree_search_nearest_forward(this.root, new Node(interval)); | ||
| } else if (this.root) { | ||
| node = this.local_minimum(this.root); | ||
| } | ||
| while (node) { | ||
| yield outputMapperFn(node.item.value, node.item.key); | ||
| node = this.tree_successor(node); | ||
| } | ||
| } | ||
| recalc_max(node) { | ||
@@ -403,2 +422,17 @@ let node_current = node; | ||
| tree_search_nearest_forward(node, search_node) { | ||
| let best; | ||
| let curr = node; | ||
| while (curr && curr != this.nil_node) { | ||
| if (curr.less_than(search_node)) { | ||
| if (curr.intersect(search_node) && (!best || curr.less_than(best))) best = curr; | ||
| curr = curr.right; | ||
| } else { | ||
| if (!best || curr.less_than(best)) best = curr; | ||
| curr = curr.left; | ||
| } | ||
| } | ||
| return best || null; | ||
| } | ||
| // Original search_interval method; container res support push() insertion | ||
@@ -601,5 +635,5 @@ // Search all intervals intersecting given one | ||
| return height; | ||
| }; | ||
| } | ||
| }; | ||
| export default IntervalTree; |
New alerts
License Policy Violation
LicenseThis 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
LicenseThis 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
- increased by4.43%
147800
- Number of package files
- increased by6.25%
17
- Lines of code
- increased by4.68%
3241
- Number of lines in readme file
- increased by11.98%
215
No dependency changes