lib/patches/patch_interval_tree.rb
module Patches
module PatchIntervalTree
module ForTree
def divide_intervals(intervals)
return nil if intervals.empty?
x_center = center(intervals)
s_center = []
s_left = []
s_right = []
intervals.each do |k|
case
when k.end && k.end != Float::INFINITY && k.end.to_r < x_center
s_left << k
when k.begin && k.begin.to_r > x_center
s_right << k
else
s_center << k
end
end
IntervalTree::Node.new(x_center, s_center, divide_intervals(s_left), divide_intervals(s_right))
end
def search(query, options = {})
options = IntervalTree::Tree::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(top_node, query, [], options[:unique])
end
.sort_by{|x| [x.begin || -Float::INFINITY, x.end || Float::INFINITY] }
end
private
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.begin, range.end)
end
end
end
def center(intervals)
min_val = intervals.map(&:begin).compact.min
max_val = intervals.map(&:end).compact.max
return min_val * 2 if max_val == nil
return max_val / 2 if min_val == nil
return (min_val.to_r + max_val.to_r) / 2
end
end
module ForNode
def search_s_center(query)
s_center.select do |range|
# when this range is smaller than and not overlaps with `query`
# range query
# |---------| |---------|
if query.begin and range.end
next false if query.begin > range.end
next false if query.begin == range.end and range.exclude_end?
end
# when this range is larger than and not overlaps with `query`
# query range
# |---------| |---------|
if query.end and range.begin
next false if query.end < range.begin
next false if query.end == range.begin and query.exclude_end?
end
next true
end
end
end
end
end
module IntervalTree
class Tree
prepend Patches::PatchIntervalTree::ForTree
end
class Node
prepend Patches::PatchIntervalTree::ForNode
end
end