Posted By

christos on 01/23/08


Tagged

sort search ruby tree algorithm radix


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

webstic


Basic Uncommented Crappy Binary Radix Trie


 / Published in: Ruby
 

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

  1. class Fixnum
  2. def to_b(l = 8)
  3. "0′" + self.to_s(2).rjust(l, "0")
  4. end
  5. def set?(i)
  6. if((self & (1 << i)) != 0)
  7. return true
  8. else
  9. return false
  10. end
  11. end
  12.  
  13. def bdiff(x)
  14. ret = -1
  15. 32.downto(0) do |i|
  16. if(self.set?(i) != x.set?(i))
  17. ret = i
  18. break
  19. end
  20. end
  21. ret
  22. end
  23. end
  24.  
  25. class String
  26. def to_ip
  27. ip = 0
  28. split(".").each_with_index do |octet, index|
  29. ip |= (octet.to_i << ((3 - index)*8))
  30. end
  31. ip
  32. end
  33. end
  34.  
  35. class SimpleTrie
  36. def initialize(width=32)
  37. @@node ||= Struct.new(:right, :left, :pos, :key, :value, :color)
  38. @root = @@node.new(nil, nil, width, 0, nil)
  39. @root.right = @root
  40. @root.left = @root
  41. @width = width
  42. @sz = 0
  43. end
  44.  
  45. private
  46.  
  47. def srch(key, limit=nil)
  48. cur = @root
  49. prev = nil
  50.  
  51. while(((not prev) or (cur.pos < prev.pos)) and ((not limit) or cur.pos > limit))
  52. prev = cur
  53. if(key.set? cur.pos)
  54. cur = cur.right
  55. else
  56. cur = cur.left
  57. end
  58. end
  59.  
  60. return cur, prev
  61. end
  62.  
  63. public
  64.  
  65. def []=(key, val)
  66. x, prev = srch(key)
  67. bit = key.bdiff(x.key)
  68. cur, prev = srch(key, bit)
  69.  
  70. node = @@node.new(nil, nil, bit, key, val)
  71.  
  72. if(key.set? bit)
  73. node.right = node
  74. node.left = cur
  75. else
  76. node.right = cur
  77. node.left = node
  78. end
  79.  
  80. if(key.set? prev.pos)
  81. prev.right = node
  82. else
  83. prev.left = node
  84. end
  85.  
  86. @sz += 1
  87.  
  88. return val
  89. end
  90.  
  91. def walk
  92. color = rand
  93. walker = lambda do |x, dir, tab|
  94. if(x.color != color)
  95. tab.times { print " " }
  96. puts "#{ dir } #{ x.key } ( #{ x.key.to_b } ) @ #{ x.pos }"
  97.  
  98. x.color = color
  99.  
  100. walker.call(x.right, "-> ", tab+1)
  101. walker.call(x.left, "<- ", tab+1)
  102. end
  103. end
  104.  
  105. walker.call(@root, ". ", 0)
  106. end
  107.  
  108. def [](key)
  109. res, p = srch(key)
  110. return res.value
  111. end
  112. end

Report this snippet  

You need to login to post a comment.