class IntervalTree::Node

def ==(other)
  x_center == other.x_center &&
  s_center == other.s_center &&
  left_node == other.left_node &&
  right_node == other.right_node
end

def initialize(x_center, s_center, left_node, right_node)
  @x_center = x_center
  @s_center = s_center
  @left_node = left_node
  @right_node = right_node
end

def search(query)
  search_s_center(query) +
    (left_node && query.begin.to_r < x_center && left_node.search(query) || []) +
    (right_node && query.end.to_r > x_center && right_node.search(query) || [])
end

def search_s_center(query)
  s_center.select do |k|
    (
      # k is entirely contained within the query
      (k.begin >= query.begin) &&
      (k.end <= query.end)
    ) || (
      # k's start overlaps with the query
      (k.begin >= query.begin) &&
      (k.begin < query.end)
    ) || (
      # k's end overlaps with the query
      (k.end > query.begin) &&
      (k.end <= query.end)
    ) || (
      # k is bigger than the query
      (k.begin < query.begin) &&
      (k.end > query.end)
    )
  end
end