flatten-interval-tree

Interval Tree implementation as augmented binary red-black tree

Downloads in past

Stats

StarsIssuesVersionUpdatedCreatedSize
flatten-interval-tree
39110.2.35 years ago7 years agoMinified + gzip package size for flatten-interval-tree in KB

Readme

Interval Tree
npm version Build Status Interval Tree implementation as it is described in Cormen et al. (2009, Section 14.3: Interval trees, pp. 348–354).

Important note

This package is not supported and will be deprecated soon. Consider moving to the scoped version @flatten-js/interval-tree.

Contacts

Follow me on Twitter @alexbol

Installation

```bash npm install flatten-interval-tree -save ```

Usage

```js let IntervalTree = require('flatten-interval-tree'); ```

API Reference

Constructor

Create new instance of interval tree ```js 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: lessthan, equalto, intersect, clone, output, maximalval, vallessthan.
Method returns reference to the inserted node ```js let node = tree.insert(key, value); ```

Exist(key,value)

Method returns true if entry {key, value} exists in the tree.
Method may be useful if need to support unique items. ```js 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 ```js 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 ```js let resp = tree.search(interval); ```

Size (getter)

Returns number of items stored in the tree ```js let size = tree.size; ```

ForEach(visitor)

Enables to traverse the whole tree and perform operation for each item ```js tree.forEach( (key, value) => console.log(value) ) ```

Tests

```bash 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