class RangeTree::Tree
Attributes
children[RW]
ends[RW]
rebuild_on_add[RW]
root[RW]
starts[RW]
Public Class Methods
new(rebuild_on_add=true)
click to toggle source
# File lib/range_tree.rb, line 8 def initialize(rebuild_on_add=true) self.children = [] self.rebuild_on_add = rebuild_on_add self.starts = Hash.new{|h,k| h[k] = []} self.ends = Hash.new{|h,k| h[k] = []} end
Public Instance Methods
>>(value)
click to toggle source
# File lib/range_tree.rb, line 27 def >>(value) remove(value) end
[](index)
click to toggle source
# File lib/range_tree.rb, line 65 def [](index) return nil unless self.root case index when Range self.root.search_range(index).map(&:value) when Fixnum self.root.search(index).map(&:value) else raise "Unexpected index type #{index.class}" end end
[]=(min, max, value)
click to toggle source
# File lib/range_tree.rb, line 23 def []=(min, max, value) add(min, max, value) end
add(min, max, value)
click to toggle source
# File lib/range_tree.rb, line 15 def add(min, max, value) node = Node.new(min, max, value) self.children << node self.starts[min] << node self.ends[max.respond_to?(:succ) ? max.succ : max + 1] << node self.rebuild if self.rebuild_on_add end
all(&block)
click to toggle source
# File lib/range_tree.rb, line 61 def all &block iterate(self.starts.keys.min..self.ends.keys.max).each(&block) end
distinct(&block)
click to toggle source
# File lib/range_tree.rb, line 57 def distinct &block iterate([*self.starts.keys, *self.ends.keys].uniq.sort).each(&block) end
inspect()
click to toggle source
# File lib/range_tree.rb, line 85 def inspect "#{self}" end
max()
click to toggle source
# File lib/range_tree.rb, line 35 def max self.root && self.root.max end
min()
click to toggle source
# File lib/range_tree.rb, line 31 def min self.root && self.root.min end
rebuild()
click to toggle source
# File lib/range_tree.rb, line 48 def rebuild current_level = self.children.sort_by(&:mid_point) current_level = current_level.each_slice(2).map do |pair| Node.new(pair.map(&:min).min, pair.map(&:max).max, pair) end while current_level.length > 1 self.root = current_level.first end
remove(value)
click to toggle source
# File lib/range_tree.rb, line 39 def remove(value) return unless node_to_remove = self.children.find{|child| child.value == value} self.children.delete(node_to_remove) self.starts[node_to_remove.min].delete(node_to_remove) self.ends[node_to_remove.max].delete(node_to_remove) self.rebuild if self.rebuild_on_add return node_to_remove.min..node_to_remove.max end
to_s()
click to toggle source
# File lib/range_tree.rb, line 77 def to_s if self.root "RangeTree[#{root.min}..#{root.max}]" else "RangeTree[empty]" end end
Private Instance Methods
iterate(range)
click to toggle source
# File lib/range_tree.rb, line 90 def iterate(range) return [] unless self.root collection = Set.new(self.root.search(range.first)) Enumerator.new do |enum| range.each do |current_point| self.ends[current_point].each{|node| collection.delete(node)} if self.ends.include?(current_point) self.starts[current_point].each{|node| collection << node } if self.starts.include?(current_point) enum.yield current_point, collection.map(&:value) end end end