seq/divideconquer.h

Go to the documentation of this file.

#ifndef GRPPI_SEQ_DIVIDECONQUER_H
#define GRPPI_SEQ_DIVIDECONQUER_H

#include "sequential_execution.h"

namespace grppi {

template <typename Input, typename Divider, typename Solver, typename Combiner>
typename std::result_of<Solver(Input)>::type 
divide_conquer(sequential_execution & ex, 
                   Input & input, 
                   Divider && divider_op, Solver && solver_op, 
                   Combiner && combiner_op) 
{
  auto subproblems = divider_op(input);

  if (subproblems.size()<=1) return solver_op(input);

  using Output = typename std::result_of<Solver(Input)>::type;
  std::vector<Output> partials;
  // FORK
  for (auto && item : subproblems) {
    //THREAD
    partials.push_back(divide_conquer(ex, item, 
        std::forward<Divider>(divider_op), std::forward<Solver>(solver_op), 
        std::forward<Combiner>(combiner_op)));
    //END THREAD
  }
  Output out = partials[0] ;
  //JOIN
  for(int i = 1; i<partials.size();i++){
    out = combiner_op(out,partials[i]);
  }
  return out;
}

}
#endif