Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Apr 20th, 2010  |  syntax: Ruby  |  size: 2.40 KB  |  views: 158  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.   class SearchTree
  2.     OFFSET = 'a'[0].freeze #bit value? Sets constant at 97, 'a'[0] value
  3.    
  4.     attr_accessor :value
  5.    
  6.     # 0 -> *
  7.     # 1 -> -
  8.     # 2 -> a        numeric value to alphabet
  9.     # 27 -> z
  10.     def initialize
  11.       @subtrees = Array.new( 28, nil ) #New array with 28 nil values
  12.       @value = nil
  13.     end
  14.    
  15.     def insert( s, value )
  16.       priv_insert( s.split( '' ), value ) #splits each character, priv_insert only takes first character
  17.     end
  18.    
  19.     def find( s ) #finds word not in exception 
  20.       priv_find( s.split( '' ) ) #splits word in characters
  21.     end
  22.    
  23.   protected
  24.     def key( chr )
  25.       if chr == '*'   #categorie uses * for wildcard
  26.         0
  27.       elsif chr == '-' #not sure where it is used
  28.         1
  29.       else
  30.         rval = chr.downcase[0] - OFFSET + 2 #gets unicode? (value - 97 + 2)
  31.        
  32.         if rval < 2 || rval > 27 #if not regular character
  33.           rval = -1 # ORGINAL AUTHOR - invalid character
  34.         end
  35.        
  36.         rval    #a = 97, so key(a) = 2
  37.        
  38.       end
  39.     end
  40.    
  41.     def priv_insert( s, value ) #cycle through each letter in s, till empty, then sets @value
  42.       if s.empty? #value is nil
  43.         @value = value
  44.       else
  45.         index = key( s.first ) #value of first character, set to index, say s.first = a in (alpha)
  46.         subtree = if @subtrees[index] == nil #if subtree(2) = nil new search tree with array.
  47.           @subtrees[index] = SearchTree.new
  48.         else
  49.           @subtrees[index] #else subtree = @subtree[2], which is an array
  50.         end
  51.         #inserts lpha into tree, does same for l, then p, h, a, creating new subtree at each point
  52.         subtree.priv_insert( s.tail, value ) #tail = all but first digit, inserts tail
  53.       end
  54.     end
  55.    
  56.     def priv_find( search )
  57.       if @subtrees[0]                                   #returns value of 1st value in array. Was previously set to nil initialize
  58.         @subtrees[0].value              #returns actual key word
  59.       else
  60.         if search.empty?
  61.           value
  62.         else
  63.           index = key( search.first )
  64.           if @subtrees[index]
  65.             @subtrees[index].priv_find( search.tail ) #tail defined in array, returns all but first digit
  66.           else #does it use tree to make search faster? ex: if search starts with a, looks for a, then looks for next character in a alone.
  67.             nil
  68.           end
  69.         end
  70.       end
  71.     end
  72.  
  73.   end
clone this paste RAW Paste Data