search

mgechev / javascript-algorithms

💻 JavaScript implementations of computer science algorithms
https://mgechev.github.io/javascript-algorithms/
MIT License
7.83k stars 1.27k forks source link

Bug in interval-tree.js #112

Closed pkerpedjiev closed 7 years ago

pkerpedjiev commented 7 years ago

Great library, but I think there's a bug in the IntervalTree implementation. Consider the following snippet:

it = new IntervalTree()
it.add([10383734, 10594186])
it.add([9495571, 9677853])

it.add([9303743, 9404967])
it.intersects([9303743, 9303744])

This should logically return true, right? The intersection test clearly overlaps the last added interval. Running this, however, yields false. If either of the first two add statements are removed, the intersection check at the end returns true as expected.

mgechev commented 7 years ago

Yes, it seems like there's an issue. I'll take a look at the implementation when I find some spare time. A PR will also be appreciated, if you don't mind digging into the code.

pkerpedjiev commented 7 years ago

Added a PR (#114) with a fix and some tests. Seems to work for me.

Looks like the max value wasn't being properly set for newly added nodes.