=begin rdoc
  
== SortLab

Instrumented versions of the sorting algorithms described in the chapters
on iterative algorithms and recursive algorithms.  The versions here are
not intended to be viewed by students -- those implementations are in the
modules named IterationLab and RecursionLab.

The three public methods implemented here are +isort+ (insertion sort),
+msort+ (mergesort), and +qsort+ (quicksort).  The only required parameter
is an array to sort.  A method will make a copy of the parameter and return
a sorted version of the copy.

An optional second parameter can be used when running experiments:
  :trace    print the state of the array after each iteration of the outer loop
  :count    return a count of the number of comparisons made instead of the sorted array
  :timer    return the execution time in seconds instead of the sorted array

=end

module RubyLabs

module SortLab

=begin rdoc

The Timer class implements a simpler timer.  Call +Timer.start+ to start
the timer, and +Timer.stop+ to get the elapsed time since the call to
+Timer.start+.
=end

class Timer
  
  def Timer.start
    @@tstart = Time.now
  end
  	
  def Timer.stop
    return Time.now - @@tstart
  end
  	
end

=begin rdoc
Insertion sort.
=end

def isort(a, mode = nil)
  a = a.clone
  Timer.start if mode == :timer
  count = 0
  for i in 1..a.length - 1
		puts isort_brackets(a,i) if mode == :trace
    x = a.slice!(i)
    j = i - 1
    while j >= 0 && (count += 1) > 0 && a[j] > x
      j = j - 1
    end
    a.insert(j + 1, x)
  end
  return case mode
    when :count : count
    when :timer : Timer.stop
    else a
  end
end

=begin rdoc
Helper method for printing the state of the array during insertion sort.
=end

def isort_brackets(a, i)
  pre = (i == 0) ? [] : a.slice(0..(i-1))
  post = (i <= a.length) ? a.slice(i..-1) : []
	return "[" + pre.join(", ") + "] [" + post.join(", ") + "]"
end

  
# Merge sort.  Makes a copy of the input Array, returns a sorted
# version of the copy.  Uses a "helper function" named merge to
# combine successively bigger pieces of the input array.

def msort(a, mode = nil)
  a = a.clone                   # don't modify the input array!
	Timer.start
  n = 1                         # size of "pile" at each step
  count = 0
  while n < a.length
    i = 0                       # first pile starts here
    while i < a.length
      count += merge(a,i,n)     # merge piles at a[i] and i+n, put at a[i]
			print " [" + a[i..i+2*n-1].join(" ") + "] " if mode == :trace
      i += 2*n                  # next pile starts at i+2n
    end
		puts if mode == :trace
    n *= 2                      # double the pile size
  end
	if mode == :timer
		return Timer.stop
	elsif mode == :count
	  return count
	else
  	return a
	end
end

# "Helper function" to merge two "piles" in place.  A call to this method
# merges n-element lists at a[i] and a[i+n] and stores the merged result
# in the array starting at a[i].  Uses an auxiliary list to hold items moved
# from a[i..i+n-1], then merges those into place at a[i+n].

def merge(a, i, n)
	aux = []
	j = k = i + n
	kmax = i + 2*n
	kmax = a.length if kmax > a.length
	count = 0
	# phase 1 -- copy items from a[i..i+n-1] to aux
	while i < k
		if a[j] && a[j] < a[i] && (aux.empty? || a[j] < aux[0])
			aux << a[i]
			a[i] = a[j]
			j += 1
			count += 1
		elsif !aux.empty? && aux[0] < a[i]
			aux << a[i]
			a[i] = aux.shift
			count += 1
		end
		i += 1
	end
	# phase 2 -- merge aux into empty slots in a[i+n..i+2n]
	while k < kmax && ! aux.empty?
		if j == kmax || a[j] > aux[0]
			a[k] = aux.shift
		else
			a[k] = a[j]
			j += 1
		end
		k += 1
		count += 1
	end
	return count
end
  
# QuickSort, based on the description from Cormen et al.  The interface is
# a method qsort, called with the array to sort and an optional mode parameter
# that specifies whether to count comparisons or measure execution time.  

# The actual sorting is done by qs.  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.

def qsort(a, mode = nil)
  dup = a.clone
  Timer.start
  if mode == :timer
    return Timer.stop
  else
    count = qs(dup, 0, a.length-1, mode)
    return mode == :count ? count : dup
  end
end

def qs(a, p, r, mode)
	puts bracketed(a,p,r) if mode == :trace
  if p < r
    q, count = partition(a, p, r)
    count += qs(a, p, q, mode)
    count += qs(a, q+1, r, mode)
  else
    count = 0
  end
	return count
end

# Set the pivot (called x here) to the item on the left edge of the
# region, then extend the regions until they meet in the middle

def partition(a, p, r)
  x = a[p]
  i = p - 1
  j = r + 1
  count = 0
  while true
    loop { j = j - 1; count += 1; break if a[j] <= x }
    loop { i = i + 1; count += 1; break if a[i] >= x }
    if i < j
      a[i], a[j] = a[j], a[i]
    else
      return j, count
    end
  end
end

def bracketed(a, left, right)
  # puts "#{left}..#{right}"
  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