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

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