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