augmented-interval-tree

!Dependencies


Augmented interval tree implementation with no dependencies.

Basic Usage

augmented-interval-tree exports a single IntervalTree constructor. After constructing an interval tree instance, intervals can be added to the tree using the insert() method. The tree can be queried using the find() method.

``javascript
const IntervalTree = require('augmented-interval-tree');
const tree = new IntervalTree();
let results;

tree.insert(5, 10, 'foo');
tree.insert(1, 2, 'bar');
tree.insert(3, 7, 'baz');
tree.insert(15, 15);

// Match all intervals.
results = tree.find(1, 20);
/*
results equals [
{ start: 5, end: 10, data: 'foo' },
{ start: 1, end: 2, data: 'bar' },
{ start: 3, end: 7, data: 'baz' },
{ start: 15, end: 15, data: undefined }
].
*/

// Match single point.
results = tree.find(15);
// results equals [{ start: 15, end: 15, data: undefined }].

// No matches.
results = tree.find(11, 14);
// results equals [].

results = tree.find(4, 6);
/*
results equals [
{ start: 5, end: 10, data: 'foo' },
{ start: 3, end: 7, data: 'baz' }
].
*/
`

API

$3

- Arguments
- None

Constructs a new augmented interval tree instance. Must be called with new.

$3

- Arguments
- start (number) - The interval's starting value (inclusive).
- end (number) - The interval's ending value (inclusive).
- data (value) - Optional data to store with the interval. Defaults to undefined.
- Returns
- Nothing

Inserts an interval into the tree. The interval spans from start (inclusive) to end (inclusive). data can be used to optionally store metadata with the interval.

$3

- Arguments
- start (number) - The query interval's starting value (inclusive).
- end (number) - The query interval's ending value (inclusive). Defaults to start, meaning that the query searches for all intervals containing a specific value.
- Returns
- matches (array of objects) - An array of intervals, where each interval adheres to the following schema:
- start (number) - The interval's starting value.
- end (number) - The interval's ending value.
- data (value) - Any data stored with the interval.

Returns all intervals in the tree that overlap with the interval of [start, end]`.