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

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

123456789012345678901234567890123456789012345678901234567890123456789012345678

*/


/* The DivConqContext class uses the Strategy 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 delegating the
   variable parts of the divide-and-conquer application to hook
   methods that must be implemented in a subclass of the
   DivConqStrategy class specific to a particular application.

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

class DivConqContext[Prob <: Problem,Sol <: Solution]
    (dcs: DivConqStrategy[Prob,Sol]) {

  // the Strategy object
  private var dc = dcs

  /* 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 on the
     current Strategy object.
  */

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

  // Allow the Strategy object to be changed at runtime.
  def setStrategy(dcs: DivConqStrategy[Prob,Sol]) { dc = dcs }
}


/* The DivConqStrategy class is the base class for all Strategy
   objects in applications.  It encapsulates the concrete
   implementations of the variable parts of the divide-and-conquer
   application.  

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

abstract class DivConqStrategy[Prob <: Problem,Sol <: Solution] {
  def isSimple(p: Prob): Boolean
  def simplySolve(p: Prob): Sol
  def decompose(p: Prob): Seq[Prob]
  def combine(p: Prob, ss: Seq[Sol]) : Sol
}