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