/* Insertion Sorting Framework
   H. Conrad Cunningham
   Version #1:  28 March 2010

   This is relatively straightforward Scala translation of the C++
   abstract class InsertionSorter from section 21.1.1 of Timothy
   Budd's _An Introduction to Object-Oriented Programming_, Third
   Edition.  This Scala version uses a trait instead of an abstract
   class.

   This trait follows the Template Method design pattern for
   implementing a simple framework.

123456789012345678901234567890123456789012345678901234567890123456789012345678

*/

trait InsertionSorter {

  // Concrete template method
  final def sort {
    for (i <- 1 to size-1) {
      var j = i - 1
      while (j >= 0 && lessThan(j+1,j)) {
        swap(j,j+1)
        j = j - 1
     }
   }
  }

  // Abstract hook methods (called by template method)
  def swap(i: Int, j: Int) 
  def size: Int 
  def lessThan(i: Int, j: Int): Boolean
}