IntervalTree¶ ↑

An implementation of the agumented interval tree algorithm in Ruby

• description in Wikipedia en.wikipedia.org/wiki/Interval_tree

• an implementstion in Python by Tyler Kahn forrst.com/posts/Interval_Tree_implementation_in_python-e0K

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]

Result intervals are always returned in the “left-closed and right-open” style that can be expressed by three-dotted Range object literals (first…last)

Full-closed intervals “(first..last)” for tree are internally converted to half-closed intervals.

Author

MISHIMA, Hiroyuki ( github.com/misshie )

Copyright

© 2011, MISHIMA, Hiroyuki

License

The MIT/X11 license