class IntervalTree::Tree
Constants
- DEFAULT_OPTIONS
Search by range or point
Attributes
top_node[R]
Public Class Methods
new(ranges, &range_factory)
click to toggle source
# File lib/interval_tree.rb, line 6 def initialize(ranges, &range_factory) range_factory = lambda { |l, r| (l ... r+1) } unless block_given? ranges_excl = ensure_exclusive_end([ranges].flatten, range_factory) @top_node = divide_intervals(ranges_excl) end
Public Instance Methods
==(other)
click to toggle source
# File lib/interval_tree.rb, line 50 def ==(other) top_node == other.top_node end
divide_intervals(intervals)
click to toggle source
# File lib/interval_tree.rb, line 13 def divide_intervals(intervals) return nil if intervals.empty? x_center = center(intervals) s_center = Array.new s_left = Array.new s_right = Array.new intervals.each do |k| case when k.last.to_r < x_center s_left << k when k.first.to_r > x_center s_right << k else s_center << k end end Node.new(x_center, s_center, divide_intervals(s_left), divide_intervals(s_right)) end
search(query, options = {})
click to toggle source
# File lib/interval_tree.rb, line 36 def search(query, options = {}) options = DEFAULT_OPTIONS.merge(options) return nil unless @top_node if query.respond_to?(:first) result = top_node.search(query) options[:unique] ? result.uniq : result else point_search(self.top_node, query, [], options[:unique]) end .sort_by{|x|[x.first, x.last]} end
Private Instance Methods
center(intervals)
click to toggle source
# File lib/interval_tree.rb, line 69 def center(intervals) ( intervals.map(&:begin).min.to_r + intervals.map(&:end).max.to_r ) / 2 end
ensure_exclusive_end(ranges, range_factory)
click to toggle source
# File lib/interval_tree.rb, line 56 def ensure_exclusive_end(ranges, range_factory) ranges.map do |range| case when !range.respond_to?(:exclude_end?) range when range.exclude_end? range else range_factory.call(range.first, range.end) end end end
point_search(node, point, result, unique = true)
click to toggle source
# File lib/interval_tree.rb, line 76 def point_search(node, point, result, unique = true) node.s_center.each do |k| if k.include?(point) result << k end end if node.left_node && ( point.to_r < node.x_center ) point_search(node.left_node, point, []).each{|k|result << k} end if node.right_node && ( point.to_r >= node.x_center ) point_search(node.right_node, point, []).each{|k|result << k} end if unique result.uniq else result end end