@flatten-js/interval-tree
v2.0.0-alpha.1TypeScript
Interval search tree with TypeScript support
0/weekUpdated 3 months agoMITUnpacked: 200.6 KB
Published by Alex Bol
npm install @flatten-js/interval-treeInterval Tree
The package @flatten-js/interval-tree is an implementation of interval binary search tree according to Cormen et al. Introduction to Algorithms (2009, Section 14.3: Interval trees, pp. 348–354).
Cormen shows that insertion, deletion of nodes and range queries take O(log(n)) time where n is the number of items
stored in the tree.
This package is a part of flatten-js library.
An earlier implementation, flatten-interval-tree, is deprecated.
Please use this package (@flatten-js/interval-tree) instead.
Contacts
LinkedIn: Alexander Bol
X (Twitter) @alex_bol_
Installation
``
bash
npm install --save @flatten-js/interval-tree
`
Usage
ts
import IntervalTree from '@flatten-js/interval-tree'
// TypeScript: specify value type for better hints
const tree = new IntervalTree();
`$3
Tree stores pairs where key is an interval, and value is an object of any type.
If value is omitted, the tree stores the key itself as the value for convenience, so searches and iteration still return the key (you can always provide your own mapper).Keys with the same interval are now bucketed into a single node. This means multiple values can be stored under one identical key without requiring values to be comparable.
No custom comparator is required for values. Equality for values is by strict equality (
===) unless your value implements an equal_to(other) method.Interval can be a pair of numbers
[low, high] (numeric pairs are normalized so that low <= high).
User may also implement their own Interval class as an extension of the IntervalBase class.
See Interval2d class in Interval.ts for an example of such extension.$3
`ts
import IntervalTree from '@flatten-js/interval-tree';const tree = new IntervalTree();
const intervals: Array<[number, number]> = [[6,8],[1,4],[5,12],[1,1],[5,7]];
// Insert interval as a key and string "val0", "val1" etc. as a value
intervals.forEach((iv, i) => {
tree.insert(iv, "val"+i);
});
// Get array of keys sorted in ascendant order
const sorted_intervals = tree.keys; // expected array [[1,1],[1,4],[5,7],[5,12],[6,8]]
// Search items which keys intersect with given interval, and return array of values
const values_in_range = tree.search([2,3]); // expected array ['val1']
`Interval types
The library supports multiple interval classes:
- Interval (default export): 1D interval whose endpoints are comparable (number, bigint, string, Date).
- Interval2D: a lexicographic 2D interval whose endpoints are points [x, y].ts
import IntervalTree, { Interval2D } from '@flatten-js/interval-tree';// example of Interval2d tree which stores string values
const tree = new IntervalTree();
// 2D intervals (lexicographic ordering)
const r1 = new Interval2D([0, 0], [10, 10]);
const r2 = new Interval2D([5, 5], [15, 15]);
tree.insert(r1, 'R1');
tree.insert(r2, 'R2');
`$3
Create a new instance of the interval tree. In TypeScript, you may optionally specify the value type V for stronger type hints.
ts
// Without explicit value type (values default to unknown/any as inferred)
const tree = new IntervalTree();// With explicit value type V
const treeStrings = new IntervalTree();
const treeObjects = new IntervalTree<{ id: number; name: string }>();
`$3
Insert a new item into the tree. Key is an interval object or a pair of numbers (numeric pairs are normalized so that low <= high).
If value is omitted, the key itself is stored as the value for convenience.
If a node with an identical key already exists, the value is appended to that node’s bucket.
Returns a reference to the inserted node.
`ts
const node = tree.insert(key, value)
`$3
Returns if the item exists in the tree.
- Called as exist(key), it checks whether a node with the given key exists (bucket may contain one or more values).
- Called as exist(key, value), it checks whether the specific value exists inside the bucket of that key (strict equality unless the value implements equal_to).
`ts
const existsKey = tree.exist(key)
const existsPair = tree.exist(key, value)
`$3
Removes entries from the tree.
- Called as , it removes the entire node for that key (i.e., the whole bucket).
- Called as remove(key, value), it removes a single matching value from the bucket; if the bucket becomes empty, the node is removed.
Returns the removed node if something was deleted, or undefined if nothing was found.
`ts
const removedNode = tree.remove(key)
const removedPairNode = tree.remove(key, value)
`$3
Returns array of values which keys intersected with given interval.
javascript
const resp = tree.search(interval)
`
Optional outputMapperFn(value, key) enables to map search results into custom defined output.
Example:
javascript
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 (const composer of composers)
tree.insert(composer.period, composer.name);// Great composers who lived in 17th century
const searchRes = tree.search( [1600,1700],
(name, period) => {return
${name} (${period.low}-${period.high})});console.log(searchRes)
// expected to be
// [ 'Antonio Vivaldi (1678-1741)', 'Johann Sebastian Bach (1685-1750)' ]
`$3
Returns true if intersection found between given interval and any of intervals stored in the treejavascript
const found = tree.intersect_any(interval)
`$3
Returns number of items stored in the tree (getter)
javascript
const size = tree.size
`$3
Returns tree keys in ascendant order (getter)
javascript
const keys = tree.keys
`$3
Returns tree values in ascendant keys order (getter)
javascript
const values = tree.values
` $3
Returns items in ascendant keys order (getter)
`javascript
const items = tree.items
`$3
Enables to traverse the whole tree and perform operation for each item
javascript
tree.forEach( (key, value) => console.log(value) )
`$3
Creates new tree with same keys using callback to transform (key,value) to a new value
javascript
let tree1 = tree.map((value, key) => (key.high-key.low))
`$3
Clear tree
javascript
tree.clear()
`$3
Returns an iterator (and iterable).
Call on the iterator to navigate to successor tree nodes and return the corresponding values.
In the absence of a starting interval, the iterator will start with the lowest interval.
`javascript
let iterator = tree.iterate();
let next = iterator.next().value;
`
Optional outputMapperFn(value, key) enables to map search results into custom defined output.
Example:
javascript
let iterator = tree.iterate([5,5], (value, key) => key);
let next_key = iterator.next().value;
`
Supports syntax.
Example:
`javascript
for (let key of tree.iterate([5,5], (value, key) => key)) {
if (key[0] > 8) break;
console.log(key);
}
`Documentation
API reference is now generated with TypeDoc and published to GitHub Pages.
- Live examples: https://alexbol99.github.io/flatten-interval-tree/examples.html
- API docs: https://alexbol99.github.io/flatten-interval-tree/Styling: The docs use TypeDoc’s default theme with a custom stylesheet (typedoc.theme.css) for improved typography, spacing, a branded accent color, and automatic dark mode. The top navigation also links to GitHub and the live examples page.
To build docs locally:
bash
npm run docs
`
The output is written into the docs/ folder.Tests
bash
npm test
``Contributors
In lieu of a formal style guide, take care to maintain the existing coding style. Add unit tests for any new or changed functionality. Lint and test your code.
License
MIT
Support
