Strategy Pattern

Goals

Concepts

Library

Lesson

Design Patterns

In 1994 Erich Gamma, Richard Helm, Ralph Johnson, and John Vissides published a book that was to become central to object-oriented architecture. These four authors, subsequently referred to as the Gang of Four (GoF), had noticed certain repeated structural elements in object-oriented programming—ways that good developers use classes to solve certain common tasks. They named these similar approaches design patterns, and in their book Design Patterns: Elements of Reusable Object-Oriented Software they named and explained 23 different design patterns categorized as either creational, structural, and behavioral. The names they gave to the design patterns in each of these categories are now used across the industry.

Design patterns are not rules. You do not have to use a design pattern, although the better a developer you become you may accidentally use one or invent one without knowing it. Likewise if you use a design pattern you do not have to hold to all the details in the description given by the Gang of Four. Design patterns are like guideposts from experts who have had to deal with similar problems; if nothing else they provide a common language so that you can describe the approach you are taking to solve a problem.

In the preceding lessons you have already been introduced to several design patterns that were described in the Design Patterns book. They have become so ingrained in Java programming that you may come to think of them as given, as permanent structures in the Java landscape, as indeed they now are. In this lesson you will also learn a new design pattern, the strategy pattern.

Factory Method Pattern

When learning about generics, you created a static factory method for your linked list implementation. The factory method pattern is one of the creational design patterns, and has more uses than merely serving as a convenience for replacing the constructor. Later in this lesson you'll learn how to create factories to produce objects of different types, configured using the strategy pattern.

Composite Pattern

Throughout these lessons you have learned how to compose one class out of one or more other classes. With graph classes such as linked lists and trees you have learned how to compose classes out of an indefinite number of other node classes strung together. These are all examples of the composite pattern, one of the structural design patterns.

Iterator Pattern

Most recently you learned how to extract out an interface for iterating some underlying data structure, allowing the interface implementation to worry about how to navigate the objects contained in the structure. This approach to abstract is the iterator pattern, which is another of the structural design patterns.

Strategy Pattern

The behavioral design patterns help specify how programs behave, as you might have guessed from their name. You might at first naturally tend to implement behavior directly into your classes. Consider that you are writing the software to control a boat with the latest features. The boat needs to deal with the situation in which the helmsman (the person steering the boat) falls overboard. You might implement the emergency procedures so that the boat's speed is cut in half so that other can better react to the situation:

Boat class with built-in emergency procedures.
public class Boat {

  /** @return The speed, in knots. */
  public int getSpeed() {
    …
  }

  public void setSpeed(final int newSpeed) {
    …
  }

  /** Called when the helmsman falls overboard. */
  public void onHelmsmanOverboard() {
    setSpeed(getSpeed() / 2);  //cut speed in half
  }

}

The marketing department may determine that cutting speed to 50% is still too dangerous—instead you should cut speed to 10% of the original speed. You'll have to rewrite your Boat class:

Boat class with revised emergency procedures.
public class Boat {

  …

  /** Called when the helmsman falls overboard. */
  public void onHelmsmanOverboard() {
    setSpeed(getSpeed() / 10);  //cut speed to 10%
  }

}

After the Boat has been on the market for a while, the marketing department decides to release another variation of the boat that will set a constant speed of 5 knots. That way the emergency speed won't depend on the speed at the time the helmsman went overboard. Marketing wants to sell both versions of the boat simultaneously, calling one the Model 1 and the other the Model 2. So what do you do? You could refactor the current Boat class into an AbstractBoat class with an abstract onHelmsmanOverboard() method. Then you could create both Model1Boat and a Model2Boat subclasses, each with a different onHelmsmanOverboard() implementation.

But by this time you've become wise to the ways of the marketing department, so to keep from rewriting your Boat class over and over in the future, you create a simple interface that will determine the new speed based upon the old speed in emergency conditions. You name this interface the HelmsmanOverboardEmergencyProcedure, and it will return the new speed of the boat in emergency conditions

Interface for determining new speed during emergency procedures.
public interface HelmsmanOverboardEmergencyProcedure {

