class Fixnum
def to_b(l = 8)
"0′" + self.to_s(2).rjust(l, "0")
end
def set?(i)
if((self & (1 << i)) != 0)
return true
else
return false
end
end
def bdiff(x)
ret = -1
32.downto(0) do |i|
if(self.set?(i) != x.set?(i))
ret = i
break
end
end
ret
end
end
class String
def to_ip
ip = 0
split(".").each_with_index do |octet, index|
ip |= (octet.to_i << ((3 - index)*8))
end
ip
end
end
class SimpleTrie
def initialize(width=32)
@@node ||= Struct.new(:right, :left, :pos, :key, :value, :color)
@root = @@node.new(nil, nil, width, 0, nil)
@root.right = @root
@root.left = @root
@width = width
@sz = 0
end
private
def srch(key, limit=nil)
cur = @root
prev = nil
while(((not prev) or (cur.pos < prev.pos)) and ((not limit) or cur.pos > limit))
prev = cur
if(key.set? cur.pos)
cur = cur.right
else
cur = cur.left
end
end
return cur, prev
end
public
def []=(key, val)
x, prev = srch(key)
bit = key.bdiff(x.key)
cur, prev = srch(key, bit)
node = @@node.new(nil, nil, bit, key, val)
if(key.set? bit)
node.right = node
node.left = cur
else
node.right = cur
node.left = node
end
if(key.set? prev.pos)
prev.right = node
else
prev.left = node
end
@sz += 1
return val
end
def walk
color = rand
walker = lambda do |x, dir, tab|
if(x.color != color)
tab.times { print " " }
puts "#{ dir } #{ x.key } ( #{ x.key.to_b } ) @ #{ x.pos }"
x.color = color
walker.call(x.right, "-> ", tab+1)
walker.call(x.left, "<- ", tab+1)
end
end
walker.call(@root, ". ", 0)
end
def [](key)
res, p = srch(key)
return res.value
end
end