Range/Segment Tree Ruby

Question

I am looking for a range or segment tree implementation in Ruby. I could not find any sample or gem available.

Does anyone have a sample code ?

Thanks,

Answer 1

There looks to be one called interval-tree, repo is here, https://github.com/gam3/interval-tree and here https://github.com/misshie/interval-tree. It seems like it is the later who made the thing, but the gem on rubygems points to the first. Very strange.

The documentation is wrong on the repo and everywhere else. To use it, use either IntervalTree::InclusiveTree.new or IntervalTree::ExclusiveTree.new. This is not documented anywhere which is strange. Also, equally strange, it is not possible to add issues to the github repo to fix this. I am considering forking and making a new version which can be maintained by the community.

Anyways, here is how you use it:

require "interval-tree"

itv = [(0...3), (1...4), (3...5),]
t = IntervalTree::Tree.new(itv)
p t.search(2) => [0...3, 1...4]
p t.search(1...3) => [0...3, 1...4, 3...5]

As you see, also the require statement is wrongly documented in the repo. What a mess.

Answer 2

This Github repo is...um...the fourth hit down on Google for 'ruby interval tree'.