# interval-query

interval-query is a Node.js module for storing number intervals and offers two different query methods: segment tree and sequential. The main purpose of this module is to solve the following problem: given a set of intervals, how to find all overlapping intervals.

## Installation

```
npm install query-interval
```

## Example

`var intervals = ; var tree = ; tree;tree;tree;tree;console;`

## Segment tree

One method to query for overlapping intervals is to use a Segment tree. The usage is as in the example above: we build a new tree object, push intervals to the data structure, build the tree and can then run certain queries on the tree. The segment tree is a static structure which means we cannot add further intervals once the tree is built. Rebuilding the tree is then required.

## Sequential

The sequential algorithm simply traverses the array of intervals to search for overlaps. It builds up a dynamic structure where intervals can be added at any time. The interface is similar to the segment tree, but without tree specific methods. Example:

`var intervals = ; var sequ = ; sequ;sequ;sequ;console;sequ;console;`

## API

### Segment tree and Sequential

##### pushInterval(from, to)#####

Push interval to interval stack.

`from`

: interval start (number).`to`

: interval end (number).

##### pushArray(from, to, validate)#####

Push array of intervals.

`from`

: interval start points (array).`to`

: interval end points (array).`validate`

: validate intervals (boolean, default: true).

##### clearIntervalStack()#####

Clear the interval stack.

##### queryPoint(point, resultFn)#####

Query single point.

`point`

: (number).`resultFn`

: result array of intervals (function).*Returns*overlapping intervals (number).

##### queryPointArray(points, resultFn, validate)#####

Query multiple points.

`points`

: (array).`resultFn`

: result array of intervals (function).`validate`

: validate points (boolean, default: true).*Returns*overlapping intervals (number).

##### queryInterval(from, to, options)#####

Query single interval.

`from`

: interval start (number).`to`

: interval end (number).`options`

: (object).`endpoints`

: include endpoints of interval in comparison, e.g. (1, 2) overlaps with (2, 3) (boolean, default: true).`resultFn`

: result array of intervals (function).

*Returns*overlapping intervals (number).

##### queryIntervalArray(from, to, options)#####

Query multiple intervals.

`from`

: interval start points (array).`to`

: interval end points (array).`options`

: (object).`endpoints`

: include endpoints of interval in comparison, e.g. (1, 2) overlaps with (2, 3) (boolean, default: true).`resultFn`

: result array of intervals (function).`validate`

: validate intervals (boolean, default: true).

*Returns*overlapping intervals (number).

##### queryOverlap()#####

Query overlapping intervals for all intervals of the stack.

*Returns*intervals (array).`id`

: interval id (number).`from`

: interval start (number).`to`

: interval end (number).`overlap`

: overlapping interval ids (array).

### Segment tree only

##### buildTree()#####

Build tree structure.

##### printTree()#####

Prints tree to console.

##### printTreeTopDown()#####

Prints tree to console top down.

## Performance

Detailed performance analysis in this blog post: http://www.chasinclouds.com/2012/02/segment-tree-implementation-in.html

## Licence

Use of this source code is governed by a MIT-style license that can be found in the LICENSE file.