skyline_tree.rb

class SkylineTree
  attr_reader :root

  def initialize(node_class = Node, start = nil, value = nil)
    @node_class = node_class
    @root = start && tree_type.new(start, value)
  end

  def add(range, value = nil)
    if root
      @root.add(range, value)
    else
      @root = @node_class.new(range, value)
    end
  end

  def print_skyline
    inorder(@root)
    print "#{@last.range_end}, 0" if @last
    @last = nil
  end

  def inorder(node)
    inorder(node.left) if node.left
    print "#{@last.range_end}, 0, " if @last && @last.range_end != node.range_start
    print "#{node.range_start}, #{node.value}, "
    @last = node
    inorder(node.right) if node.right
  end

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

    def initialize(range, value = nil)
      @range_start, @range_end = *range
      @value = value
    end

    def add(range, value = nil)
      return unless range
      case
        when self.to_left?(range)
          self.left ? self.left.add(range, value) : (self.left = self.class.new(range, value))
        when self.to_right?(range)
          self.right ? self.right.add(range, value) : (self.right = self.class.new(range, value))
        else
          self.right ? self.right.add([self.range_end, range[1]], value) : (self.right = self.class.new([self.range_end, range[1]], value)) if range[1] > self.range_end
          self.left ? self.left.add([range[0], self.range_start], value) : (self.left = self.class.new([range[0], self.range_start], value)) if range[0] < self.range_start
      end
    end

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

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