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

   This is part of a Scala adaptation of the Java Quicksort
   application that uses the Strategy-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 QuickSortStrategy class is a subclass of the Strategy-based
   Divide-and-Conquer Framework class DivConqStrategy, the base class
   for the Strategy objects used by the DivConqContext class.  This
   class 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 QuickSortStrategy[T <% Ordered[T]] 
    extends DivConqStrategy[QuickSortDesc[T],QuickSortDesc[T]]{    

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

  // Nothing to do, so Problem description becomes Solution description.
  def simplySolve(p: QuickSortDesc[T]): QuickSortDesc[T] = p
    
  // Partition to elements < the pivot element and >= pivot element.
  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.
  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 QuickSortTest holds a simple testing script for
   the QuickSort application.
*/

object QuickSortStrategyTest {

  def main (args: Array[String]) {   
    val st = new QuickSortStrategy[Int]
    val qs = new DivConqContext[QuickSortDesc[Int],QuickSortDesc[Int]](st)

    println("\nBeginning of QuickSortStrategy 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 QuickSortStrategy test.")
  }
  
  // Local method to aid in printing array
  private def seqAsStr[T](s: Seq[T]) = s.mkString("Array(",",",")")
}