Posted By

christos on 01/23/08

Tagged

Versions (?)

Last Edited at 01/23/08 12:48pm

Statistics

Viewed 637 times

Favorited by 1 user(s)

Related snippets

Basic Uncommented Crappy Binary Radix Trie

/ Published in: Ruby

Highlighted TextExpand

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

URL: http://www.matasano.com/log/basic-uncommented-crappy-binary-radix-trie/

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.