Class: DSA::SkipList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/DSA/skip_list.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SkipList

Returns a new instance of SkipList.



32
33
34
35
36
 
# File 'lib/DSA/skip_list.rb', line 32

def initialize
  @levels = [SkipListLevel.new]
  @length = 0
  @height = 0
end

Instance Attribute Details

#height ⇒ Object (readonly)

Returns the value of attribute height.



30
31
32
 
# File 'lib/DSA/skip_list.rb', line 30

def height
  @height
end

#length ⇒ Object (readonly)

Returns the value of attribute length.



30
31
32
 
# File 'lib/DSA/skip_list.rb', line 30

def length
  @length
end

Instance Method Details

#add(key, value = nil) ⇒ Object 



177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/DSA/skip_list.rb', line 177

def add(key, value = nil)
  potential_place = []
  walk = start_node
  while 1
    if walk.next.is_sentinel? || key <= walk.next.key
      if walk.down
        potential_place.push walk
        walk = walk.down
        next
      else
        insert_node_between walk, walk.next, SkipListNode.new(key, value)
        @length += 1
        build_tower walk.next, potential_place, key, value
        break
      end
    else
      walk = walk.next
      next
    end
  end
end

#delete(key, value = nil) ⇒ Object

if value provided, the nodes have the same key/value pairs will be deleted, otherwise, all nodes have the same key are deleted return the value of last deleted node



161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
# File 'lib/DSA/skip_list.rb', line 161

def delete(key, value = nil)
  nodes = find_nodes(key)
  return false unless nodes

  return_value = false
  nodes.each do |node|
    if !value || value == node.value
      return_value = remove_tower node
      @length -= 1
      remove_empty_level
    end
  end

  return_value
end

#each ⇒ Object 



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/DSA/skip_list.rb', line 56

def each
  walk = @levels.first.head
  if block_given?
    walk = walk.next
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.next
    end
  else
    Enumerator.new do |y|
      each do |key, value|
        y << [key, value]
      end
    end
  end
end

#find(key) ⇒ Object 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/DSA/skip_list.rb', line 38

def find(key)
  nodes = find_nodes key

  if block_given?
    return unless nodes
    nodes.each do |node|
      yield [node.key, node.value]
    end
  else
    Enumerator.new do |y|
      find(key) do |key, value|
        y << [key, value]
      end
    end
  end

end

#ge(key) ⇒ Object 



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/DSA/skip_list.rb', line 92

def ge(key)
  nodes = find_nodes(key, true, false)

  if block_given?
    return unless nodes
    if nodes.first.key == key
      walk = nodes.first
    else
      walk = nodes.first.next
    end
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.next
    end
  else
    Enumerator.new do |y|
      ge(key) do |key, value|
        y << [key, value]
      end
    end
  end
end

#gt(key) ⇒ Object 



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/DSA/skip_list.rb', line 73

def gt(key)
  nodes = find_nodes(key, true, false)

  if block_given?
    return unless nodes
    walk = nodes.last.next
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.next
    end
  else
    Enumerator.new do |y|
      gt(key) do |key, value|
        y << [key, value]
      end
    end
  end
end

#le(key) ⇒ Object 



134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/DSA/skip_list.rb', line 134

def le(key)
  nodes = find_nodes(key, false, true)

  if block_given?
    return unless nodes
    if nodes.first.key == key
      walk = nodes.last
    else
      walk = nodes.last.prev
    end
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.prev
    end
  else
    Enumerator.new do |y|
      le(key) do |key, value|
        y << [key, value]
      end
    end
  end
end

#lt(key) ⇒ Object 



115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/DSA/skip_list.rb', line 115

def lt(key)
  nodes = find_nodes(key, false, true)

  if block_given?
    return unless nodes
    walk = nodes.first.prev
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.prev
    end
  else
    Enumerator.new do |y|
      lt(key) do |key, value|
        y << [key, value]
      end
    end
  end
end

#print_me(width = 10) ⇒ Object 



199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
# File 'lib/DSA/skip_list.rb', line 199

def print_me(width = 10)
  rec = Hash.new
  walk = @levels.first.head
  i = 0
  j = 0
  walk = walk.next
  while ! walk.is_sentinel?
    rec[ [i, j] ] = "#{walk.key},#{walk.value}"
    up_walk = walk
    while up_walk.up
      up_walk = up_walk.up
      j += 1
      rec[ [i, j] ] ="#{up_walk.key},#{up_walk.value}"
    end
    walk = walk.next
    i += 1
    j = 0
  end

  # print
  puts '=' * 100
  (height+1).times.reverse_each do |j|
    printf 'Sentinel--'
    (length).times do |i|
      if rec[ [i, j] ]
        printf ">%#{width+2}s", "#{rec[ [i, j] ]}--"
      else
        printf '-' + '-' * width + '--'
      end
    end
    puts '>Sentinel'
  end
  puts '=' * 100
end