Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class SearchTree
- OFFSET = 'a'[0].freeze #bit value? Sets constant at 97, 'a'[0] value
- attr_accessor :value
- # 0 -> *
- # 1 -> -
- # 2 -> a numeric value to alphabet
- # 27 -> z
- def initialize
- @subtrees = Array.new( 28, nil ) #New array with 28 nil values
- @value = nil
- end
- def insert( s, value )
- priv_insert( s.split( '' ), value ) #splits each character, priv_insert only takes first character
- end
- def find( s ) #finds word not in exception
- priv_find( s.split( '' ) ) #splits word in characters
- end
- protected
- def key( chr )
- if chr == '*' #categorie uses * for wildcard
- 0
- elsif chr == '-' #not sure where it is used
- 1
- else
- rval = chr.downcase[0] - OFFSET + 2 #gets unicode? (value - 97 + 2)
- if rval < 2 || rval > 27 #if not regular character
- rval = -1 # ORGINAL AUTHOR - invalid character
- end
- rval #a = 97, so key(a) = 2
- end
- end
- def priv_insert( s, value ) #cycle through each letter in s, till empty, then sets @value
- if s.empty? #value is nil
- @value = value
- else
- index = key( s.first ) #value of first character, set to index, say s.first = a in (alpha)
- subtree = if @subtrees[index] == nil #if subtree(2) = nil new search tree with array.
- @subtrees[index] = SearchTree.new
- else
- @subtrees[index] #else subtree = @subtree[2], which is an array
- end
- #inserts lpha into tree, does same for l, then p, h, a, creating new subtree at each point
- subtree.priv_insert( s.tail, value ) #tail = all but first digit, inserts tail
- end
- end
- def priv_find( search )
- if @subtrees[0] #returns value of 1st value in array. Was previously set to nil initialize
- @subtrees[0].value #returns actual key word
- else
- if search.empty?
- value
- else
- index = key( search.first )
- if @subtrees[index]
- @subtrees[index].priv_find( search.tail ) #tail defined in array, returns all but first digit
- 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.
- nil
- end
- end
- end
- end
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement