IntervalSkipList

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

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

    # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 64
64:   def delete(marker)
65:     range = ranges[marker]
66:     path_to_first_node = make_path
67:     first_node = find(range.first, path_to_first_node)
68: 
69:     cur_node = first_node
70:     cur_level = first_node.top_level
71:     while next_node_at_level_inside_range?(cur_node, cur_level, range)
72:       while can_ascend_from?(cur_node, cur_level) && next_node_at_level_inside_range?(cur_node, cur_level + 1, range)
73:         cur_level += 1
74:       end
75:       cur_node = unmark_forward_path_at_level(cur_node, cur_level, marker)
76:     end
77: 
78:     while node_inside_range?(cur_node, range)
79:       while can_descend_from?(cur_level) && next_node_at_level_outside_range?(cur_node, cur_level, range)
80:         cur_level -= 1
81:       end
82:       cur_node = unmark_forward_path_at_level(cur_node, cur_level, marker)
83:     end
84:     last_node = cur_node
85: 
86:     first_node.endpoint_of.delete(marker)
87:     if first_node.endpoint_of.empty?
88:       first_node.delete(path_to_first_node)
89:     end
90: 
91:     last_node.endpoint_of.delete(marker)
92:     if last_node.endpoint_of.empty?
93:       path_to_last_node = make_path
94:       find(range.last, path_to_last_node)
95:       last_node.delete(path_to_last_node)
96:     end
97:   end

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

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

    # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 40
40:   def insert(range, marker)
41:     ranges[marker] = range
42:     first_node = insert_node(range.first)
43:     first_node.endpoint_of.push(marker)
44:     last_node = insert_node(range.last)
45:     last_node.endpoint_of.push(marker)
46: 
47:     cur_node = first_node
48:     cur_level = first_node.top_level
49:     while next_node_at_level_inside_range?(cur_node, cur_level, range)
50:       while can_ascend_from?(cur_node, cur_level) && next_node_at_level_inside_range?(cur_node, cur_level + 1, range)
51:         cur_level += 1
52:       end
53:       cur_node = mark_forward_path_at_level(cur_node, cur_level, marker)
54:     end
55: 
56:     while node_inside_range?(cur_node, range)
57:       while can_descend_from?(cur_level) && next_node_at_level_outside_range?(cur_node, cur_level, range)
58:         cur_level -= 1 
59:       end
60:       cur_node = mark_forward_path_at_level(cur_node, cur_level, marker)
61:     end
62:   end

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

    # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 24
24:   def overlapping(range)
25:     markers, first_node = containing_with_node(range.first)
26: 
27:     cur_node = first_node
28:     begin
29:       markers.concat(cur_node.forward_markers.flatten)
30:       cur_node = cur_node.forward[0]
31:     end while cur_node.key < range.last
32: 
33:     return markers.uniq, cur_node
34:   end

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

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

     # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 112
112:   def containing_with_node(n)
113:     containing = []
114:     cur_node = head
115:     (max_height - 1).downto(0) do |cur_level|
116:       while (next_node = cur_node.forward[cur_level]) && next_node.key <= n
117:         cur_node = next_node
118:         if cur_node.key == n
119:           return containing + (cur_node.markers - cur_node.endpoint_of), cur_node
120:         end
121:       end
122:       containing.concat(cur_node.forward_markers[cur_level])
123:     end
124: 
125:     return containing, cur_node
126:   end

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

     # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 134
134:   def find(key, path)
135:     cur_node = head
136:     (max_height - 1).downto(0) do |cur_level|
137:       while (next_node = cur_node.forward[cur_level]) && next_node.key < key
138:         cur_node = next_node
139:       end
140:       path[cur_level] = cur_node
141:     end
142:     cur_node.forward[0]
143:   end

     # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 102
102:   def insert_node(key)
103:     path = make_path
104:     found_node = find(key, path)
105:     if found_node && found_node.key == key
106:       return found_node
107:     else
108:       return Node.new(key, next_node_height, path)
109:     end
110:   end

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

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

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

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

     # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 149
149:   def next_node_height
150:     height = 1
151:     while rand < probability && height < max_height
152:       height += 1
153:     end
154:     height
155:   end

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

     # File lib/treetop/runtime/interval_skip_list/interval_skip_list.rb, line 191
191:   def nodes
192:     nodes = []
193:     cur_node = head.forward[0]
194:     until cur_node.nil?
195:       nodes << cur_node
196:       cur_node = cur_node.forward[0]
197:     end
198:     nodes
199:   end

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