Software Design Pattern By Example: Strategy

Explain Strategy Design Pattern in an easy-to-understand example

(I know the majority of this blog’s readers are testers or automation/DevOps engineers. This one is about software design.)

Table of Contents:
· The Problem: GCD
· Preparation
  ∘ Implement individual algorithms
· Sub-optimal Design
· Strategy Pattern
· Apply Strategy pattern again
· Exercise
  ∘ A quick introduction to Object-Oriented in C++

The Problem: GCD

In mathematics, the greatest common divisor (GCD, also called the greatest common factor) of two or more integers (not all zero), is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4, and the gcd of 6, 8, 12 is 2.

In this exercise, you implement at least two algorithms to solve the GCD of two integers x and y . The program will decide the use of algorithms dynamically based on the multiple of x, y. For example, If x * y > 100000 using algorithm A, otherwise B. The decision logic does not matter, as long as the program demonstrates it can ‘choose’ a different algorithm.

Preparation

As always, start simple and make small progress.

1. Implement 2+ GCD algorithms.
   It is OK to start with a procedural style (i.e. non-OO design).

2. Encapsulate implementations in classes
   Wrap your implementations into several meaningful classes. See below for a super-short introduction of OO in C++

3. Optimize the design
   The goal of this exercise is to ensure your design is flexible, you may do a self-assessment by asking yourself the following questions:
   — how much will it affect my program if the decision logic changes?
   — how easy is it to add another algorithm?

Implement individual algorithms

The actual implementation of algorithms is not the focus of this exercise, feel free to copy the solutions from the Internet. I recommend the following algorithms:

• Classic GCD Algorithm
  Get a list of divisors of x and look for the first one from the highest that is also a divisor of y.
  Example code on GeeksForGeeks: get all prime factors

• Euclidean GCD Algorithm
  Using recursive calls, the program is very short (around 4 lines depending on the coding style)

• Binary GCD Algorithm
  Also known as Stein’s algorithm.

Sub-optimal Design

Quite commonly, programmers end up with a not-bad-but-no-so-good design like the one below.

// read x, y from the user …
if (x * y> 10000) {
  GCDBinary* solver = new GCDBinary();
  std::cout << solver->gcd(x, y) << std::endl;
} else if (x * y > 100) {
  GCDEuclid* solver = new GCDEuclid();
  std::cout << solver->gcd(x, y) << std::endl;
} else {
  GCDStein* solver = new GCDStein();
  std::cout << solver->gcd(x, y) << std::endl;
}

why is it not optimal? Firstly, duplications. More importantly, if we add or remove a new algorithm, there will be relatively more changes, compared to the design below.

Strategy Pattern

How about this version?

GCDSolver* gcd_solver = determine_algorithm(x, y);
std::cout << gcd_solver->gcd(x, y) << std::endl;

determine_algorithmis a C-style function that returns a suitable GCD algorithm implementation. The program is much neater, right? It is designed with the Strategy pattern.

GCDSolver* determine_algorithm(int x, int y) {
    if (x * y> 10000) {
        return new GCDBinary();
    } else if (x * y > 100) {
        return new GCDEuclid();
    } else {
        return  new GCDStein();
    }
}

Two class definitions.

class GCDBinary : public GCDSolver {
 public:
   int gcd(int a, int b) override;
};

class GCDEuclid : public GCDSolver {
 public:
   int gcd(int a, int b) override;
   std::string getName() override;
};

And implementations.

#include "GCDEuclid.hpp"

int GCDEuclid::gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

#include "GCDBinary.hpp"

int GCDBinary::gcd(int a, int b) {
  //...
}

Strategy is a widely used GoF pattern.

Image Credit: https://sourcemaking.com/design_patterns/strategy

Apply the Strategy pattern again

Now there is a new requirement: besides the GCD, also print out the algorithm name. For example, here is the sample output for two big numbers,

[Binary] 1000

and when two numbers are small.

[Stein] 10

The solution is actually very simple, just another application of the Strategy pattern. The key statement in the main method can be:

std::cout << “[“ << gcd_solver->getName() << “] “ << gcd_solver->gcd(x, y) << “\n”;

Exercise

Add one or more GCD algorithms, or remove an existing algorithm implementation. See what impacts these changes had on your code.

A quick introduction to Object-Oriented in C++

For readers who are not familiar with C++.

Class definitions

class Bird {
 virtual void fly() = 0; // means no implementation
};

class Parrot : public Bird {
 void fly() override;
}

class Ostrich : public Bird {
 void fly() override;
}

The keywords virtual means the parent class defines a “behaviour”, which its child (and grandchild …) can override it.

Class implementations

void Parrot::fly(){ 
 std::cout << “I can and I can talk sometimes” << std::endl;
};

void Ostrich::fly(){ 
 std::cout << “I rather walk” << std::endl;
}

Suggested conventions

If you don’t have a preferred C++ style and naming conventions, Here is my suggestion. Take FooBar class, the header file is Foo.hpp and the implementation file is FooBar.cpp.

Class definition template

#ifndef FooBar_hpp
#define FooBar_hpp
class Foo {// …}; // important to have ‘;’ at the end of class definition
#endif /* FooBar_hpp *

Class implementation template

#include “FooBar.hpp”

FooBar::FooBar() {
 // Constructor …
}

void FooBar::OneMethod() {
 // …
}

Related reading

• Software Design Pattern By Example: Singleton

• Software Design Pattern By Example: Template Method