Interval 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

npm install --save @flatten-js/interval-tree
Copy

Usage

import IntervalTree from '@flatten-js/interval-tree'
// TypeScript: specify value type for better hints
const tree = new IntervalTree<string>();
Copy

Notes

Tree stores pairs <key, value> 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.

Example

import IntervalTree from '@flatten-js/interval-tree';

const tree = new IntervalTree<string>();

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']
Copy

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].

import IntervalTree, { Interval2D } from '@flatten-js/interval-tree';

// example of Interval2d tree which stores string values
const tree = new IntervalTree<string>();

// 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');
Copy

Constructor

Create a new instance of the interval tree. In TypeScript, you may optionally specify the value type V for stronger type hints.

// Without explicit value type (values default to unknown/any as inferred)
const tree = new IntervalTree();

// With explicit value type V
const treeStrings = new IntervalTree<string>();
const treeObjects = new IntervalTree<{ id: number; name: string }>();
Copy

Insert(key[, value])

Insert a new item into the tree. Key is an interval object or a pair of numbers [low, high] (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.

const node = tree.insert(key, value)
Copy

Exist(key[, value])

Returns true 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).

const existsKey = tree.exist(key)
const existsPair = tree.exist(key, value)
Copy

Remove(key[, value])

Removes entries from the tree.

• Called as remove(key), 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.

const removedNode = tree.remove(key)
const removedPairNode = tree.remove(key, value)
Copy

Search(interval[, outputMapperFn])

Returns array of values which keys intersected with given interval.

const resp = tree.search(interval)
Copy

Optional outputMapperFn(value, key) enables to map search results into custom defined output. Example:

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)' ]
Copy

Intersect_any(interval)

Returns true if intersection found between given interval and any of intervals stored in the tree

const found = tree.intersect_any(interval)
Copy

Size

Returns number of items stored in the tree (getter)

const size = tree.size
Copy

Keys

Returns tree keys in ascendant order (getter)

const keys = tree.keys
Copy

Values

Returns tree values in ascendant keys order (getter)

const values = tree.values
Copy

Items

Returns items in ascendant keys order (getter)

const items = tree.items
Copy

ForEach(visitor)

Enables to traverse the whole tree and perform operation for each item

tree.forEach( (key, value) => console.log(value) )
Copy

Map(callback)

Creates new tree with same keys using callback to transform (key,value) to a new value

let tree1 = tree.map((value, key) => (key.high-key.low))
Copy

Clear()

Clear tree

tree.clear()
Copy

Iterate([interval, outputMapperFn])

Returns an iterator (and iterable).
Call next 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.

let iterator = tree.iterate();
let next = iterator.next().value;
Copy

Optional outputMapperFn(value, key) enables to map search results into custom defined output.
Example:

let iterator = tree.iterate([5,5], (value, key) => key);
let next_key = iterator.next().value;
Copy

Supports for .. of syntax.
Example:

for (let key of tree.iterate([5,5], (value, key) => key)) {
    if (key[0] > 8) break;
    console.log(key);
}
Copy

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:

npm run docs
Copy

The output is written into the docs/ folder.

Tests

npm test
Copy

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