Range Count Tree For problems like given n ranges, find the interval when maximum ranges intersect

range_count_tree.rb

# RangeCountTree
# A bst variant for fast retrieval of count of ranges which are intersecting given n ranges
#
# Creator : Shadab Ahmed
#
# Each node stores a range and the count of intervals which intersect with the range.
#
# We just follow these rules:
# 1. Any range which is greater than the current range is stored in the right subtree
# 2. Any range which is smaller than the current range is stored in the left subtree
# 3. If a new range which intersects with an existing range, is added, then we split
#   the existing range to maintain the same structure as specified in 1 & 2
#
# It works like this:
# notation = range_start,range_end -> count
#
# Lets start with a range 4,8. Tree after adding 4,8:
#                     4,8 -> 1
#
#
# Lets add a smaller range now 2,4
#
#                     4,8 -> 1
#                    /
#                 2,4 -> 1
#
# Lets add a larger range now 8,12
#
#                     4,8 -> 1
#                    /        \
#                 2,4 -> 1     8,12 -> 1
#
#
# Now if say there is a range 8,10. This intersects with 8,12 so we split 8,12 into 8,10
# and 10,12. 8,10 has now count 2. 8,12 is replaced by 8,10 while 10,12 becomes the right
# child of 8,10
#
#                     4,8 -> 1
#                    /        \
#                 2,4 -> 1     8,10 -> 2
#                                       \
#                                       10,12 -> 1
#
#
# Lets add a range 5,6. This intersects with 4,8. 4,8 is now split into three intervals:
# 4,5 - 5,6 - 6,7 . 4,5 is added to left subtree and 6,7 is added to the right subtree
#
#                     5,6     ->      2
#                    /                 \
#            2,4 -> 1                   8,10 -> 2
#                    \                 /         \
#                    4,5 -> 1   6,7 ->1           10,12 -> 1
#
#
#
# Finding max count is relatively simple like a bst. However, deletion will be complex
# since we split ranges.

class RangeCountTree
  attr_reader :root

  def initialize(start = nil)
    @root = start && Node.new(start)
  end

  def find(num)
    @root && @root.find(num)
  end

  def find_max
    @root.find_max
  end

  def add(range)
    if root
      @root.add(range)
    else
      @root = Node.new(range)
    end
  end

  class Node
    attr_accessor :left, :right, :range_start, :range_end, :count

    def initialize(range, count = 1)
      @range_start, @range_end = *range
      @count = count
    end

    def add(range, count = 1)
      return unless range
      case
        when to_left?(range)
          self.left ? self.left.add(range, count) : (self.left = self.class.new(range, count))
        when to_right?(range)
          self.right ? self.right.add(range, count) : (self.right = self.class.new(range, count))
        else
          split_and_update(range)
          self.count += 1
      end
    end

    def find(num)
      if (self.range_start...self.range_end).include? num
        self
      elsif num >= self.range_end
        self.right && self.right.find(num)
      else
        self.left && self.left.find(num)
      end
    end

    def find_max
      max_counts = [self]
      left_max = self.left && self.left.find_max
      right_max = self.right && self.right.find_max
      [left_max, right_max].each do |subtree_max|
        if subtree_max && !subtree_max.empty?
          if subtree_max[0].count > max_counts[0].count
            max_counts = subtree_max
          elsif subtree_max[0].count == max_counts[0].count
            max_counts += subtree_max
          end
        end
      end
      max_counts
    end

    private
    def to_left?(range)
      range[1] <= @range_start
    end

    def to_right?(range)
      range[0] >= @range_end
    end

    def split_and_update(range)
      range_left, range_cur, range_right = split(range)
      [['@left', range_left], ['@right', range_right]].each do |subtree_name, range|
        next unless range
        # If the new split range lies under current range it inherits current count
        # else it has a new count
        count = ((range[1] <= @range_start || range[0] >= @range_end) && 1) || self.count
        subtree = instance_variable_get(subtree_name)
        if subtree
          subtree.add(range, self.count)
        else
          self.instance_variable_set(subtree_name, (range && self.class.new(range, count)))
        end
      end
      @range_start, @range_end = range_cur
    end

    def split(range)
      split_ranges = []
      range_limits = ([self.range_start, self.range_end] + range).sort
      split_ranges << (range_limits[0] == range_limits[1] ? nil : [range_limits[0], range_limits[1]])
      split_ranges << [range_limits[1], range_limits[2]]
      split_ranges << (range_limits[2] == range_limits[3] ? nil : [range_limits[2], range_limits[3]])
      split_ranges
    end
  end
end

scientists.rb

=begin
An editor of The History of the World of Science wants to find out the time when the
largest number of prominent scientists were alive. The prominent scientists are, by 
definition, the people mentioned in the book with the dates of their birth and death.
(No living scientists are included in the book.) Devise an algorithm for this task if it 
has the book's index as its input. The entries in the index are sorted alphabetically
and give the persons' birth and death years. If person A died the same year person B was 
born, assume that the former event happened before the latter one.
=end
require './range_count_tree'

data = <<-DATA
Nicola, 1919,1941
Albert, 1920,1940
Heisen, 1997, 1999
Edison, 1915,1956
Turin, 1924,1929
DATA

scientists = data.split("\n").collect do |line|
  name, born, died = line.split(',')
  [name, born.to_i, died.to_i]
end

rtree = RangeCountTree.new
scientists.each do |scientist|
  rtree.add(scientist[1,2])
end

puts "Best times for scientists to live:"
rtree.find_max.each do |x|
  puts "Year #{x.range_start} to #{x.range_end} when #{x.count} scientist(s) lived"
end

# Save the tree as tree.png. You need to install ruby-graphwiz
require 'graphviz'

GraphViz::new( :G, :type => :'strict digraph', :ordering =>"out" ) { |g|
  queue = [rtree.root]
  until queue.empty?
    root = queue.shift
    next unless root
    root_node = g.find_node(root.object_id.to_s)
    root_node ||= g.add_nodes(root.object_id.to_s, :label =>
        "#{root.range_start},#{root.range_end} -> #{root.count}")

    [[root.left, "left"], [root.right, "right"]].each do |child, label|
      if child
        child_node = g.add_nodes(child.object_id.to_s, :label =>
            "#{child.range_start},#{child.range_end} -> #{child.count}")
        g.add_edges(root_node, child_node, :label => label, :sametail => '1')
        queue << child
      end
    end
end
}.output( :png => "tree.png" )

=begin
Output

Best times for scientists to live:
Year 1924 to 1929 when 4 scientist(s) lived

=end