Class: MazeSolver::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/maze_solver/tree.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Tree

Binary Tree Interprentation for Apress Open List



4
5
6
7
8
 
# File 'lib/maze_solver/tree.rb', line 4

def initialize
  ## Tree in hash form with priority as key and array 
  ## of elements as value
  @tree = Hash.new { |hash, key| hash[key] = [] }
end

Instance Method Details

#in?(element, priority) ⇒ Boolean

Returns:

  • (Boolean) 


28
29
30
31
32
33
34
 
# File 'lib/maze_solver/tree.rb', line 28

def in?(element, priority)
  ## check if elements is in the stack
  if @tree.has_key?(priority)
    return true if @tree[priority].find { |elem| elem == element }
  end
  false
end

#next ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/maze_solver/tree.rb', line 36

def next
  ## Poping an element

  return nil if @tree.empty?
   
  priority, element = *@tree.min # get the min priority
  result = element.shift # get the first element 
  @tree.delete(priority) if element.empty? # if branch with this priority is empty delete it
  
  return result
end

#push(element, priority) ⇒ Object 



23
24
25
26
 
# File 'lib/maze_solver/tree.rb', line 23

def push(element, priority)
  ## push an element in the stack
  @tree[priority] << element
end

#to_s ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/maze_solver/tree.rb', line 10

def to_s
  ## Representation of Tree
  o = '{'
  @tree.each do |k, v|
    o += ":#{k} => [\n" 
    v.each do |el|
      o += "#{el} \n"
    end
    o+="\n]\n"
  end
  o += "}"
end