snippetsmania.com
Post and share your code snippets

class Fixnum
def to_b(l = <img src='http://www.snippetsmania.com/wp-includes/images/smilies/icon_cool.gif' alt='8)' class='wp-smiley' /> "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

source