  /** Returns the new speed in knots in emergency conditions.
   * @param currentSpeed The current speed in knots.
   * @return The new speed for the boat.
   */
  int getNewSpeed(int currentSpeed);

}

You retrofit the Boat class to delegate to this new emergency procedure interface to know what to do when the helmsman goes overboard:

Boat retrofitted to use emergency procedure interface.
public class Boat {

  private final HelmsmanOverboardEmergencyProcedure noPilotEmergencyProcedure;

  public Boat(final HelmsmanOverboardEmergencyProcedure noPilotEmergencyProcedure) {
    this.noPilotEmergencyProcedure = checkNotNull(noPilotEmergencyProcedure);
  }

  …

  /** Called when the helmsman falls overboard. */
  public void onHelmsmanOverboard() {
    final int newSpeed = noPilotEmergencyProcedure.getNewSpeed(getSpeed());
    setSpeed(newSpeed);
  }

}

When the helmsman goes overboard, you simply give HelmsmanOverboardEmergencyProcedure.getNewSpeed(…) your current speed, and it gives you back the new speed you should take in these emergency conditions. Now you can write an implementation for HelmsmanOverboardEmergencyProcedure for each model of the boat, and use the correct procedure implementation when you need it.

Two different implementations of the emergency procedures interface.
public class HalfSpeedEmergencyProcedure implements HelmsmanOverboardEmergencyProcedure {

  @Override
  public int getNewSpeed(final int currentSpeed) {
    return currentSpeed / 2;
  }

}
public class FiveKnotsEmergencyProcedure implements HelmsmanOverboardEmergencyProcedure {

  @Override
  public int getNewSpeed(final int currentSpeed) {
    return 5;  //set an absolute speed; ignore the current speed
  }

}
final Boat model1Boat = new Boat(new HalfSpeedEmergencyProcedure());
final Boat model2Boat = new Boat(new FiveKnotsEmergencyProcedure());

Encapsulating some sort of logic into a second class or interface, rather than implementing the logic directly into the first class, is referred to as the strategy pattern. The second class provides a strategy for performing some task. Rather than rewriting the original class, one need merely provide a different strategy implementation if different functionality is desired.

Parameterized Strategies

A strategy implementation is a class and can require parameters in the constructor as with any class. We could make a general strategy for setting the speed to some constant value, requiring that a developer provide this constant speed in the constructor. A developer could then create an emergency procedure of 5 knots (equivalent to the FiveKnotsEmergencyProcecure above) or of any value.

Emergency procedure configured by its constructor.
public class ConstantSpeedEmergencyProcedure implements HelmsmanOverboardEmergencyProcedure {

  private final int newSpeed;

  /**
   * Constructor.
   * @param newSpeed The new speed to unconditionally set in an emergency condition.
   */
  public ConstantSpeedEmergencyProcedure(final int newSpeed) {
    this.newSpeed = newSpeed;
  }

 @Override
  public int getNewSpeed(final int currentSpeed) {
    return newSpeed;
  }

}
final Boat model2Boat = new Boat(new ConstantSpeedEmergencyProcedure(5));

Strategy Constants

If there are strategies you use all the time, there is no point in creating multiple duplicate instances of them. We could create constant instances of these strategies (as long as we make the classes immutable) so that they can be reused. Rather than remembering which strategies we need to pass to which constructors to produce which boat types, we could use a variation of the factory pattern. The BoatFactory class has methods for calling the Boat constructor and passing the appropriate strategy. The caller doesn't need to keep track of which strategies to use, and the Boat doesn't have to know which strategies exist. The BoatFactory therefore serves as a layer of indirection that makes creating preconfigured Boat instances more flexible.

Boat factory of emergency procedures.
public class BoatFactory {

  public static final HelmsmanOverboardEmergencyProcedure HALF_SPEED_EMERGENCY_PROCEDURE =
    new HalfSpeedEmergencyProcedure();

  public static final HelmsmanOverboardEmergencyProcedure FIVE_KNOTS_EMERGENCY_PROCEDURE =
    new ConstantSpeedEmergencyProcedure(5);

  public static Boat createModel1Boat() {
    new Boat(HALF_SPEED_EMERGENCY_PROCEDURE);
  }

