class TimeFrame::Collection
This collection supports the concept of interval trees to improve the access speed to intervals (or objects containing intervals) intersecting given time_frames or covering time elements
Public Class Methods
new(item_list = [], sorted = false, &block)
click to toggle source
# File lib/time_frame/collection.rb, line 10 def initialize(item_list = [], sorted = false, &block) block ||= ->(item) { item } @tree_nodes = item_list.map do |item| TreeNode.new(item: item, &block) end build_tree(sorted) if @tree_nodes.any? end
Public Instance Methods
all_covering(time)
click to toggle source
# File lib/time_frame/collection.rb, line 24 def all_covering(time) all_matching { |element| element.cover? time } end
all_intersecting(time_frame)
click to toggle source
# File lib/time_frame/collection.rb, line 28 def all_intersecting(time_frame) all_matching { |element| element.overlaps? time_frame } end
each(&block)
click to toggle source
# File lib/time_frame/collection.rb, line 18 def each(&block) @tree_nodes.each do |node| block.call(node.item) end end
Private Instance Methods
add_matching(node, result, &matcher)
click to toggle source
# File lib/time_frame/collection.rb, line 64 def add_matching(node, result, &matcher) return unless node && matcher.call(node.child_time_frame) add_matching(node.left_child, result, &matcher) result << node.item if matcher.call(node.time_frame) add_matching(node.right_child, result, &matcher) end
all_matching(&matcher)
click to toggle source
# File lib/time_frame/collection.rb, line 34 def all_matching(&matcher) [].tap do |result| add_matching(@root, result, &matcher) if any? end end
build_sub_tree(lower, upper, ancestor = nil, side = nil)
click to toggle source
# File lib/time_frame/collection.rb, line 52 def build_sub_tree(lower, upper, ancestor = nil, side = nil) mid = (lower + upper) / 2 node = @tree_nodes[mid] node.update_ancestor_relation(ancestor, side) if ancestor && side build_sub_tree(lower, mid - 1, node, :left) unless lower == mid build_sub_tree(mid + 1, upper, node, :right) unless upper == mid node.update_child_frame(node.child_time_frame) if lower == upper end
build_tree(sorted)
click to toggle source
# File lib/time_frame/collection.rb, line 46 def build_tree(sorted) sort_nodes unless sorted build_sub_tree(0, @tree_nodes.size - 1) @root = @tree_nodes[(@tree_nodes.size - 1) / 2] end
sort_nodes()
click to toggle source
# File lib/time_frame/collection.rb, line 40 def sort_nodes @tree_nodes.sort_by! do |item| [item.time_frame.min, item.time_frame.max] end end