class IntervalTree::Tree
Constants
- DEFAULT_OPTIONS
Attributes
top_node[R]
Public Class Methods
new(ranges, &range_factory)
click to toggle source
# File lib/interval_tree.rb, line 27 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
divide_intervals(intervals)
click to toggle source
# File lib/interval_tree.rb, line 34 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 < x_center s_left << k when k.first > 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(interval, options = {})
click to toggle source
# File lib/interval_tree.rb, line 56 def search(interval, options = {}) options = DEFAULT_OPTIONS.merge(options) return nil unless @top_node if interval.respond_to?(:first) first = interval.first last = interval.last else first = interval last = nil end if last result = Array.new (first...last).each do |j| search(j).each{|k|result << k} result.uniq! end result.sort_by{|x|[x.first, x.last]} else point_search(self.top_node, first, [], options[:unique]).sort_by{|x|[x.first, x.last]} end end
Private Instance Methods
center(intervals)
click to toggle source
augmented tree using a start point as resresentative value of the node
# File lib/interval_tree.rb, line 97 def center(intervals) i = intervals.reduce([intervals.first.first, intervals.first.last]) { |acc, int| [[acc.first, int.first].min, [acc.last, int.last].max] } i.first + (i.last - i.first) / 2 end
ensure_exclusive_end(ranges, range_factory)
click to toggle source
# File lib/interval_tree.rb, line 82 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 102 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 < node.x_center ) point_search(node.left_node, point, []).each{|k|result << k} end if node.right_node && ( point >= node.x_center ) point_search(node.right_node, point, []).each{|k|result << k} end if unique result.uniq else result end end