1  
   2  # From: http://www.matasano.com/log/basic-uncommented-crappy-binary-radix-trie/
   3  # Author: Thomas Ptacek
   4  # cf. also http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/
   5  
   6  #!/usr/local/bin/ruby -w
   7  
   8  class Fixnum
   9      def to_b(l = 8)
  10          "0'" + self.to_s(2).rjust(l, "0")
  11      end
  12      def set?(i)
  13          if((self & (1 << i)) != 0)
  14              return true
  15          else
  16              return false
  17          end
  18      end
  19  
  20       def bdiff(x)
  21           ret = -1
  22           32.downto(0) do |i|
  23               if(self.set?(i) != x.set?(i))
  24                   ret = i
  25                   break
  26               end
  27           end
  28           ret
  29       end
  30  end
  31  
  32  class String
  33      def to_ip
  34          ip = 0
  35          split(".").each_with_index do |octet, index|
  36              ip |= (octet.to_i << ((3 - index)*8))
  37          end
  38          ip
  39      end
  40  end
  41  
  42  class SimpleTrie
  43      def initialize(width=32)
  44          @@node ||= Struct.new(:right, :left, :pos, :key, :value, :color)
  45          @root = @@node.new(nil, nil, width, 0, nil)
  46          @root.right = @root
  47          @root.left = @root
  48          @width = width
  49          @sz = 0
  50      end
  51  
  52      private
  53  
  54      def srch(key, limit=nil)
  55          cur = @root
  56          prev = nil
  57  
  58          while(((not prev) or (cur.pos < prev.pos)) and ((not limit) or cur.pos > limit))
  59              prev = cur
  60              if(key.set? cur.pos)
  61                  cur = cur.right
  62              else
  63                  cur = cur.left
  64              end
  65          end
  66  
  67          return cur, prev
  68      end
  69  
  70      public
  71  
  72      def []=(key, val)
  73          x, prev = srch(key)
  74          bit = key.bdiff(x.key)
  75          cur, prev = srch(key, bit)
  76  
  77          node = @@node.new(nil, nil, bit, key, val)
  78  
  79          if(key.set? bit)
  80              node.right = node
  81              node.left = cur
  82          else
  83              node.right = cur
  84              node.left = node
  85          end
  86  
  87          if(key.set? prev.pos)
  88              prev.right = node
  89          else
  90              prev.left = node
  91          end
  92  
  93          @sz += 1
  94  
  95          return val
  96      end
  97  
  98      def walk
  99          color = rand
 100          walker = lambda do |x, dir, tab|
 101              if(x.color != color)
 102                  tab.times { print "  " }
 103                  puts "#{ dir } #{ x.key } ( #{ x.key.to_b } ) @ #{ x.pos }"
 104  
 105                  x.color = color
 106  
 107                  walker.call(x.right, "-> ", tab+1)
 108                  walker.call(x.left, "<- ", tab+1)
 109              end
 110          end
 111  
 112          walker.call(@root, ".   ", 0)
 113      end
 114  
 115      def [](key)
 116          res, p = srch(key)
 117          return res.value
 118      end
 119  end
 120  
 121  
 122  require 'pp'
 123  
 124  t = SimpleTrie.new
 125  
 126  t[3] = 3
 127  t[4] = 4
 128  t[2] = 2
 129  
 130  t.walk
 131  pp t
 132  
 133  p t[3]