omedale

# We would use binary tree to implement Breadth First Search(BFS)
# use Queue to help implement BFS, we use "deq" to remove an element and "enq" to add element
# 1. Add root node to the queue, and mark it as visited(already explored).
# 2. Loop on the queue as long as it's not empty.
#    1. Get and remove the node at the top of the queue(current).
#    2. For every non-visited child of the current node, do the following: 
#       1. Mark it as visited.
#       2. Check if it's the goal node, If so, then return it.
#       3. Otherwise, push it to the queue.
# 3. If queue is empty, then goal node was not found!

omedale

# Put unvisited nodes on a queue
# Solves the shortest path problem: Find path from "source" to "target"
# that uses the fewest number of edges
# It's not recursive (like depth first search)
#
# The steps are quite simple:
# * Put s into a FIFO queue and mark it as visited
# * Repeat until the queue is empty:
#   - Remove the least recently added node n
#   - add each of n's unvisited adjacents to the queue and

omedale

# Implement Depth First Search using Binary Search Tree
# uses stack to perform the DFS.
# Precedure
#  1. Add root node to the stack.
#  2. Loop on the stack as long as it's not empty.
#    1. Get the node at the top of the stack(current), mark it as visited,
#    2. For every non-visited child of the current node, do the following:
#        1. Check if it's the goal node, If so, then return this child node.
#        2. Otherwise, push it to the stack.
#  3. If stack is empty, then goal node was not found!

omedale

class ASTAR
  def initialize(start, stop)
    [start, stop].each do |e|
      raise ArgumentError, 
        "Required a Node as input." +
        "Received a #{e.class}" unless e.is_a? Node
    end

    @start = start # start node
    @stop  = stop  # end node

omedale

def heap_sort(array)
  n = array.length - 1

  # turn the array into a max heap
  # where parent nodes(first element of the array) is larger than all its children
  (n / 2).downto(0) do |i|      
    create_max_heap(array, i, n) 
  end

  while n > 0

omedale

def quick_sort(array)
  return array if array.size <= 1
  
  # select a pivot element
  # here we get the first element of the array
  pivot ||= array.shift
  
  #use the pivot to break down the array into 2 subarray(left and right)
  left = array.select { |n| n < pivot }
  right = array.select { |n| n >= pivot }

omedale

def merge_sort(array)
  # set base case to allows the recursion to work and not go on indefinitely.
  return array if array.size <= 1
  
  # split the array into two 
  left, right = array.each_slice((array.size/2).round).to_a

  # merge the mergesorted left half with the mergesorted right half.
  merge = -> (left, right) {
    array = []

omedale

def insertion_sort(array)
  return array if array.size <= 1
  (array.size).times do |j|
    while j > 0
      if array[j - 1] > array[j]
        array[j - 1], array[j] = array[j], array[j - 1]
      else
        break
      end
      

omedale

module FormatString
  def to_slug(str)
    str.downcase.strip.gsub(' ', '-').gsub(/[^\w-]/, '')
  end
end

module DateTime
  def now
    Time.now
  end

omedale

# when a class uses another object to provide some or all of its functionality
class Movement

  def step
    puts "stepping"
  end

  def crawl
    puts "crawling"
  end