module RubyAnagrams::Subtrees

Provides subtree branching and searching behavior to the trie data strucutre. @author Connor Lay

Public Instance Methods

descend(symbols) click to toggle source

Descends the trie data structure following the given sequence of symbols. The last node visited is returned, either because it is a leaf or there are no symbols left. @note This method alters the symbol array. @param symbols [Array<Symbol>] the symbol sequence to follow. @return [Node] the last node visited.

# File lib/anagrams/subtrees.rb, line 23
def descend symbols
  return self unless symbol = symbols[0]
  return self unless child = @children[symbol]
  symbols.slice! 0
  child.descend symbols
end
node_count() click to toggle source

Returns the number of nodes in the subtree. When called on Root, returns the number of nodes in the entire trie data structure. @return [Integer] the number of nodes in the subtree.

# File lib/anagrams/subtrees.rb, line 9
def node_count
  nodes = 1
  @children.each_value do |child|
    nodes += child.node_count
  end
  nodes
end

Protected Instance Methods

add_to_subtree(symbols) click to toggle source

Descends the trie data structure, adding nodes when needed, for a given sequence of symbols. The last node visited is designated as a terminal. @param symbols [Array<Symbol>] the symbol sequence to follow. @return [String] the word represented by the last node visited.

# File lib/anagrams/subtrees.rb, line 35
def add_to_subtree symbols
  current = descend symbols
  symbols.each do |symbol|
    current[symbol] = Node.new symbol, current
    current = current[symbol]
  end
  current.terminal!
  current.word
end
search_subtree(symbols) click to toggle source

Depth-first searches the trie data structure for a node representing a given sequence of symbols. @param symbols [Array<Symbol>] the symbol sequence to follow. @return [Boolean] true if the last node visited is a terminal, false otherwise.

# File lib/anagrams/subtrees.rb, line 49
def search_subtree symbols
  current = descend symbols
  current.terminal? && symbols.empty?
end