/* Scala Template-based Divide-and-Conquer Framework
   H. Conrad Cunningham
   Version #1:  30 March 2010

   This is part of a Scala adaptation of the Java 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.)  This version also takes advantage of Scala features
   such as "map" and traits.

123456789012345678901234567890123456789012345678901234567890123456789012345678

*/


/* The DivConqTemplate trait uses the Template Method design pattern
   to implement the framework-level algorithms for divide-and-conquer
   applications.  This class has one concrete (and final) template
   method "solve", which encodes the fundamental steps shared by all
   divide-and-conquer algorithms.  It does its work by calling
   abstract hook methods that must be implemented in a subclass
   specific to a particular application. 

   The two type parameters represent the types (class names) of the
   Problem and Solution descriptions, respectively.
*/

trait DivConqTemplate[Prob <: Problem, Sol <: Solution] {

  /* Template method "solve" encodes the logic common to all
     divide-and-conquer algorithms.  To carry out the parts of the
     algorithms that are variable, the template method calls the hook
     methods isSimple, simplySolve, decompose, and combine.
  */

  final def solve(p: Prob): Sol = {   
    if (isSimple(p))
      simplySolve(p)
    else
      combine(p, decompose(p).map(solve(_)))
  }   

  // Hook methods implemented by subclasses for specific applications
  protected def isSimple(p: Prob): Boolean
  protected def simplySolve(p: Prob): Sol
  protected def decompose(p: Prob): Seq[Prob]
  protected def combine(p: Prob, ss: Seq[Sol]): Sol
}