  public static Boat createModel2Boat() {
    new Boat(FIVE_KNOTS_EMERGENCY_PROCEDURE);
  }

}

These particular strategy implementations aren't complicated; you might decide just to create them in place using anonymous classes.

Boat factory of emergency procedures using anonymous classes.
public class BoatFactory {

  public static final HelmsmanOverboardEmergencyProcedure HALF_SPEED_EMERGENCY_PROCEDURE =
    new HelmsmanOverboardEmergencyProcedure() {
      @Override
      public int getNewSpeed(final int currentSpeed) {
        return currentSpeed / 2;
      }
    };

  public static final HelmsmanOverboardEmergencyProcedure FIVE_KNOTS_EMERGENCY_PROCEDURE =
    new HelmsmanOverboardEmergencyProcedure() {
      @Override
      public int getNewSpeed(final int currentSpeed) {
        return 5;
      }
    };

  public static Boat createModel1Boat() {
    new Boat(HALF_SPEED_EMERGENCY_PROCEDURE);
  }

  public static Boat createModel2Boat() {
    new Boat(FIVE_KNOTS_EMERGENCY_PROCEDURE);
  }

}

Interactive Strategies

The strategies we have been looking at so far have been little more than a set of configuration values, although they do illustrate that a strategy does allow more complex calculations that a simple list of values. You can also give your strategy even more control, based upon your needs. You could pass the strategy a reference to the Boat itself, essentially letting the strategy take control. At the same time we could make this a general strategy for all emergency procedures.

More generalized emergency procedure strategy.
public interface BoatEmergencyProcedure {

  /**
   * Handles the situation when the helmsman falls overboard.
   * @param boat The boat from which the helmsman just fell overboard.
   */
  void handleHelmsmanOverboard(@Nonnull Boat boat);

  /**
   * Handles the boat running aground.
   * @param boat The boat that is running aground.
   */
  void handleRunningAground(@Nonnull Boat boat);

}
Boat class using general emergency procedure strategy.
public class Boat {

  private final BoatEmergencyProcedure emergencyProcedure;

  public Boat(final BoatEmergencyProcedure emergencyProcedure) {
    this.emergencyProcedure = checkNotNull(emergencyProcedure);
  }

  …

  /** Called when the helmsman falls overboard. */
  public void onHelmsmanOverboard() {
    emergencyProcedure.handleHelmsmanOverboard(this);
  }

}

This approach would still allow the strategy to reduce the speed, if that is what is desired:

Emergency procedure implementation for reducing speed to half.
public class HalfSpeedEmergencyProcedure implements BoatEmergencyProcedure {

  @Override
  void handleHelmsmanOverboard(@Nonnull final Boat boat) {
    boat.setSpeed(boat.getSpeed() / 2);  //cut speed in half
  }

  @Override
  void handleRunningAground(@Nonnull final Boat boat) {
    …
  }

}

But it also allows more involved actions, such as turning the boat around and stopping:

Emergency procedure implementation for performing complicated actions.
public class CircleBackEmergencyProcedure implements BoatEmergencyProcedure {

  @Override
  void handleHelmsmanOverboard(@Nonnull final Boat boat) {
    boat.setSpeed(5);  //slow down
    boat.turn90DegreesLeft();  //circle back
    boat.turn90DegreesLeft();
    boat.turn90DegreesLeft();
    boat.setSpeed(0);  //stop and hope the helmsman can get back on board
  }

  @Override
  void handleRunningAground(@Nonnull final Boat boat) {
    …
  }

}

Comparator<T>

The standard Java libraries provide various classes and interfaces that can function as strategies. One simple yet useful strategy is the java.util.Comparator<T> interface. It allows two objects to be compared for order. Its main method, Comparator.compare(…), compares two objects and returns an int indicating which object is greater than the other. The trick is that the actual magnitude of the returned value is not important; what is important is the sign. If a negative value is returned, the first object is less than the second. If a positive value is returned, the second object is greater than the second. If zero is returned, the objects are considered equal.

java.util.Comparator<T>
package java.util;

public interface Comparator<T> {

