# @flatten-js/interval-tree

Interval search tree

## Usage no npm install needed!

``````<script type="module">
import flattenJsIntervalTree from 'https://cdn.skypack.dev/@flatten-js/interval-tree';
</script>``````

# 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, in package flatten-interval-tree, is no longer supported and will be deprecated soon. Please use this package (@flatten-js/interval-tree) instead.

## Installation

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

## Usage

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

### Notes

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

Interval can be simply a pair of numbers or it can be a user-defined object that implements `IntervalInterface` described in typescript declaration file `index.d.ts`.

Axis aligned rectangle is an example of such interval. We may look at rectangle as an interval between its low left and top right corners. See Box class in flatten-js library as an example of `IntervalInterface` implementation.

### Example

``````let tree = new IntervalTree();

let intervals = [[6,8],[1,4],[5,12],[1,1],[5,7]];

// Insert interval as a key and string "val0", "val1" etc. as a value
for (let i=0; i < intervals.length; i++) {
tree.insert(intervals[i],"val"+i);
}

// Get array of keys sorted in ascendant order
let 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
let values_in_range = tree.search([2,3]);     //  expected array ['val1']
``````

### Constructor

Create new instance of interval tree

``````let tree = new IntervalTree()
``````

### Insert(key[, value])

Insert new item into the tree. Key is an interval object or pair of numbers [low, high].
Value may represent any value or reference to any object. If value omitted, tree will store and retrieve keys as values.
Method returns reference to the inserted node

``````let node = tree.insert(key, value)
``````

### Exist(key,value)

Method returns true if item {key, value} exists in the tree.
Method may be useful if need to support unique items.

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

``````let removed = tree.remove(key, value)
``````

### Search(interval[, outputMapperFn])

Returns array of values which keys intersected with given interval.

``````let resp = tree.search(interval)
``````

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 (let 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)' ]
``````

### Intersect_any(interval)

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

``````let found = tree.intersect_any(interval)
``````

### Size

Returns number of items stored in the tree (getter)

``````let size = tree.size
``````

### Keys

Returns tree keys in ascendant order (getter)

``````let keys = tree.keys
``````

### Values

Returns tree values in ascendant keys order (getter)

``````let values = tree.values
``````

### Items

Returns items in ascendant keys order (getter)

``````let items = tree.items
``````

### ForEach(visitor)

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

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

### 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))
``````

## Documentation

Documentation may be found here: https://alexbol99.github.io/flatten-interval-tree

## Tests

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