interval-tree-1d

A simple 1D interval tree. Supports O(log(n)) amortized updates and O(log(n)) queries.

Example

var createIntervalTree = require("interval-tree-1d")

//Create some random list of intervals
var intervals = [ [1, 2], [-1, 0], [0.5, 1], [-10, 10] ]

//Build tree
var tree = createIntervalTree(intervals)

//Find all intervals containing query point 0.7
console.log("querying point:", 0.7)
tree.queryPoint(0.7, function(interval) {
  console.log(interval)
})

API

var createIntervalTree = require("interval-tree-1d")

Constructor

`var tree = createIntervalTree(intervals)`

Constructs an interval tree given a list of intervals

Properties

`tree.count`

Returns the number of items in the tree

`tree.intervals`

Returns a list of all the intervals in the tree

`tree.insert(interval)`

Adds an interval to the tree

`tree.remove(interval)`

Removes an interval from the tree

`tree.queryPoint(p, visit(interval))`

Visits all intervals containing the point p

`tree.queryInterval(lo, hi, visit(interval))`

Returns all intervals which intersect the interval [lo, hi]

Credits

Current Tags

1.0.4 ... latest (3 years ago)

7 Versions

1.0.4 ... 3 years ago
1.0.3 ... 10 years ago
1.0.2 ... 10 years ago
1.0.1 ... 10 years ago
1.0.0 ... 11 years ago
0.0.1 ... 11 years ago
0.0.0 ... 11 years ago