class SearchTree

Class that is a Tree-like data structure to hold all Openings

Attributes

root[RW]

Public Class Methods

new() click to toggle source
# File lib/chess_openings/search_tree.rb, line 7
def initialize
  @root = Node.new(nil)
end

Public Instance Methods

==(other) click to toggle source

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
empty?() click to toggle source

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_moves_in_depth(num) click to toggle source

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(moves, value) click to toggle source

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_all_with_moves(moves) click to toggle source

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
size() click to toggle source

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
to_s() click to toggle source

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

find_node(moves, curr_node) click to toggle source
# 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
get_all_from_node(curr_node) click to toggle source
# 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
get_moves_in_depth_helper(num_moves, curr_node, depth) click to toggle source
# 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
insert_helper(moves, value, curr_node) click to toggle source
# 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
search_helper(moves, curr_node) click to toggle source
# 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
size_helper(node) click to toggle source
# 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