flatten-interval-tree

flatten-interval-tree

Implementation of the interval binary search tree according to Cormen et al. Introduction to Algorithms (2009, Section 14.3: Interval trees, pp. 348–354).

This version is beta

Installation

npm install --save flatten-interval-tree

Usage

import IntervalTree from 'flatten-interval-tree'

API Reference

Constructor

Create new instance of interval tree

let tree = new IntervalTree()

Insert(key, value)

Insert new item into the tree. Key is and interval object or an array of [low, high] numeric values.
Value may represent any value or refer to any object. If value omitted, tree will store and retrieve keys only.
If key is an object, it should expose low and high properties and implement the following methods: less_than, equal_to, intersect, clone, output, maximal_val, val_less_than.
Method returns reference to the inserted node

let node = tree.insert(key, value)

Exist(key,value)

Method returns true if item {key, value} exists in the tree.
Method may be useful if need to support unique items.

let exist = tree.exist(key, value)

Remove(key, value)

Removes item from the tree. Returns true if item was actually deleted, false if not found

let removed = tree.remove(key, value)

Search(interval)

Returns array of values which keys intersected with given interval.
If tree stores only keys with no values, search returns array of keys which intersect given interval

let resp = tree.search(interval)

Size (getter)

Returns number of items stored in the tree

let size = tree.size

ForEach(visitor)

Enables to traverse the whole tree and perform operation for each item

tree.forEach( (key, value) => console.log(value) )

Documentation

Documentation may be found here: https://alexbol99.github.io/flatten-interval-tree

Tests

npm test

Contributors

In lieu of a formal style guide, take care to maintain the existing coding style. Add unit tests for any new or changed functionality. Lint and test your code.

License

MIT