An interval tree used to find interval inclusion for arbitrary points and ranges. This library utilizes an augmented AVL tree for O(log(n)) insertion, removal, and querying.
From rubygems.org:
gem install itree
Insertions of ranges can be made with any type that defines <=>, <, >, and == operators. Insertions can be accompanied by an optional data object that will be saved along with the range.
require 'rubygems'
require 'itree'
tree = Intervals::Tree.new
t.insert(0,100)
t.insert(50,500)
t.insert(90,200,"this data is saved with the range")A stabbing query returns an array of Intervals::Node ranges that fully contain the desired point or range.
require 'rubygems'
require 'itree'
tree = Intervals::Tree.new
t.insert(0,100)
t.insert(50,500)
results = t.stab(5)
results.length # => 1
results[0].scores # => [0,100]
results = t.stab(55)
results.length # => 2
results[0].scores # => [0,100]
results[1].scores # => [50,500]
results = t.stab(10,20)
results.length # => 1
results[0].scores # => [0,100]
results = t.stab(10,200)
results.length # => 0Ranges are removed by directly removing the desired range.
require 'rubygems'
require 'itree'
tree = Intervals::Tree.new
t.insert(0,100)
t.insert(50,500)
t.size # => 2
t.remove(0,100)
t.size # => 1- Interval Trees on Wikipedia
- interval-tree gem by @misshie - An implementation that utilizes Ruby ranges but does not allow dynamic insertion and removal on an existing object.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent