Skip to content
A data structure for storing intervals and finding overlaps with either segment tree or sequential query
JavaScript
Find file
Latest commit 4978a6b Jul 11, 2014 @toberndo Merge pull request #1 from dwilhelm89/patch-1
npm package name was inverse
Failed to load latest commit information.
lib 0.3.0 Feb 29, 2012
test 0.3.0 Feb 29, 2012
.gitignore npm publish Feb 22, 2012
History.md 0.3.0 Feb 29, 2012
LICENSE Copyright Feb 22, 2012
Makefile 0.3.0 Feb 29, 2012
Readme.md npm package name was inverse ;-) Jul 11, 2014
index.js initial commit Feb 21, 2012
package.json 0.3.0 Feb 29, 2012

Readme.md

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 interval-query

Example

var intervals = require('interval-query');

var tree = new intervals.SegmentTree;

tree.pushInterval(1, 5);
tree.pushInterval(2, 7);
tree.pushInterval(3, 6);
tree.buildTree();
console.log(tree.queryOverlap());

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.

segment tree example

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 = require('interval-query');

var sequ = new intervals.Sequential;

sequ.pushInterval(1, 5);
sequ.pushInterval(2, 7);
sequ.pushInterval(3, 6);
console.log(sequ.queryInterval(6, 8));
sequ.pushInterval(6.5, 7.33);
console.log(sequ.queryInterval(6, 8));

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.

Something went wrong with that request. Please try again.