Design Patterns - Strategy Pattern

In this tutorial we will learn about Strategy Pattern.

Table of contents

• Definition
• Class diagram
• Example
• Implementation
• Points to remember

Strategy Pattern is a Behavioral design pattern.

Definition

The Strategy Pattern defines a family of algorithms, encapsulates each one of them in a separate class and makes them interchangeable.

This pattern lets us change the algorithm independently without changing the client that use it.

Class diagram

Following is the class diagram of Strategy Pattern.

The Strategy interface has a method run which the subclass (concrete strategies) implements. This is the method that the Context uses.

The concrete class ConcreteStrategy1 implements the Strategy class and also implements a specific algorithm in the run method which is invoked by the Context class.

There can be one or more number of concrete strategy classes present.

The Context class contains a reference to one of the concrete strategies. It has a setter method setStrategy which is used to set the reference to one of the concrete strategies. It also has a method performAction which invokes the run method of the concrete strategy it references.

The Client class creates one of the concrete strategy and passes it to the Context class. This is done using the setter method that the Context class exposes. Then using the performAction method of the Context class the client invokes the run method of the concrete strategy.

Example

In the following example we are going to implement a Strategy class Search which will have a method find that the concrete strategy subclasses will implement.

Check out the following tutorials to learn more about Linear Search and Binary Search. You can also watch the Linear Search video and Binary Search video.

We will then create two subclasses that implements the Strategy class Search namely, LinearSearch and BinarySearch.

In the concrete strategy class LinearSearch we will implement the linear search algorithm inside the find method.

In the concrete strategy class BinarySearch we will implement the binary search algorithm inside the find method.

Next, we will create the Context class Numbers. This will expose a setter method setSeachingAlgorithm and performSearch method.

Finally, we will create the Client class StrategyPatternExample. In this class we will instantiate two concrete strategy classes (one of type LinearSearch and one of type BinarySearch) and use them to search for a number using the Numbers context class.

Pseudo code

// strategy interface
interface Search:
  int find(int needle, int[] haystack);


// concrete strategy class
class LinearSearch implements Search:
  int find(int needle, int[] haystack):
    // this holds the linear search implementation
    // if needle is present in haystack
    //   then return index
    // else
    //   return -1


// concrete strategy class
class BinarySearch implements Search:
  int find(int needle, int[] haystack):
    // this holds the binary search implementation
    // if needle is present in haystack
    //   then return index
    // else
    //   return -1


// context class
class Numbers:
  private Search strategy;

  setSeachingAlgorithm(Search strategy):
    this.strategy = strategy;

  performSearch(int needle, int[] haystack):
    return strategy.find(needle, haystack);


// client class
class Client:
  main():
    int[] haystack = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    Search linearSearch = new LinearSearch();
    Search binarySearch = new BinarySearch();

    Numbers obj = new Numbers();

    obj.setSeachingAlgorithm(linearSearch);
    print("Linear search 1 " + obj.performSearch(1, haystack));  // this returns index 0
    print("Linear search 100 " + obj.performSearch(100, haystack)); // this returns index -1

    obj.setSeachingAlgorithm(binarySearch);
    print("Binary search 1 " + obj.performSearch(1, haystack));  // this returns index 0
    print("Linear search 100 " + obj.performSearch(100, haystack)); // this returns index -1

Implementation

package strategy.search;

public interface Search {
    public int find(int needle, int[] haystack);
}

package strategy.search;

public class LinearSearch implements Search {
    @Override
    public int find(int needle, int[] haystack) {
        for (int index = 0; index < haystack.length; index++) {
            if (haystack[index] == needle) {
                return index;
            }
        }
        return -1;
    }
}

package strategy.search;

public class BinarySearch implements Search {
    @Override
    public int find(int needle, int[] haystack) {
        int begin = 0, end = haystack.length - 1, middle = (begin + end) / 2;
        while (begin <= end && haystack[middle] != needle) {
            if (needle < haystack[middle]) {
                end = middle - 1;
            } else {
                begin = middle + 1;
            }
            middle = (begin + end) / 2;
        }
        if (begin > end) {
            return -1;
        }
        return middle;
    }
}

package strategy.search;

public class Numbers {
    private Search strategy;

    public void setSeachingAlgorithm(Search strategy) {
        this.strategy = strategy;
    }

    public int performSearch(int needle, int[] haystack) {
        return strategy.find(needle, haystack);
    }
}

package strategy.search;

public class StrategyPatternExample {
    public static void main(String[] args) {
        int[] haystack = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        Search linearSearch = new LinearSearch();
        Search binarySearch = new BinarySearch();

        Numbers obj = new Numbers();

        obj.setSeachingAlgorithm(linearSearch);
        System.out.println("Linear search 1 " + obj.performSearch(1, haystack));
        System.out.println("Linear search 100 " + obj.performSearch(100, haystack));

        obj.setSeachingAlgorithm(binarySearch);
        System.out.println("Binary search 1 " + obj.performSearch(1, haystack));
        System.out.println("Binary search 100 " + obj.performSearch(100, haystack));
    }
}

Points to remember

• Strategy pattern helps in interchanging algorithm used at runtime.
• Helps in replacing inheritance with composition.
• Follows Open/Close Principle.
• Helps in isolating the implementation details in the concrete strategy classes.

Reference

• Design Patterns: Elements of Reusable Object-Oriented Software
• Head First Design Patterns