Skip to content

Instantly share code, notes, and snippets.

@shadabahmed
Created April 23, 2013 04:59
Show Gist options
  • Save shadabahmed/5440961 to your computer and use it in GitHub Desktop.
Save shadabahmed/5440961 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment