Object
# 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
Disabled; run with --debug to generate this.
Generated with the Darkfish Rdoc Generator 1.1.6.