class SearchTree
Class that is a Tree-like data structure to hold all Openings
Attributes
Public Class Methods
# File lib/chess_openings/search_tree.rb, line 7 def initialize @root = Node.new(nil) end
Public Instance Methods
Compares two trees
@param [SearchTree] other SearchTree
to be compared with @return [Boolean] True if both trees have the same children with the same values
# File lib/chess_openings/search_tree.rb, line 36 def ==(other) @root == other.root end
Check if tree doesnt have child Nodes and root is empty
@return [Boolean] True if the tree doesnt have childs and root value is nil, false otherwise
# File lib/chess_openings/search_tree.rb, line 14 def empty? @root.empty? && @root.leaf? end
Get all values at a certain depth
@param [int] num Depth to be used to find values @return [Array] Array with all the values found at depth num
# File lib/chess_openings/search_tree.rb, line 72 def get_moves_in_depth(num) get_moves_in_depth_helper(num, @root, 0).flatten end
Insert new value in SearchTree
at the depth of the moves
@param [Array] moves Path to the place to insert the value @param [Opening] value Value to be inserted in the tree
# File lib/chess_openings/search_tree.rb, line 44 def insert(moves, value) moves = ChessOpeningsHelper.moves_as_symbols(moves) insert_helper(moves, value, @root) end
Search in the tree with the path moves
@param [Array] moves Array with Strings or symbols that represent the path @return [Opening] Opening
that was found in the tree, Nil otherwise
# File lib/chess_openings/search_tree.rb, line 53 def search(moves) moves = ChessOpeningsHelper.moves_as_symbols(moves) search_helper(moves, @root) end
Search the tree for all the values from the path and values of its children
@param [Array] moves Array with Strings or symbols that represent the path @return [Array] Array with values found
# File lib/chess_openings/search_tree.rb, line 62 def search_all_with_moves(moves) moves = ChessOpeningsHelper.moves_as_symbols(moves) node = find_node(moves, @root) get_all_from_node(node).flatten end
Number of not empty Nodes
@return [int] Total of not empty Nodes in the tree
# File lib/chess_openings/search_tree.rb, line 21 def size size_helper(@root) end
String representation of the tree
@return [String] Representation of the Nodes in the tree
# File lib/chess_openings/search_tree.rb, line 28 def to_s @root.to_s end
Private Instance Methods
# File lib/chess_openings/search_tree.rb, line 88 def find_node(moves, curr_node) return curr_node if moves.empty? curr_hash = curr_node.nodes move = moves.first return nil if curr_hash[move].nil? next_node = curr_hash[move] find_node(moves.drop(1), next_node) end
# File lib/chess_openings/search_tree.rb, line 99 def get_all_from_node(curr_node) result = curr_node.value.nil? ? [] : [curr_node.value] return result if curr_node.leaf? curr_hash = curr_node.nodes curr_hash.values.each do |next_node| result << get_all_from_node(next_node) end result end
# File lib/chess_openings/search_tree.rb, line 78 def get_moves_in_depth_helper(num_moves, curr_node, depth) return [] if depth == num_moves && curr_node.value.nil? return [curr_node.value] if depth == num_moves result = [] curr_node.nodes.values.each do |node| result << get_moves_in_depth_helper(num_moves, node, depth + 1) end result end
# File lib/chess_openings/search_tree.rb, line 111 def insert_helper(moves, value, curr_node) return if moves.empty? curr_hash = curr_node.nodes move = moves.first last_move = moves.size == 1 if curr_hash[move].nil? curr_hash[move] = last_move ? Node.new(value) : Node.new(nil) elsif last_move && curr_hash[move].value.nil? curr_hash[move].value = value end insert_helper(moves.drop(1), value, curr_hash[move]) end
# File lib/chess_openings/search_tree.rb, line 124 def search_helper(moves, curr_node) move = moves.first curr_hash = curr_node.nodes return nil if curr_hash[move].nil? next_node = curr_hash[move] search_helper(moves.drop(1), next_node) || curr_hash[move].value end
# File lib/chess_openings/search_tree.rb, line 132 def size_helper(node) sum = node.value.nil? ? 0 : 1 return sum if node.leaf? node.keys.each do |key| sum += size_helper(node.nodes[key]) end sum end