shinout / interval-tree Goto Github PK

View Code? Open in Web Editor NEW

35.0 4.0 17.0 151 KB

interval tree in javascript

License: MIT License

JavaScript 100.00%

interval-tree's Introduction

interval-tree

interval tree in JavaScript

this repository is no more maintenanced. use interval-tree2

Installation

git clone git://github.com/shinout/interval-tree.git

OR

npm install interval-tree

Usage

var IntervalTree = require('interval-tree');

// add interval data

var itree = new IntervalTree(300); // 300 : the center of the tree

itree.add([22, 56,  'foo']);
itree.add([44, 199, 'bar']);

// search 1: get overlapped regions from one point
var results = itree.search(103);

results.forEach(function(result) {
  console.log(result.data); // overlapped range data
  console.log(result.id);   // id of the overlapped range
});

// search 2: get overlapped regions from a range
var results2 = itree.search(103, 400);

results2.forEach(function(result) {
  console.log(result.data);  // overlapped range data
  console.log(result.id);    // id of the overlapped range
  console.log(result.rate1); // overlapped rate to the given range
  console.log(result.rate2); // overlapped rate to the range of this result
});

interval-tree's People

Contributors

Stargazers

Watchers

Forkers

pygy codermak anujsrc traksewt kborders01 popham mlaveau zj8487 sambaran69 sebamarynissen circlingthesun occidens azhao12345 b3nj4m ruaneg jaredlunde

interval-tree's Issues

Small range raises stack overflow

Changing the readme example to:

var Tree = require('interval-tree');
var itree = new Tree(300);
itree.add([22, 43, 'foo']);

Will raise a Maximum call stack size exceeded in SortedList.js:26:17.
Is there something wrong with this code?

ps. [email protected]

Maximum call stack exceeded on floating points

I get

node_modules/sortedlist/SortedList.js:26
      if (Array.isArray(val)) {
                ^
RangeError: Maximum call stack size exceeded

when I run

var Tree = require('interval-tree');
var itree = new Tree(5);
var a = [0,1,2,3,4,6,7,8,9,9.6,10];
for (var i = 1; i < a.length; i++) {
    itree.add([a[i-1], a[i], a[i]]);
}

whereas

var Tree = require('interval-tree');
var itree = new Tree(5);
var a = [0,1,2,3,4,6,7,8,9,10];
for (var i = 1; i < a.length; i++) {
    itree.add([a[i-1], a[i], a[i]]);
}

runs fine, even with a = [0,1,2,3,4,6,7,8,9,10,11,12,13,14] etc.
Tried to debug this in Chrome as well, and it seems that _insert is called a lot, causing the stack overflow, so I think it is an issue with the interval-tree, rather than with the sortedlist module.

cannot query under the lowest value

var t = new IntervalTree( 5 );
t.add( 3, 5, ''a'' );
t.search( 1, 2 );

TypeError: Cannot read property '0' of undefined

get RangeError when adding interval with 1073741824 / 1073741825

The following line produces a RangeError:

new IntervalTree(1).add([1073741824, 1073741825, 'hello']);

The exact error in Chrome is:

Uncaught RangeError: Maximum call stack size exceeded - SortedList.js:26

Project crash on its own tests

Project crash on its own tests.
I'm using node 0.10.20 and installing from npm.

user@host:~$ cd /tmp
user@host:/tmp$ npm install interval-tree
npm http GET https://registry.npmjs.org/interval-tree
npm http 304 https://registry.npmjs.org/interval-tree
npm http GET https://registry.npmjs.org/sortedlist
npm http 304 https://registry.npmjs.org/sortedlist
[email protected] node_modules/interval-tree
└── [email protected]
user@host:/tmp$ cd node_modules/interval-tree/
user@host:/tmp/node_modules/interval-tree$ node --version
v0.10.20
user@host:/tmp/node_modules/interval-tree$ npm view interval-tree version
0.0.2
user@host:/tmp/node_modules/interval-tree$ node test.js 

/tmp/node_modules/interval-tree/IntervalTree.js:154
    node.starts.arr.map(function(itvl) { arr.push(itvl.result()) });
                    ^
TypeError: Cannot call method 'map' of undefined
    at IntervalTree._pointSearch (/tmp/node_modules/interval-tree/IntervalTree.js:154:21)
    at IntervalTree.search (/tmp/node_modules/interval-tree/IntervalTree.js:80:18)
    at test (/tmp/node_modules/interval-tree/test.js:28:25)
    at Object.<anonymous> (/tmp/node_modules/interval-tree/test.js:71:3)
    at Module._compile (module.js:456:26)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Function.Module.runMain (module.js:497:10)
    at startup (node.js:119:16)

Zero-fill right shift issue

great job, but I have a suggestion

new Node((itvl.start + itvl.end) >>> 1);

is quite good untill

(itvl.start + itvl.end) <== 4294967295

because

4294967296 >>> 1 === 0
4294967297 >>> 1 === 0
4294967298 >>> 1 === 1
4294967299 >>> 1 === 1
4294967300 >>> 1 === 2

and so on

Self Balancing Feature?

A self balancing feature would be nice / a way to initialize the tree w/ an unsorted array

remove range?

:-)

/**
 * remove: 
 **/
IntervalTree.prototype.remove = function(interval_id) {
};