=begin rdoc
  
== RecursionLab

Divide and conquer algorithms for searching and sorting.
The methods implemented in this module are +bsearch+ (binary search),
+msort+ (merge sort), and +qsort!+ (QuickSort).  The module also
contains 'helper methods' that can be used to trace the execution
of the algorithms.

=end

module RubyLabs

module RecursionLab
  
=begin rdoc

Linear search -- use for baseline tests.  Form that makes it easy to attach
probe to count comparisons.
=end

# :begin :search
	def search(a, k)
	  i = 0
	  while i < a.length
	    return i if a[i] == k
	    i += 1
	  end
		return nil
	end
# :end :search

	
=begin rdoc

Call <tt>bsearch(k, a)</tt> to search for item +k+ in array +a+, using
the binary search algorithm.  Based on the specification in Introduction
to Algorithms, by Cormen et al.

=end

# :begin :bsearch
	def bsearch(a, k)
	  lower = -1
	  upper = a.length
	  while true                              # iteration ends with return statement
	    mid = (lower + upper) / 2             # set the mid point for this iteration
	    return nil if upper == lower + 1      # search fails if the region is empty
	    return mid if k == a[mid]             # search succeeds if k is at the midpoint
	    if k < a[mid]
	      upper = mid                         # next search: lower half of the region
	    else
	      lower = mid                         # next search: upper half
	    end
	  end	  
	end
# :end :bsearch

=begin rdoc

Recursive implementation of binary search.

=end

# :begin :rbsearch
  def rbsearch(a, k, lower = -1, upper = a.length)
    mid = (lower + upper) / 2
    return nil if upper == lower + 1      # search fails if the region is empty
    return mid if k == a[mid]             # search succeeds if k is at the midpoint
    if k < a[mid]
      return rbsearch(a, k, lower, mid)
    else
      return rbsearch(a, k, mid, upper)
    end
  end
# :end :rbsearch

=begin rdoc
A helper method that can be called from a probe to display the contents
of an array during a search or sort.
=end

	def brackets(a, left, right = a.length-1, mid = nil)    # :nodoc:
    left = 0 if left < 0
    right = a.length-1 if right >= a.length
    pre = left == 0 ? "" : " " + a.slice(0..(left-1)).join("  ") + " "
    inner = left <= right ? a.slice(left..right).join("  ") : ""
    post = " " + a.slice(right+1..-1).join("  ")
    res = pre + "[" + inner + "]" + post
    if mid && left < right
      res[res.index(a[mid].to_s)-1] = ?*
    end
    return res
	end

=begin rdoc

A test harness for bsearch -- makes an array, gets an item not in the array,
counts comparisons (assuming user has set a counting probe)

=end

  def bsearch_count(n)
    a = TestArray.new(n)
    x = a.random(:fail)
    count { bsearch(a,x) }
  end
  
=begin rdoc
  
Merge sort.  Makes a copy of the input array, returns a sorted
version of the copy.  Uses a "helper function" to
combine successively bigger pieces of the input array.

=end

# :begin :msort :merge :merge_groups :less
def msort(array)
  a = array.clone
  size = 1
  while size < a.length
    merge_groups(a, size)
    size = size * 2
  end
	return a
end
# :end :msort

# "Helper method" to merge all groups of size g

# :begin :merge_groups
def merge_groups(a, gs)
  i = 0                            # first group starts here
  while i < a.length
    j = i + 2*gs - 1               # end of second group
    a[i..j] = merge(a, i, gs)      # merge groups at a[i] and a[i+g]
    i += 2*gs                      # next groups starts 2*g places to the right
  end
end
# :end :merge_groups

# "Helper method" to merge two blocks.  A call of the form merge(a, i, n) creates
# a new list by merging n-element lists starting at a[i] and a[i+n].

# :begin :merge
  def merge(a, i, gs)    # :nodoc:
    ix = j = min(i + gs, a.length)
    jx = min(j + gs, a.length)
    res = []
    while i < ix || j < jx
      if j == jx || i < ix && less( a[i], a[j] )
        res << a[i]
        i += 1
      else
        res << a[j]
        j += 1
      end
    end
    return res
  end
# :end :merge

# :begin :less
  def less(x, y)
    return x < y
  end
# :end :less

# Helper function to print brackets during merge sort

  def msort_brackets(a, n)      # :nodoc:
    # return " [" + a[i..i+2*n-1].join(" ") + "] "
  	res = []
  	i = 0
  	while i < a.length
  		res << a[i..((i+n)-1)].join(" ")
  		i += n
  	end
  	return "[" + res.join("] [") + "]"
  end
  
=begin rdoc
  
QuickSort, based on the description from Cormen et al.  Sorts the input array in place.  
The parameters (using notation from Cormen et al): +p+ is the left boundary of the region 
to sort, and +r+ is right boundary.  The call to +partition+ sets +q+, the new boundary 
between two sub-regions.

=end

# :begin :qsort :partition
	def qsort(a, p = 0, r = a.length-1)       # sort the region bounded by p and r
	  a = a.dup if p == 0 && r == a.length-1  # don't modify the input array (top level only)
	  if p < r
	    q = partition(a, p, r)    # q is boundary between small items and large items
	    qsort(a, p, q)            # sort small items (range from p to q)
	    qsort(a, q+1, r)          # sort large items (range from q+1 to r)
	  end
	  return a
	end
# :end :qsort

# :begin :partition
	def partition(a, p, r)        # partition the region bounded by p and r
	  x = a[p]                    # x is the pivot value
	  i = p - 1
	  j = r + 1
	  while true                  # squeeze i, j until they point at items to exchange
	    loop { j = j - 1; break if a[j] <= x }
	    loop { i = i + 1; break if a[i] >= x }
	    if i < j                  
	      a[i], a[j] = a[j], a[i] # exchange items at locations i and j
	    else
	      return j                # no more exchanges; return location that separates regions
	    end
	  end
	end
# :end :partition

# Helper procedure used to trace the execution of qsort

	def qsort_brackets(a, left, right)       # :nodoc:
	  tmp = []
	  tmp += a[ 0 .. (left-1) ] if left > 0
	  tmp << "["
	  tmp += a[ left .. right ] if right >= 0
	  tmp << "]"
	  tmp += a[ (right+1) .. (a.length-1) ] if right < a.length
	  return tmp.join(" ")
	end

end # RecursionLab

end # RubyLabs