# Posted By

christos on 01/23/08

# Statistics

Viewed 469 times
Favorited by 1 user(s)

# Basic Uncommented Crappy Binary Radix Trie

/ Published in: Ruby
`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     endend class String    def to_ip        ip = 0        split(".").each_with_index do |octet, index|            ip |= (octet.to_i << ((3 - index)*8))        end        ip    endend 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    endend`