Home » Tools » Strategy pattern in MPD-Helper

Strategy pattern in MPD-Helper

Here are some thoughts about last refactoring step for my MPD-Helper (repo’s here, post’s here) – replacing code type with Strategy.

I’ll try to explain pattern (I’ll base on Gang of Four brilliant book), my motivation for this refactoring and (in short) implementation.


Strategy is behavioral pattern which defines a family of interchangeable algorithms. Goal is to allow client classes to independently choose algorithm to use on-the-fly at runtime.

UML structure:


Use example: in simple* pacman clone you could define movement algorithm family with one class that defines chasing character, and one for escaping from it, and then change behaviour simply by exchanging moving class depending on situation.

* In reality each ghost from pacman have little different moving algorithm – one always goes to tile just before player, one always to tile just after and so on…

MPD-strat Combobox highlighted on screen allows to select algorithm which solves given jobs.
After selection application slightly changes input area (ex. change labels on rows), and then – in many various places – I placed conditionals to choose accurate behaviour depending on selected algorithm. It didn’t look good.
I wanted to simplyfy code and reduce if statements. Ideally there could be only one if statement in “combo box index changed” event handler.


I started with class on the left side of diagram, and changed it to algorithm family on the right side:


First step was to determine which methoods were used by which algorithm, and design class hierarchy (you can see it above). For example aproximateSequencing was fundamental for LPT and RTP algorithms but completely irrelevant for Johnson or Hu, but no algorithm can operate without sortJobs and one of it’s comparators. Methods for sorting’ll become part of ‘Solver’ interface for algorithms family, while others’ll be moved to subclasses. It could be nice to create another subinterface for LTP and RTP algorithms because RTP is basically reversed LTP, and then derive subclasses for each algorithm.
Next I created method to override in subclasses. All but Fifo solving function need list of jobs and number of machines. So interface for algorithms consist of:

 public virtual Solution Solve(QList<Job*> jobs, int MachineAmount);
int AscendingBasedOnProcessingTime(Job *A, Job *B, int MachineToCompare);
int DescendingBasedOnProcessingTime(Job* A, Job* B, int MachineToCompare);
int AscendingBasedOnRelase(Job* A, Job* B, int def);
void sortJobs(QList<Job*> *JobsToSort, int MachineToCompare,
              int (Solver::*)(Job *, Job *, int));

With little subinterface for LTP and RTP:

int FindFreeMachine(int* MachineTimes, int MachineAmount);
QVector< QList<Job*> > aproximateSequencing(QList<Job *> jobs,
                                            int MachineAmount);

Second step was to create each subclass for algorithm family. At the begining of refactoring I had two if statements:

  1. One for changing input area:
    if(chosenAlgorithm == 0){
       rowsAmount = ui->MachinesSpinBox->value();
    else if(chosenAlgorithm == 1){
       QStringList newLabels = (QStringList() << "P" << "R");
    else if(chosenAlgorithm == 4){
       QStringList newLabels = 
          (QStringList() << "Prec[1]" << "Prec[2]" << "Prec[3]");
       rowsAmount = 1;
  2. One for executing proper algorithm:
     if(chosenAlgorithm == 0){
       MachineCount = ui->MachinesSpinBox->value();
       solution = solv.Johnson(A, MachineCount);
    else if(chosenAlgorithm == 1){
       MachineCount = 1;
       solution = solv.Fifo(A);
    else if(chosenAlgorithm == 2){
       MachineCount = ui->MachinesSpinBox->value();
       solution = solv.LPT(A,MachineCount);
    else if(chosenAlgorithm == 3){
       MachineCount = ui->MachinesSpinBox->value();
       solution = solv.RPT(A,MachineCount);
    else if(chosenAlgorithm == 4){
       MachineCount = ui->MachinesSpinBox->value();
       solution = solv.Hu(A,MachineCount);

Goal was to change second statement to this:

   MachineCount = (chosenAlgorithm != 1) ? ui->MachinesSpinBox->value() : 1;
   solution = solv->Solve(A, MachineCount);

With instructions to create proper solver inside first if statement.

I copied if statement with algorithm execution into virtual solve method and then:
I worked in a loop:

  • Pick one of the algorithms. Create a subclass for it and override solve method.
  • Remove one of legs of the conditional statement connected with given algorithm.
  • Compile and test.

Untill all algorithms were turned into subclasses. Then I made superclass method pure virtual.

-> Implemetation recipe is nearly identical to one you can find in Fowler’s Refactoring in Replace conditional with polymorphism chapter.
-> It’s really important to remember that in c++ you need to highlight with function is virtual with proper keyword.

Posted in Tools and tagged as , ,

Comments are closed.