An implementation of the centered interval tree algorithm in Ruby.
2020-11-09, contribution by Brendan Weibrecht, Chris Nankervis and Thomas van der Pol
- Substantially improved performance when supplied with a large range as the search query.
2017-05-12, contribution by Sam Davies
- User can specify an option in search
unique: falseif s/he wants multiple matches to be returned.
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_endconstructs 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#initializewhile maintaining perfect backward compatibility. Search in empty trees failing
- Adds a nil guard in
Tree#searchto protect against empty tree searches failing.
- Cosmetic improvements: Language & whitespace in specs, Gemfile addition, and .gitignore update
$ gem install fast_interval_tree
See spec/interval_tree_spec.rb for details.
require "interval_tree" itv = [(0...3), (1...4), (3...5), (0...3)] t = IntervalTree::Tree.new(itv) p t.search(2) #=> [0...3, 1...4] p t.search(2, unique: false) #=> [0...3, 0...3, 1...4] p t.search(1...4) #=> [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
Two-dotted full-closed intervals
(first..last) are also accepted and internally
converted to half-closed intervals.
Author: MISHIMA, Hiroyuki ( https://github.com/misshie ), Simeon Simeonov ( https://github.com/ssimeonov ), Carlos Alonso ( https://github.com/calonso ), Sam Davies ( https://github.com/samphilipd ), Brendan Weibrecht (https://github.com/ZimbiX), Chris Nankervis (https://github.com/chrisnankervis), Thomas van der Pol (https://github.com/tvanderpol).
Copyright: (c) 2011-2020 MISHIMA, Hiroyuki; Simeon Simeonov; Carlos Alonsol; Sam Davies; Brendan Weibrecht; Chris Nankervis; Thomas van der Pol
License: The MIT/X11 license