Created: 2011-07-11 07:52
Updated: 2018-07-10 13:09
License: mit

IntervalTree vesion 0.1.1

An implementation of the augmented interval tree algorithm in Ruby

See also


2017-05-12, contribution by Sam Davies ( )

  • User can specify an option in search unique: false if s/he wants multiple matches to be returened.

2015-11-02, contribution by Carlos Alonso ( )

  • Improved centering
  • Fixed searching: With some use cases with very large trees, the library fails to find intervals.
  • Added rubygems structure to be able to be pushed as a gem

2013-04-06, contribution by Simeon Simeonov ( )

  • Range factory: The current design allows for Range-compatible elements to be added except for the case where Tree#ensure_exclusive_end constructs a Range in a private method. In keeping with good design practices of containers such as Hash, this pull requests allows for a custom range factory to be provided to Tree#initialize while maintaining perfect backward compatibility. Search in empty trees failing
  • Adds a nil guard in Tree#search to protect against empty tree searches failing.
  • Cosmetic improvements: Language & whitespace in specs, Gemfile addition, and .gitignore update


$ gem install augmented_interval_tree


See spec/interval_tree_spec.rb for details.

require "interval_tree"

itv = [(0...3), (1...4), (3...5), (0...3)]
t =
p     #=> [0...3, 1...4]
p, unique: false) #=> [0...3, 1...4, 0...3]
p #=> [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)

Two-dotted full-closed intervals (first..last) are also accepted and internally converted to half-closed intervals.


Author: MISHIMA, Hiroyuki ( ), Simeon Simeonov ( ), Carlos Alonso ( ), Sam Davies ( ).

Copyright: (c) 2011-2017 MISHIMA, Hiroyuki; Simeon Simeonov; Carlos Alonsol; Sam Davies

License: The MIT/X11 license

Cookies help us deliver our services. By using our services, you agree to our use of cookies Learn more