Design patterns - Strategy

From Juneday education
Jump to: navigation, search

Description

In this chapter, we'll discuss the Strategy pattern.

Aim of the pattern

The intent of this pattern is to let us adhere to the Open-Closed principle when it comes to changing the behavior of an object at runtime without having to change its class and recompile. The Open-Closed principle was the principle that said we should be open for extension but closed to modification. What it means, is that you should be able to add functionality with as little as possible (optimally none) effect on existing code.

The idea behind this pattern is to encapsulate a process or an algorithm (or a behavior if you want an understandable word) so that this can change without affecting other code. The common way is to create an interface (if we're talking Java, and we are) for a behavior or a strategy for solving some problem, and let implementing classes offer various ways to do it. These implementing classes have many benefits. They allow us to create objects in runtime for a behavior and use it together with existing objects.

In the Java API there are some examples. One classic example is the Comparator interface in java.util. The idea here, is that some methods (like for instance sorting and searching) needs a way to compare the objects in a collection to be operated on. If we sort a collection of objects of some type, the sorting algorithm obviously needs to be able to compare all the objects to each other in order to come up with some ordering.

Any object which is of a class which implements Comparator can be used for this task in for instance Collections.sort().

Problem description

A first attempt at making your objects comparable so that a sorting method can arrange them in some order, would perhaps be to let every object know how it should compare itself to some other object of the same type. This can actually be done using the java.lang.Comparable interface.

Let's take a simple example of sorting a list of String. If we have a list of String references for strings representing album names, it would be nice to be able to sort that list. Perhaps we are making a small application for keeping track of our music albums, and we'd like to be able to print the list sorted. For simplicity, we'll use Strings to represent an album and we only focus on the group/artist names.

This could be a small such list of groups/artists:

String[] albums = {
  "Yes",
  "The 5,6,7,8s",
  "ABBA",
  "The Beatles",
  "Neil Young",
  "The The",
  "Wasp",
  "The Who",
  "The Them",
  "Beatless"
};

How can we sort them? We'll, luckily for us, String implements java.lang.Comparable<String>, so we can let the string objects themselves be responsible for comparing themselves with other strings. So we can actually use Arrays.sort() right away!

public class AlbumList {

  public static void main(String[] args) {
    String[] albums = {
      "Yes",
      "The 5,6,7,8s",
      "ABBA",
      "The Beatles",
      "Neil Young",
      "The The",
      "Wasp",
      "The Who",
      "The Them",
      "Beatless"
    };
    java.util.Arrays.sort(albums);
    System.out.println("My sorted albums: " + java.util.Arrays.toString(albums));
  }
}
/* Output:
$ javac AlbumList.java && java AlbumList
My sorted albums: [ABBA, Beatless, Neil Young, The 5,6,7,8s, The Beatles, The The, The Them, The Who, Wasp, Yes]
*/

We'll that's too bad. It seems that it sorts them really strictly and with group names beginning with "The", the sort is not what at least I wanted. What can we do?

Solution - applying the Strategy Pattern

The good news is that the sort methods in the Java API are designed with the Strategy pattern in mind. There are alternative overloaded versions of the sort() methods in Arrays and Collections, which not only take a list as the argument, but also a reference to an object which is a Comparator.

What they have done, is to create another interface (this time in java.util called Comparator which encapsulates the strategy for comparing two objects of the same type.

That allows us to send along a comparator object together with the list, when we call one of the sort() methods. This means that we can encapsulate the algorithm for comparing (for instance two String objects) in an object of type Comparator. The Comparator interface makes all this possible.

The interface Comparator is rather simple (at least in Java 7):

public interface Comparator<T> {
  int compare(T o1, T o2);
  boolean equals(Object obj);
}

You can safely ignore the equals() method, since every object inherits it from Object, so it is not mandatory to implement it, just because it is included in the interface. So the only method you need to implement is int compare(T o1, T o2).

The logic of the compare() method is the same as in the compareTo() method in Comparable - you should calculate an int describing which of the two objects are greatest according to some rules for comparison.

If o1 is greater than o2, you should return a positive int. If they are to be considered equal when comparing them, you should return 0. Otherwise you should return a negative int.

This actually means that we can quite simply create an object implementing Comparator<String> (by overriding and implementing this simple method) and fix our sorting of the artist/group names above. We will show you how you can implement it in a class of its own first, then show you how you can implement it as an anonymous local/inner class.

import java.util.Comparator;
public class IgnoreTheComparator implements Comparator<String> {

  @Override
  public int compare(String a, String b) {
    String first = a;
    String second = b;
    if (a.startsWith("The")) {
      first = a.substring(4);
    }
    if (b.startsWith("The")) {
      second = b.substring(4);
    }
    return first.compareTo(second);
  }
}

The test program now becomes:

public class AlbumList {

  public static void main(String[] args) {
    String[] albums = {
      "Yes",
      "The 5,6,7,8s",
      "ABBA",
      "The Beatles",
      "Neil Young",
      "The The",
      "Wasp",
      "The Who",
      "The Them",
      "Beatless"
    };
    java.util.Arrays.sort(albums);
    System.out.println("My sorted albums: " + java.util.Arrays.toString(albums));

    java.util.Arrays.sort(albums, new IgnoreTheComparator());
    System.out.println("My sorted albums: " + java.util.Arrays.toString(albums));
  }
}
/* Output:
$ javac AlbumList.java && java AlbumList
My sorted albums: [ABBA, Beatless, Neil Young, The 5,6,7,8s, The Beatles, The The, The Them, The Who, Wasp, Yes]
My sorted albums: [The 5,6,7,8s, ABBA, The Beatles, Beatless, Neil Young, The The, The Them, Wasp, The Who, Yes]
*/

The IgnoreTheComparator ignores the occurrence of the string "The" at the beginning of any of the strings to compare, simply by removing it if it exists. Then, with any "The" suffices removed, it let's the string first compare itself to the string second.

Here's how we could accomplish the same comparator without using a dedicated class, but instead creating the comparator as an anonymous inner class:

public class AlbumList {

  public static void main(String[] args) {
    String[] albums = {
      "Yes",
      "The 5,6,7,8s",
      "ABBA",
      "The Beatles",
      "Neil Young",
      "The The",
      "Wasp",
      "The Who",
      "The Them",
      "Beatless"
    };
    java.util.Arrays.sort(albums);
    System.out.println("My sorted albums: " + java.util.Arrays.toString(albums));

    java.util.Arrays.sort(albums, new java.util.Comparator<String>() {
        @Override
          public int compare(String a, String b) {
          String first = a;
          String second = b;
          if (a.startsWith("The")) {
            first = a.substring(4);
          }
          if (b.startsWith("The")) {
            second = b.substring(4);
          }
          return first.compareTo(second);
        }
      });
    System.out.println("Sorted using an anonymous inner class: " + java.util.Arrays.toString(albums));
  }
}

It is worth noticing here, that the search method java.util.Arrays.binarySearch() in its simple form looks in a sorted array using binary search with comparisons from the natural ordering of the elements. The natural ordering of String objects are the lexicographic order, which we didn't like for artist/group names. So we will not be able to find an element using binarySearch in its simple form. We have to pass along a reference to the same comparator which was used when sorting the array. The first if-statement fails its test and shows that we can't find "The Who" in the array using the simple version of binarySearch(). The second if-statements succeeds its test, and we're able to find "The Who", using an IgnoreTheComparator again.

public class AlbumList{
  public static void main(String[] args){
    String[] albums = {
      "Yes",
      "The 5,6,7,8s",
      "ABBA",
      "The Beatles",
      "Neil Young",
      "The The",
      "Wasp",
      "The Who",
      "The Them",
      "Beatless"
    };
    java.util.Arrays.sort(albums);
    System.out.println("My sorted albums: " + java.util.Arrays.toString(albums));

    java.util.Arrays.sort(albums, new IgnoreTheComparator());
    System.out.println("My sorted albums: " + java.util.Arrays.toString(albums));
    
    int index = java.util.Arrays.binarySearch(albums, "The Who");

    if (index < 0) {
      System.out.println("Couldn't find them");
    } else {
      System.out.println("They were at index: " +index);
    }

    index = java.util.Arrays.binarySearch(albums, "The Who", new IgnoreTheComparator());
    if (index < 0) {
      System.out.println("Couldn't find them");
    } else {
      System.out.println("Now it worked! They were at index: " +index);
    }
  }
}
/* Output:
My sorted albums: [ABBA, Beatless, Neil Young, The 5,6,7,8s, The Beatles, The The, The Them, The Who, Wasp, Yes]
My sorted albums: [The 5,6,7,8s, ABBA, The Beatles, Beatless, Neil Young, The The, The Them, Wasp, The Who, Yes]
Couldn't find them
Now it worked! They were at index: 8
*/

If you want to know what's so interesting about binary search (it is quite interesting actually!), you can read about it here. But it is quite outside of the scope of this chapter. It is enough if you know that it is a very quick way to search a sorted collection of objects. The version in java.util.Arrays returns a negative number if it can't find the key we're looking for, and the index of the key otherwise.

The point of all this was to show you that thanks to the strategy pattern, we can encapsulate for instance comparisons of objects to a dedicated object of some interface type. This allowed the authors of the sorting methods to implement sorting without knowing (or caring about) how the comparisons between objects took place. This in turn, allows us to sort the same list using different criteria for how to compare (how to order) the objects, without having to change neither the objects' classes (for instance String), nor the sorting algorithm. The sorting algorithm was open for extension (we just added a completely new way to order strings!) but closed for modification (we didn't have to wait for a method called "sortStringsButIgnoreIfTheyStartWithTHE()" to be written for us).

Another example

Another example of the strategy pattern in the Java API comes from Swing. Containers contain components, and those components are laid out according to some strategy. For instance, a FlowLayout lays out the components in one row until the container width forces the row to wrap. A BorderLayout has five areas, NORTH, SOUTH, EAST, WEST and CENTER. Components put in the different areas will behave a differently when it comes to calculating preferred size (for instance components in the NORTH and SOUTH areas stretch out maximally horizontally but keep their preferred height, and in EAST and WEST the opposite holds, while in CENTER, they stretch out in all dimensions).

Rather than having versions of all the layouts for each container, the designers encapsulated the layout to a layout object (such as an object of type FlowLayout). This also allows a component to change its layout in runtime as shown by the following stupid example:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class LayoutChanger {

  private JButton first;
  private JButton second;
  private JButton third;
  private JButton fourth;
  private JFrame frame;
  private JPanel panel;
  private boolean isGrid;

  public LayoutChanger() {
    initComponents();
    layoutComponents();
    frame.setVisible(true);
  }

  private void initComponents() {
    frame = new JFrame("Layout changer");
    frame.setLayout(new BorderLayout());
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    panel = new JPanel();
    panel.setLayout(new FlowLayout());
    first = new JButton("First");
    second = new JButton("Second");
    third = new JButton("Third");
    fourth = new JButton("Click me!");
    fourth.addActionListener(new ActionListener() {
        @Override
        public void actionPerformed(ActionEvent ae) {
          if (isGrid) {
            System.out.println("changing to flow");
            panel.setLayout(new FlowLayout());
            frame.pack();
          } else {
            System.out.println("changing to grid");
            panel.setLayout(new GridLayout(2,2));
            frame.pack();
          }
          isGrid = !isGrid;
        }
      });
  }

  private void layoutComponents() {
    panel.add(first);
    panel.add(second);
    panel.add(third);
    panel.add(fourth);
    frame.add(panel, BorderLayout.CENTER);
    frame.pack();
  }

  public static void main(String[] args) {
    new LayoutChanger();
  }
}

It's the fourth button which will make the layout change in runtime:

    fourth.addActionListener(new ActionListener() {
        @Override
        public void actionPerformed(ActionEvent ae) {
          if (isGrid) {
            System.out.println("changing to flow");
            panel.setLayout(new FlowLayout());
            frame.pack();
          } else {
            System.out.println("changing to grid");
            panel.setLayout(new GridLayout(2,2));
            frame.pack();
          }
          isGrid = !isGrid;
        }
      });

Exercises

Task 1 - Write a filter using the strategy pattern

Consider the following scenario. We have an Album class for albums in our record collection. And we have a method for printing a whole list of albums. But we want to print somtimes filtered on genre. Perhaps I want to print a list of all albums except for the Pop albums. Or I want to print a list of only the Pop albums. But most of all, I want to adhere to the open-closed principle, so I don't want to write a new print method for every type of filter. In the first version, the only filtering I'm interested in is by genre (like Pop, Rock, Classical etc).

At least, write and test one filter for excluding pop music albums.

Here are the classes for Album and the printing program (a test program which creates and prints albums):

/* Album.java */
public class Album {

  public enum Genre {
    POP("Pop"),
    ROCK("Rock"),
    CLASSICAL("Classical"),
    OTHER("Other");
    private String genre;
    Genre(String genre) { this.genre=genre; }
    public String toString() { return genre; }
  }

  private Genre genre;
  private String title;
  private String artist;

  public Album(String title, String artist, Genre genre) {
    this.title = title;
    this.artist= artist;
    this.genre = genre;
  }

  public String artist() { return artist; }
  public String title() { return title; }
  public String genre() { return genre.toString(); }

  public String toString() {
    return new StringBuilder(title)
      .append(" by ")
      .append(artist)
      .append(" (").append(genre.toString()).append(")")
      .toString();
  }
}

/* TestAlbum.java */
public class TestAlbum {

  public static void main(String[] args) {
    Album[] albums = {
      new Album("Hotel California", "Eagles", Album.Genre.ROCK),
      new Album("Best of", "J.S. Bach", Album.Genre.CLASSICAL),
      new Album("Arrival", "ABBA", Album.Genre.POP),
      new Album("Hemma hos 1", "Janne & Kjell", Album.Genre.OTHER),
      new Album("White album", "Beatles", Album.Genre.POP),
      new Album("Best of", "Mozart", Album.Genre.CLASSICAL),
      new Album("Thank you for the music", "ABBA", Album.Genre.POP)
    };
    printAlbums(albums);
  }

  static void printAlbums(Album[] albums) {
    for(Album a : albums) {
      System.out.println(a);
    }
  }
}

Your task is to create a filtering scheme which allows client code to pass along a filter object to printAlbums() so that it can check each album if it is permitted before printing it. See hints below if you don't know where to start.

Challenge - 1

Write a couple of genre filters as anonymous inner classes as arguments to printAlbums().

Challenge - 2

Change the scheme so that the filter is a general filter (not only for genres). This is only a matter of changing the name! AlbumFilter is now a better name - the rest stays the same (you must change the signature of the printAlbums() method of course, but that's it).

Add some fields to Album, like "int rating" (your own rating of an album on a scale 1-10). Write filters which can be used for writing only albums with a rating over some level.

Hints

Write a filter interface (e.g. GenreFilter) with only one abstract method boolean permit(Album a);. Write filter classes which implement the interface (and the method). Change printAlbums so that it takes one more argument, a reference to a GenreFilter. Change the for-loop so that it only prints if checking the current album against the filter's method returns true.

Suggested solutions

Expand using link to the right to see the full content.

You can download source code including suggested solutions here (github). But here are the source code for the suggested solutions:

// GenreFilter.java
public interface GenreFilter {
  public boolean permit(Album a);
}

//NoPopFilter.java
public class NoPopFilter implements GenreFilter {
  @Override
  public boolean permit(Album album) {
    return !album.genre().equals("Pop");
  }
}

//OnlyPopFilter.java
public class OnlyPopFilter implements GenreFilter {
  @Override
  public boolean permit(Album album) {
    return album.genre().equals("Pop");
  }
}

//TestAlbum.java
public class TestAlbum {

  public static void main(String[] args) {
    Album[] albums = {
      new Album("Hotel California", "Eagles", Album.Genre.ROCK),
      new Album("Best of", "J.S. Bach", Album.Genre.CLASSICAL),
      new Album("Arrival", "ABBA", Album.Genre.POP),
      new Album("Hemma hos 1", "Janne & Kjell", Album.Genre.OTHER),
      new Album("White album", "Beatles", Album.Genre.POP),
      new Album("Best of", "Mozart", Album.Genre.CLASSICAL),
      new Album("Thank you for the music", "ABBA", Album.Genre.POP)
    };
    System.out.println("No pop, please!");
    printAlbums(albums, new NoPopFilter());
    System.out.println("Changed my mind. Erase and rewind!");
    printAlbums(albums, new OnlyPopFilter());
  }

  static void printAlbums(Album[] albums, GenreFilter filter) {
    for(Album a : albums) {
      if (filter.permit(a)) {
        System.out.println(a);
      }
    }
  }
}

An alternative solution, using Java 8 streams and lambda (with Predicate):

import java.util.function.Predicate;
import java.util.Arrays;

public class SortAlbums {
  public static void main(String[] args) {
    Album[] albums = fetchAlbums();
    System.out.println("Pop albums:");
    printSomeAlbums(albums, a -> a.genre().equals(Album.Genre.POP.toString()));
    System.out.println();
    System.out.println("Non-Pop albums:");
    printSomeAlbums(albums, a -> !a.genre().equals(Album.Genre.POP.toString()));
  }

  private static Album[] fetchAlbums() {
    Album[] albums = {
      new Album("Hotel California", "Eagles", Album.Genre.ROCK),
      new Album("Best of", "J.S. Bach", Album.Genre.CLASSICAL),
      new Album("Arrival", "ABBA", Album.Genre.POP),
      new Album("Hemma hos 1", "Janne & Kjell", Album.Genre.OTHER),
      new Album("White album", "Beatles", Album.Genre.POP),
      new Album("Best of", "Mozart", Album.Genre.CLASSICAL),
      new Album("Thank you for the music", "ABBA", Album.Genre.POP)
    };
    return albums;
  }

  private static void printSomeAlbums(Album[] albums, Predicate<Album> filter) {
    Arrays.asList(albums).stream().filter(filter).forEach(System.out::println);
  }
}

Example run:

$ javac SortAlbums.java && java SortAlbums
Pop albums:
Arrival by ABBA (Pop)
White album by Beatles (Pop)
Thank you for the music by ABBA (Pop)

Non-Pop albums:
Hotel California by Eagles (Rock)
Best of by J.S. Bach (Classical)
Hemma hos 1 by Janne & Kjell (Other)
Best of by Mozart (Classical)

Chapter links

Videos

Source code

Books this chapter is a part of

Further reading

Book TOC | previous chapter | next chapter