ruby-treetop 1.6.3-1 / usr / lib / ruby / vendor_ruby / treetop / runtime / interval_skip_list / node.rb

This file is indexed.

/usr/lib/ruby/vendor_ruby/treetop/runtime/interval_skip_list/node.rb is in ruby-treetop 1.6.3-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
class IntervalSkipList
  class Node < HeadNode
    attr_accessor :key
    attr_reader :markers, :endpoint_of

    def initialize(key, height, path)
      super(height)
      @key = key
      @markers = []
      @endpoint_of = []
      update_forward_pointers(path)
      promote_markers(path)
    end

    def all_forward_markers
      markers.flatten
    end

    def delete(path)
      0.upto(top_level) do |i|
        path[i].forward[i] = forward[i]
      end
      demote_markers(path)
    end

    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

    def update_forward_pointers(path)
      0.upto(top_level) do |i|
        forward[i] = path[i].forward[i]
        path[i].forward[i] = self
      end
    end

    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


    def can_be_promoted_higher?(marker, level)
      level < top_level && forward[level + 1] && forward[level + 1].markers.include?(marker)
    end

    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

    def demote_markers(path)
      demote_inbound_markers(path)
      demote_outbound_markers(path)
    end

    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

    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

    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

    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

    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
  end
end

APT Browse - Built by Thomas Orozco.