IntervalSkipList::Node

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 6
 6:     def initialize(key, height, path)
 7:       super(height)
 8:       @key = key
 9:       @markers = []
10:       @endpoint_of = []
11:       update_forward_pointers(path)
12:       promote_markers(path)
13:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 15
15:     def all_forward_markers
16:       markers.flatten
17:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 19
19:     def delete(path)
20:       0.upto(top_level) do |i|
21:         path[i].forward[i] = forward[i]
22:       end
23:       demote_markers(path)
24:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 26
26:     def propagate_length_change(length_change)
27:       cur_node = self
28:       while cur_node do
29:         cur_node.key += length_change
30:         cur_node = cur_node.forward[0]
31:       end
32:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 74
74:     def can_be_promoted_higher?(marker, level)
75:       level < top_level && forward[level + 1] && forward[level + 1].markers.include?(marker)
76:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 78
78:     def delete_marker_from_path(marker, level, terminus)
79:       cur_node = self
80:       until cur_node == terminus
81:         cur_node.forward_markers[level].delete(marker)
82:         cur_node.markers.delete(marker)
83:         cur_node = cur_node.forward[level]
84:       end
85:     end

     # File lib/treetop/runtime/interval_skip_list/node.rb, line 92
 92:     def demote_inbound_markers(path)
 93:       demoted = []
 94:       new_demoted = []
 95: 
 96:       top_level.downto(0) do |i|
 97:         incoming_markers = path[i].forward_markers[i].dup
 98:         incoming_markers.each do |marker|
 99:           unless forward_node_with_marker_at_or_above_level?(marker, i)
100:             path[i].forward_markers[i].delete(marker)
101:             new_demoted.push(marker)
102:           end
103:         end
104: 
105:         demoted.each do |marker|
106:           path[i + 1].place_marker_on_inbound_path(marker, i, path[i])
107: 
108:           if forward[i].markers.include?(marker)
109:             path[i].forward_markers[i].push(marker)
110:           else
111:             new_demoted.push(marker)
112:           end
113:         end
114: 
115:         demoted = new_demoted
116:         new_demoted = []
117:       end
118:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 87
87:     def demote_markers(path)
88:       demote_inbound_markers(path)
89:       demote_outbound_markers(path)
90:     end

     # File lib/treetop/runtime/interval_skip_list/node.rb, line 120
120:     def demote_outbound_markers(path)
121:       demoted = []
122:       new_demoted = []
123: 
124:       top_level.downto(0) do |i|
125:         forward_markers[i].each do |marker|
126:           new_demoted.push(marker) unless path[i].forward_markers[i].include?(marker)
127:         end
128: 
129:         demoted.each do |marker|
130:           forward[i].place_marker_on_outbound_path(marker, i, forward[i + 1])
131:           new_demoted.push(marker) unless path[i].forward_markers[i].include?(marker)
132:         end
133: 
134:         demoted = new_demoted
135:         new_demoted = []
136:       end
137:     end

     # File lib/treetop/runtime/interval_skip_list/node.rb, line 139
139:     def forward_node_with_marker_at_or_above_level?(marker, level)
140:       level.upto(top_level) do |i|
141:         return true if forward[i].markers.include?(marker)
142:       end
143:       false
144:     end

     # File lib/treetop/runtime/interval_skip_list/node.rb, line 155
155:     def place_marker_on_inbound_path(marker, level, terminus)
156:       cur_node = self
157:       until cur_node == terminus
158:         cur_node.forward_markers[level].push(marker)
159:         cur_node = cur_node.forward[level]
160:         cur_node.markers.push(marker)
161:       end
162:     end

     # File lib/treetop/runtime/interval_skip_list/node.rb, line 146
146:     def place_marker_on_outbound_path(marker, level, terminus)
147:       cur_node = self
148:       until cur_node == terminus
149:         cur_node.forward_markers[level].push(marker)
150:         cur_node.markers.push(marker)
151:         cur_node = cur_node.forward[level]
152:       end
153:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 43
43:     def promote_markers(path)
44:       promoted = []
45:       new_promoted = []
46:       0.upto(top_level) do |i|
47:         incoming_markers = path[i].forward_markers[i]
48:         markers.concat(incoming_markers)
49: 
50:         incoming_markers.each do |marker|
51:           if can_be_promoted_higher?(marker, i)
52:             new_promoted.push(marker)
53:             forward[i].delete_marker_from_path(marker, i, forward[i+1])
54:           else
55:             forward_markers[i].push(marker)
56:           end
57:         end
58: 
59:         promoted.each do |marker|
60:           if can_be_promoted_higher?(marker, i)
61:             new_promoted.push(marker)
62:             forward[i].delete_marker_from_path(marker, i, forward[i+1])
63:           else
64:             forward_markers[i].push(marker)
65:           end
66:         end
67: 
68:         promoted = new_promoted
69:         new_promoted = []
70:       end
71:     end

    # File lib/treetop/runtime/interval_skip_list/node.rb, line 36
36:     def update_forward_pointers(path)
37:       0.upto(top_level) do |i|
38:         forward[i] = path[i].forward[i]
39:         path[i].forward[i] = self
40:       end
41:     end