  /**
   * Compares two objects.
   * @param object1 The first object to be compared.
   * @param object2 The second object to be compared.
   * @return A negative integer, zero, or a positive integer depending on whether
   *     first argument is less than, equal to, or greater than the second.
   * @throws NullPointerException if an argument is <code>null</code> and this
   *      comparator does not permit <code>null</code> arguments.
   * @throws ClassCastException if the arguments' types prevent them from
   *       being compared by this comparator.
   */
  int compare(T object1, T object2);

}
Comparator.compare(object1, object2)
Return Value Meaning
< 0 object1 < object2
0 object1.equals(object2)
> 0 object1 > object2

For example, we could compare two Point classes based upon their X coordinates:

Comparator<Point> strategy implementation.
/**
 * Compares two points based upon their X coordinates.
 * <p<Note: this comparator imposes orderings that are inconsistent with equals()
 * because the Y coordinate, essential for equality, is not considered in the comparison.</p>.
 */
 public class PointXComparator implements Comparator<Point> {

  @Override
  public int compare(@Nonnull final Point point1, @Nonnull final Point point2) {
    final int x1 = point1.getX();
    final int x2 = point2.getX();
    if(x1 < x2) {
      return -1;
    } else if(x1 > x2) {
      return 1;
    } else {
      assert x1 == x2;
      return 0;
    }
  }

}

Arrays.sort(…)

To see how we can use a Comparator<T>, consider the Java utility class java.util.Arrays for working working with arrays. One of its static methods is java.util.Arrays.sort(T[], Comparator<? super T>), which allows us to sort an array of objects based upon a given Comparator<T> strategy implementation. We can use the PointXComparator above to sort the points based upon their horizontal position.

Sorting points in an array using a Comparator<Point> strategy implementation.
final Point[] points = new Point[] {
    new Point(2, 5),
    new Point(10, 3),
    new Point(11, 5),
    new Point(-8, 40),
    new Point(10, 20),
    new Point(-3, -3)
  };
Arrays.sort(points, new PointXComparator());

Comparator<T> Utilities

The java.util.Comparator<T> interface also comes with a wealth of utility methods and default implementations. Here are a few useful ones; you are encouraged to see the API documentation to discover even more.

naturalOrder()
Constant method that returns a read-made comparator of the correct type for comparing items based upon their natural ordering, which is the way the JVM naturally sorts value such as primitive wrappers, or the ordering imposed by Comparable.compareTo(T) for those objects that implement java.lang.Comparable<T>.
reversed()
Default method that returns a new comparator that will produce values resulting in a reverse ordering of the original comparator.
thenComparing(Comparator<? super T>)
Default method allowing you to chain comparators. The new comparator returned will use your provided comparator as a secondary comparator if the original comparator considers two elements equal.

Review

Gotchas

In the Real World

Self Evaluation

Task

When you wrote your BookBinarySearchTree class, you sorted the books based upon their publication date. You couldn't make the BST general—that is, supporting any type of object—because you relied on the publication date provided by the Book class for sorting. You had no way of knowing how to sort general objects. But now you've learned about the strategy pattern and how the java.util.Comparator<T> interface allows you to encapsulate sorting logic for any object in a separate comparator strategy implementation. So retrofit your BookBinarySearchTree to work with any type, providing a Comparator<T> to indicate how objects should be compared.

/**
 * A binary search tree.
 * @param <T> The type of object contained in the BST.
 */
public interface BinarySearchTree<T> {

 /**
   * Adds an object to the BST.
   * The object will be sorted in the tree based upon the BST implementation.
   * If an object is already in the tree with the same comparison characteristics,
   * no object is added.
   * @param object The object to add.
   */
  void add(@NonNull T object);

  /**
  * Determines if an equivalent object is contained in the tree.
   * @param object The object to search for based upon its comparison characteristics and the BST implementation.
   * @return true if an object is contained in the tree that compares equally with the given object.
   */
  boolean contains(@Nonnull T object);

  /**
   * Prints all objects in the tree using depth-first in-order traversal.
   * This implementation uses the {@link Object#toString()} method of each object in the tree.
   */
  void printAll();

}

See Also

References

Acknowledgments