1.3.0 • Published 8 years ago

static-interval-tree v1.3.0

Weekly downloads
76
License
-
Repository
github
Last release
8 years ago

Static interval tree

A very simple library for finding overlapping intervals in one dimension.

The intervals are indexed using an augmented balanced binary search tree. The search tree is bulk-loaded by sorting. There's no support for adding/removing intervals.

Intervals are assumed to be over integers. Coordinates can be closed start, end, or half-open [start, end).

Query time with the index should be O(log n + k), (k being number of matches returned) rather than the O(n) required for a brute-force search.

Work in progress. Might be useful for drawing genomic data.

Methods

var {index, matches} = require('static-interval-tree');

// index(intervals :: [{start, end, ...}, ...]) :: interval-tree

var idx = index([{start: 10, end: 12, id: 1}, {start: 21, end: 30: id: 2}]);

// matches(interval-tree, pos :: {start, end}) :: [{start, end, ...}, ...]

var overlapping = matches(idx, {start: 12, end: 22});
// => [{start: 10, end: 12, id: 1}, {start: 21, end: 30: id: 2}]

// matching half-open coords, [start, end)
// matches01(interval-tree, pos :: {start, end}) :: [{start, end, ...}, ...]

var overlapping = matches01(idx, {start: 12, end: 22});
// => [{start: 21, end: 30: id: 2}]

Note that building the tree is independent of the choice of closed or half-open coordinates, however you should use match01 if your coordinates are half-open. The intervals in the tree and the interval for query must use the same coordinate system, either closed or half-open.

Build

The build is based on npm and webpack.

Lint

Use npm run lint to run the lint rules. We lint with eslint and babel-eslint.

References

1.3.0

8 years ago

1.2.0

8 years ago

1.1.0

8 years ago

1.0.3

9 years ago

1.0.2

9 years ago

1.0.1

9 years ago

1.0.0

9 years ago