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