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