class DSkipList
Attributes
header[RW]
level[RW]
Public Class Methods
new(top_level = Float::INFINITY)
click to toggle source
# File lib/dskiplist.rb, line 43 def initialize(top_level = Float::INFINITY) @header = Node.new(1) @level = 0 @max_level = top_level @p = 0.5 @node_nil = Node.new(1000000) end
Public Instance Methods
[](key)
click to toggle source
# File lib/dskiplist.rb, line 70 def [] key node = self.find_node(key) if node and node.key == key return node.value else return nil end end
[]=(key, value)
click to toggle source
# File lib/dskiplist.rb, line 138 def []= key, value self.insert(key, value) end
clear()
click to toggle source
# File lib/dskiplist.rb, line 51 def clear initialize(@max_level) return self end
count(from = nil, to = nil, level = 0)
click to toggle source
# File lib/dskiplist.rb, line 147 def count(from = nil, to = nil, level = 0) each(from, to, nil, level, nil) end
delete(search_key)
click to toggle source
# File lib/dskiplist.rb, line 87 def delete(search_key) 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 0.upto(x.forward.length - 1) do |i| update[i].forward[i] = x.forward[i] end return true else return false end end
each(from=nil, to=nil, limit=nil, level=0, output=nil) { |x, output| ... }
click to toggle source
accepts a block which is run on each element
# File lib/dskiplist.rb, line 152 def each(from=nil, to=nil, limit=nil, level=0, output=nil) if from x = find_node(from) x = x.forward[level] if x.forward[level] else x = @header.forward[level] end #if no block is given, assume we are trying to count and avoid the expensive yield below if !block_given? count = 0 while x break if to && x.key >= to count += 1 x = x.forward[level] end return count elsif to or limit count = 0 while !x.nil? yield(x, output) count += 1 break if to and x.key >= to break if limit and count == limit x = x.forward[level] end else while x yield(x, output) x = x.forward[level] end end return output end
find_node(search_key)
click to toggle source
returns previous node if exact key match is not found
# File lib/dskiplist.rb, line 57 def find_node(search_key) x = @header @level.downto(0) do |i| #puts "on level #{i}" while x.forward[i] and x.forward[i].key < search_key #puts "walked node #{x.key} on level #{i}" x = x.forward[i] end end x = x.forward[0] if x.forward[0] and x.forward[0].key == search_key return x end
insert(search_key, new_value = nil)
click to toggle source
# 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
insert_hash(hash)
click to toggle source
# File lib/dskiplist.rb, line 142 def insert_hash(hash) hash.each {|key, value| self[key] = value} return self end
largest()
click to toggle source
# File lib/dskiplist.rb, line 195 def largest x = @header @level.downto(0) do |i| while x.forward[i] x = x.forward[i] end end return x.value end
random_level()
click to toggle source
# File lib/dskiplist.rb, line 79 def random_level v = 0 while rand < @p && v < @max_level v += 1 end v end
smallest()
click to toggle source
# File lib/dskiplist.rb, line 205 def smallest return @header.forward[0].value end
to_a(from = nil, to = nil, limit = nil, level = 0)
click to toggle source
# File lib/dskiplist.rb, line 190 def to_a(from = nil, to = nil, limit = nil, level = 0) each(from, to, limit, level, []) {|n, arr| arr.push(n.value)} end
Also aliased as: to_ary
to_h(from = nil, to = nil, limit = nil, level = 0)
click to toggle source
# File lib/dskiplist.rb, line 186 def to_h(from = nil, to = nil, limit = nil, level = 0) each(from, to, limit, level, {}) {|n, hash| hash[n.key] = n.value} end
to_s()
click to toggle source
# File lib/dskiplist.rb, line 209 def to_s str = "" @level.downto(0) do |l| str << "Level #{l}: " + to_a(nil, nil, nil, l).join('-') + "\n" end return str end
to_str()
click to toggle source
# File lib/dskiplist.rb, line 217 def to_str return "SkipList level #{@max_level}" end