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
|
# File 'lib/dskiplist.rb', line 108
def insert(search_key, new_value = nil)
new_value = search_key if new_value.nil?
update = []
x = @header
@level.downto(0) do |i|
while x.forward[i] and x.forward[i].key < search_key
x = x.forward[i]
end
update[i] = x
end
x = x.forward[0]
if x and x.key == search_key
x.value = new_value
else
v = random_level
if v > @level
(@level + 1).upto(v) do |i|
update[i] = @header
end
@level = v
end
x = Node.new(search_key, new_value)
0.upto(v) do |i|
x.forward[i] = update[i].forward[i]
update[i].forward[i] = x
end
end
return self
end
|