IntervalTree vesion 0.1.1
An implementation of the augmented interval tree algorithm in Ruby
- description in Wikipedia http://en.wikipedia.org/wiki/Interval_tree
- an implementation in Python by Tyler Kahn http://forrst.com/posts/Interval_Tree_implementation_in_python-e0K (broken link)
- User can specify an option in search
unique: falseif s/he wants multiple matches to be returened.
- 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
- 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 augmented_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, 1...4, 0...3] 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.
Copyright: (c) 2011-2017 MISHIMA, Hiroyuki; Simeon Simeonov; Carlos Alonsol; Sam Davies
License: The MIT/X11 license