IntervalSkipList

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 4
def initialize
  @head = HeadNode.new(max_height)
  @ranges = {}
  @probability = 0.5
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 36
def containing(n)
  containing_with_node(n).first
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 64
def delete(marker)
  range = ranges[marker]
  path_to_first_node = make_path
  first_node = find(range.first, path_to_first_node)

  cur_node = first_node
  cur_level = first_node.top_level
  while next_node_at_level_inside_range?(cur_node, cur_level, range)
    while can_ascend_from?(cur_node, cur_level) && next_node_at_level_inside_range?(cur_node, cur_level + 1, range)
      cur_level += 1
    end
    cur_node = unmark_forward_path_at_level(cur_node, cur_level, marker)
  end

  while node_inside_range?(cur_node, range)
    while can_descend_from?(cur_level) && next_node_at_level_outside_range?(cur_node, cur_level, range)
      cur_level -= 1
    end
    cur_node = unmark_forward_path_at_level(cur_node, cur_level, marker)
  end
  last_node = cur_node

  first_node.endpoint_of.delete(marker)
  if first_node.endpoint_of.empty?
    first_node.delete(path_to_first_node)
  end

  last_node.endpoint_of.delete(marker)
  if last_node.endpoint_of.empty?
    path_to_last_node = make_path
    find(range.last, path_to_last_node)
    last_node.delete(path_to_last_node)
  end
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 14
def empty?
  head.forward[0].nil?
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 18
def expire(range, length_change)
  expired_markers, first_node_after_range = overlapping(range)
  expired_markers.each { |marker| delete(marker) }
  first_node_after_range.propagate_length_change(length_change)    
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 40
def insert(range, marker)
  ranges[marker] = range
  first_node = insert_node(range.first)
  first_node.endpoint_of.push(marker)
  last_node = insert_node(range.last)
  last_node.endpoint_of.push(marker)

  cur_node = first_node
  cur_level = first_node.top_level
  while next_node_at_level_inside_range?(cur_node, cur_level, range)
    while can_ascend_from?(cur_node, cur_level) && next_node_at_level_inside_range?(cur_node, cur_level + 1, range)
      cur_level += 1
    end
    cur_node = mark_forward_path_at_level(cur_node, cur_level, marker)
  end

  while node_inside_range?(cur_node, range)
    while can_descend_from?(cur_level) && next_node_at_level_outside_range?(cur_node, cur_level, range)
      cur_level -= 1 
    end
    cur_node = mark_forward_path_at_level(cur_node, cur_level, marker)
  end
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 10
def max_height
  3
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 24
def overlapping(range)
  markers, first_node = containing_with_node(range.first)

  cur_node = first_node
  begin
    markers.concat(cur_node.forward_markers.flatten)
    cur_node = cur_node.forward[0]
  end while cur_node.key < range.last

  return markers.uniq, cur_node
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 157
def can_ascend_from?(node, level)
  level < node.top_level
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 161
def can_descend_from?(level)
  level > 0
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 112
def containing_with_node(n)
  containing = []
  cur_node = head
  (max_height - 1).downto(0) do |cur_level|
    while (next_node = cur_node.forward[cur_level]) && next_node.key <= n
      cur_node = next_node
      if cur_node.key == n
        return containing + (cur_node.markers - cur_node.endpoint_of), cur_node
      end
    end
    containing.concat(cur_node.forward_markers[cur_level])
  end

  return containing, cur_node
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 128
def delete_node(key)
  path = make_path
  found_node = find(key, path)
  found_node.delete(path) if found_node.key == key
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 134
def find(key, path)
  cur_node = head
  (max_height - 1).downto(0) do |cur_level|
    while (next_node = cur_node.forward[cur_level]) && next_node.key < key
      cur_node = next_node
    end
    path[cur_level] = cur_node
  end
  cur_node.forward[0]
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 102
def insert_node(key)
  path = make_path
  found_node = find(key, path)
  if found_node && found_node.key == key
    return found_node
  else
    return Node.new(key, next_node_height, path)
  end
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 145
def make_path
  Array.new(max_height, nil)
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 177
def mark_forward_path_at_level(node, level, marker)
  node.forward_markers[level].push(marker)
  next_node = node.forward[level]
  next_node.markers.push(marker)
  node = next_node
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 169
def next_node_at_level_inside_range?(node, level, range)
  node.forward[level] && node.forward[level].key <= range.last
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 173
def next_node_at_level_outside_range?(node, level, range)
  (node.forward[level].nil? || node.forward[level].key > range.last)
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 149
def next_node_height
  height = 1
  while rand < probability && height < max_height
    height += 1
  end
  height
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 165
def node_inside_range?(node, range)
  node.key < range.last
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 191
def nodes
  nodes = []
  cur_node = head.forward[0]
  until cur_node.nil?
    nodes << cur_node
    cur_node = cur_node.forward[0]
  end
  nodes
end

# File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 184
def unmark_forward_path_at_level(node, level, marker)
  node.forward_markers[level].delete(marker)
  next_node = node.forward[level]
  next_node.markers.delete(marker)
  node = next_node
end