/* QuickSort Application of Scala Divide-and-Comquer Template Framework
   H. Conrad Cunningham
   Version #1:  30 March 2010

   This is part of a Scala adaptation of the Java Quicksort
   application that uses the Template-based Divide-and-Conquer
   Framework described in the paper:

     H. C. Cunningham, Y. Liu, and C. Zhang. "Using Classic Problems
     to Teach Java Framework Design," _Science of Computer
     Programming_, Special Issue on Principles and Practice of
     Programming in Java (PPPJ 2004), Vol. 59, No. 1-2, pp. 147-169,
     January 2006. doi: 10.10.16/j.scico.2005.07.009.

   This Scala version uses generics to give more generality to the
   clients and to avoid casting.  (The old Java version did not use
   generics.)  

123456789012345678901234567890123456789012345678901234567890123456789012345678

*/


/* The QuickSortTemplate class is a subclass of the Template-based
   Divide-and-Conquer Framework.  It uses the QuickSortDesc class to
   represent both the Problem and Solution objects.  

   The sort is carried out in-place within the array encapsulated in
   the QuickSortDesc object.
 */

class QuickSortTemplate[T <% Ordered[T]] 
    extends DivConqTemplate[QuickSortDesc[T],QuickSortDesc[T]]{    

  // Stop when segment to sort is of length one
  protected def isSimple(p: QuickSortDesc[T]): Boolean 
    = (p.getFirst >= p.getLast)

  // Nothing to do, so Problem description becomes Solution description.
  protected def simplySolve(p: QuickSortDesc[T]): QuickSortDesc[T] = p
    
  // Partition to elements < the pivot element and >= pivot element.
  protected def decompose (p: QuickSortDesc[T]) : Array[QuickSortDesc[T]] = {
    val first = p.getFirst
    val last  = p.getLast
    val a     = p.getArr
    val x     = a(first)  // pivot value
    var sp    = first;

    for (i <- (first + 1) to last) {
      if (a(i) < x) {
        sp += 1
        swap(a,sp,i)
      }
    } 
    swap(a,first,sp)
    val ps = new Array[QuickSortDesc[T]](2)
    ps(0)  = new QuickSortDesc[T](a,first,sp-1)
    ps(1)  = new QuickSortDesc[T](a,sp+1,last)
    ps
  }
    
  // Array sorted in place, so Problem description becomes Solution.
  protected def combine(p: QuickSortDesc[T], ss: Seq[QuickSortDesc[T]])
      : QuickSortDesc[T]  = p
                  
  private def swap (a: Array[T], first: Int, last: Int) {
    val temp = a(first)
    a(first) = a(last)
    a(last)  = temp
  }
}


/* Singleton object QuickSortTemplateTest holds a simple testing
   script for the QuickSortTemplate application.
*/

object QuickSortTemplateTest {

  def main (args: Array[String]) {   
    val qs = new QuickSortTemplate[Int]

    println("\nBeginning of QuickSortTemplate test.\n")

    val sort10 = Array(10, 9, 1, 2, 8, 7, 5, 5, 3, 4)
    println("Unsorted:  " + seqAsStr(sort10))
    qs.solve( new QuickSortDesc(sort10, 0, sort10.length-1) )
    println("Sorted:    " + seqAsStr(sort10))
    println();

    val sortrev = Array(9, 8, 7, 5, 5, 4, 3, 2, 1)
    println("Unsorted:  " + seqAsStr(sortrev))
    qs.solve( new QuickSortDesc(sortrev, 0, sortrev.length-1) )
    println("Sorted:    " + seqAsStr(sortrev))
    println

    val sorted = Array(1, 2, 3, 4, 5, 5, 7, 8, 9)
    println("Unsorted:  " + seqAsStr(sorted))
    qs.solve( new QuickSortDesc(sorted, 0, sorted.length-1) )
    println("Sorted:    " + seqAsStr(sorted))
    println

    val sort01 = Array(1)
    println("Unsorted:  " + seqAsStr(sort01))
    qs.solve( new QuickSortDesc(sort01, 0, sort01.length-1) )
    println("Sorted:    " + seqAsStr(sort01))
    println

    val sort00 = new Array[Int](0)
    println("Unsorted:  " + seqAsStr(sort00))
    qs.solve( new QuickSortDesc(sort00, 0, sort00.length-1) )
    println("Sorted:    " + seqAsStr(sort00))
    println

    println("End of QuickSortTemplate test.")
  }
  
  // Local method to aid in printing array
  private def seqAsStr[T](s: Seq[T]) = s.mkString("Array(",",",")")
}