Advanced Search

Return to Snippet

Revision: 4843
at January 23, 2008 12:48 by christos
Initial Code 
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
Initial URL 
http://www.matasano.com/log/basic-uncommented-crappy-binary-radix-trie/
Initial Description 

                                

                                                            

                                    

                                        

                                        Initial Title
                                        

                                    

                                    
Basic Uncommented Crappy Binary Radix Trie

                                

                                                            

                                    

                                        

                                        Initial Tags
                                        

                                    

                                    
sort, search, ruby

                                

                                                            

                                    

                                        

                                        Initial Language
                                        

                                    

                                    
Ruby