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

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