class IntervalSkipList::Node
Attributes
endpoint_of[R]
key[RW]
markers[R]
Public Class Methods
new(key, height, path)
click to toggle source
Calls superclass method
IntervalSkipList::HeadNode.new
# File lib/treetop/runtime/interval_skip_list/node.rb, line 6 def initialize(key, height, path) super(height) @key = key @markers = [] @endpoint_of = [] update_forward_pointers(path) promote_markers(path) end
Public Instance Methods
all_forward_markers()
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 15 def all_forward_markers markers.flatten end
delete(path)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 19 def delete(path) 0.upto(top_level) do |i| path[i].forward[i] = forward[i] end demote_markers(path) end
propagate_length_change(length_change)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 26 def propagate_length_change(length_change) cur_node = self while cur_node do cur_node.key += length_change cur_node = cur_node.forward[0] end end
Protected Instance Methods
can_be_promoted_higher?(marker, level)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 74 def can_be_promoted_higher?(marker, level) level < top_level && forward[level + 1] && forward[level + 1].markers.include?(marker) end
delete_marker_from_path(marker, level, terminus)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 78 def delete_marker_from_path(marker, level, terminus) cur_node = self until cur_node == terminus cur_node.forward_markers[level].delete(marker) cur_node.markers.delete(marker) cur_node = cur_node.forward[level] end end
demote_inbound_markers(path)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 92 def demote_inbound_markers(path) demoted = [] new_demoted = [] top_level.downto(0) do |i| incoming_markers = path[i].forward_markers[i].dup incoming_markers.each do |marker| unless forward_node_with_marker_at_or_above_level?(marker, i) path[i].forward_markers[i].delete(marker) new_demoted.push(marker) end end demoted.each do |marker| path[i + 1].place_marker_on_inbound_path(marker, i, path[i]) if forward[i].markers.include?(marker) path[i].forward_markers[i].push(marker) else new_demoted.push(marker) end end demoted = new_demoted new_demoted = [] end end
demote_markers(path)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 87 def demote_markers(path) demote_inbound_markers(path) demote_outbound_markers(path) end
demote_outbound_markers(path)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 120 def demote_outbound_markers(path) demoted = [] new_demoted = [] top_level.downto(0) do |i| forward_markers[i].each do |marker| new_demoted.push(marker) unless path[i].forward_markers[i].include?(marker) end demoted.each do |marker| forward[i].place_marker_on_outbound_path(marker, i, forward[i + 1]) new_demoted.push(marker) unless path[i].forward_markers[i].include?(marker) end demoted = new_demoted new_demoted = [] end end
forward_node_with_marker_at_or_above_level?(marker, level)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 139 def forward_node_with_marker_at_or_above_level?(marker, level) level.upto(top_level) do |i| return true if forward[i].markers.include?(marker) end false end
place_marker_on_inbound_path(marker, level, terminus)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 155 def place_marker_on_inbound_path(marker, level, terminus) cur_node = self until cur_node == terminus cur_node.forward_markers[level].push(marker) cur_node = cur_node.forward[level] cur_node.markers.push(marker) end end
place_marker_on_outbound_path(marker, level, terminus)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 146 def place_marker_on_outbound_path(marker, level, terminus) cur_node = self until cur_node == terminus cur_node.forward_markers[level].push(marker) cur_node.markers.push(marker) cur_node = cur_node.forward[level] end end
promote_markers(path)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 43 def promote_markers(path) promoted = [] new_promoted = [] 0.upto(top_level) do |i| incoming_markers = path[i].forward_markers[i] markers.concat(incoming_markers) incoming_markers.each do |marker| if can_be_promoted_higher?(marker, i) new_promoted.push(marker) forward[i].delete_marker_from_path(marker, i, forward[i+1]) else forward_markers[i].push(marker) end end promoted.each do |marker| if can_be_promoted_higher?(marker, i) new_promoted.push(marker) forward[i].delete_marker_from_path(marker, i, forward[i+1]) else forward_markers[i].push(marker) end end promoted = new_promoted new_promoted = [] end end
update_forward_pointers(path)
click to toggle source
# File lib/treetop/runtime/interval_skip_list/node.rb, line 36 def update_forward_pointers(path) 0.upto(top_level) do |i| forward[i] = path[i].forward[i] path[i].forward[i] = self end end