22. TEMPLATE METHOD and STRATEGY: Inheritance versus Delegation

image

© Jennifer M. Kohnke

The best strategy in life is diligence.

—Chinese proverb

In the early 1990s—in the early days of OO—we were all quite taken with the notion of inheritance. The implications of the relationship were profound. With inheritance, we could program by difference! That is, given a class that did something almost useful to us, we could create a subclass and change only the bits we didn’t like. We could reuse code simply by inheriting it! We could establish whole taxonomies of software structures, each level of which reused code from the levels above. It was a brave new world.

Like most brave new worlds, this one turned out to be a bit too starry-eyed. By 1995, it was clear that inheritance was very easy to overuse and that overuse of inheritance was very costly. Gamma, Helm, Johnson, and Vlissides went so far as to stress: “Favor object composition over class inheritance.”1 So we cut back on our use of inheritance, often replacing it with composition or delegation.

This chapter is the story of two patterns that epitomize the difference between inheritance and delegation. TEMPLATE METHOD and STRATEGY solve similar problems and can often be used interchangeably. However, TEMPLATE METHOD uses inheritance to solve the problem, whereas STRATEGY uses delegation.

Both TEMPLATE METHOD and STRATEGY solve the problem of separating a generic algorithm from a detailed context. We frequently see the need for this in software design. We have an algorithm that is generically applicable. In order to conform to the Dependency-Inversion Principle (DIP), we want to make sure that the generic algorithm does not depend on the detailed implementation. Rather, we want the generic algorithm and the detailed implementation to depend on abstractions.

Template Method

Consider all the programs you have written. Many probably have this fundamental main loop structure:

Initialize();
while (!Done()) // main loop
{
  Idle();       // do something useful.
}
Cleanup();

First, we initialize the application. Then we enter the main loop, where we do whatever the program needs to do. We might process GUI events or perhaps database records. Finally, once we are done, we exit the main loop and clean up before we exit.

This structure is so common that we can capture it in a class named Application. Then we can reuse that class for every new program we want to write. Think of it! We never have to write that loop again!2

For example, consider Listing 22-1. Here, we see all the elements of the standard program. The TextReader and TextWriter are initialized. A Main loop reads Fahrenheit readings from the Console.In and prints out Celsius conversions. At the end, an exit message is printed.


Listing 22-1. FtoCRaw.cs

using System;
using System.IO;

public class FtoCRaw
{
  public static void Main(string[] args)
  {
    bool done = false;
    while (!done)
    {
      string fahrString = Console.In.ReadLine();
      if (fahrString == null || fahrString.Length == 0)
        done = true;
      else
      {
        double fahr = Double.Parse(fahrString);
        double celcius = 5.0/9.0*(fahr - 32);
        Console.Out.WriteLine("F={0}, C={1}",fahr,celcius);
      }
    }
    Console.Out.WriteLine("ftoc exit");
  }
}


This program has all the elements of the preceding main loop structure. It does a little initialization, does its work in a Main loop, and then cleans up and exits.

We can separate this fundamental structure from the ftoc program by using the TEMPLATE METHOD pattern. This pattern places all the generic code into an implemented method of an abstract base class. The implemented method captures the generic algorithm but defers all details to abstract methods of the base class.

So, for example, we can capture the main loop structure in an abstract base class called Application. See Listing 22-2.


Listing 22-2. Application.cs

public abstract class Application
{
  private bool isDone = false;

  protected abstract void Init();
  protected abstract void Idle();
  protected abstract void Cleanup();

  protected void SetDone()
  {
    isDone = true;
  }

  protected bool Done()
  {
    return isDone;
  }

  public void Run()
  {
    Init();
    while (!Done())
      Idle();
    Cleanup();
  }
}


This class describes a generic main-loop application. We can see the main loop in the implemented Run function. We can also see that all the work is being deferred to the abstract methods Init, Idle, and Cleanup. The Init method takes care of any initialization we need done. The Idle method does the main work of the program and will be called repeatedly until SetDone is called. The Cleanup method does whatever needs to be done before we exit.

We can rewrite the ftoc class by inheriting from Application and simply filling in the abstract methods. Listing 22-3 show what this looks like.


Listing 22-3. FtoCTemplateMethod.cs

using System;
using System.IO;

public class FtoCTemplateMethod : Application
{
  private TextReader input;
  private TextWriter output;

  public static void Main(string[] args)
  {
    new FtoCTemplateMethod().Run();
  }

  protected override void Init()
  {
    input = Console.In;
    output = Console.Out;
  }

  protected override void Idle()
  {
    string fahrString = input.ReadLine();
    if (fahrString == null || fahrString.Length == 0)
      SetDone();
    else
    {
      double fahr = Double.Parse(fahrString);
      double celcius = 5.0/9.0*(fahr - 32);
      output.WriteLine("F={0}, C={1}", fahr, celcius);
    }
  }

  protected override void Cleanup()
  {
    output.WriteLine("ftoc exit");
  }
}


It’s easy to see how the old ftoc application has been fit into the TEMPLATE METHOD pattern.

Pattern Abuse

By this time, you should be thinking “Is he serious? Does he really expect me to use this Application class for all new apps? It hasn’t bought me anything, and it’s overcomplicated the problem.”

Er..., Yeah.. :^(

I chose the example because it was simple and provided a good platform for showing the mechanics of TEMPLATE METHOD. On the other hand, I don’t really recommend building ftoc like this.

This is a good example of pattern abuse. Using TEMPLATE METHOD for this particular application is ridiculous. It complicates the program and makes it bigger. Encapsulating the main loop of every application in the universe sounded wonderful when we started, but the practical application is fruitless in this case.

Design patterns are wonderful things. They can help you with many design problems. But the fact that they exist does not mean that they should always be used. In this case, TEMPLATE METHOD was applicable to the problem, but its use was not advisable. The cost of the pattern was higher than the benefit it yielded.

Bubble Sort

So let’s look at a slightly more useful example. See Listing 22-4. Note that like Application, Bubble Sort is easy to understand, and so makes a useful teaching tool. However, no one in their right mind would ever use Bubble Sort if they had any significant amount of sorting to do. There are much better algorithms.

image


Listing 22-4. BubbleSorter.cs

public class BubbleSorter
{
  static int operations = 0;
  public static int Sort(int [] array)
  {
    operations = 0;
    if (array.Length <= 1)
      return operations;

    for (int nextToLast = array.Length-2;
      nextToLast >= 0; nextToLast--)
      for (int index = 0; index <= nextToLast; index++)
        CompareAndSwap(array, index);

    return operations;
  }

  private static void Swap(int[] array, int index)
  {
    int temp = array[index];
    array[index] = array[index+1];
    array[index+1] = temp;
  }

  private static void CompareAndSwap(int[] array, int index)
  {
    if (array[index] > array[index+1])
      Swap(array, index);
    operations++;
  }
}


The BubbleSorter class knows how to sort an array of integers, using the bubble sort algorithm. The Sort method of BubbleSorter contains the algorithm that knows how to do a bubble sort. The two ancillary methods—Swap and CompareAndSwap—deal with the details of integers and arrays and handle the mechanics that the Sort algorithm requires.

Using the TEMPLATE METHOD pattern, we can separate the bubble sort algorithm out into an abstract base class named BubbleSorter.BubbleSorter contains a Sort function implementation that calls an abstract method named OutOfOrder and another called Swap. The OutOfOrder method compares two adjacent elements in the array and returns true if the elements are out of order. The Swap method swaps two adjacent cells in the array.

The Sort method does not know about the array; nor does it care what kinds of objects are stored in the array. It simply calls OutOfOrder for various indices into the array and determines whether those indices should be swapped. See Listing 22-5.


Listing 22-5. BubbleSorter.cs

public abstract class BubbleSorter
{
  private int operations = 0;
  protected int length = 0;

  protected int DoSort()
  {
    operations = 0;
    if (length <= 1)
      return operations;

    for (int nextToLast = length-2;
      nextToLast >= 0; nextToLast--)
      for (int index = 0; index <= nextToLast; index++)
      {
        if (OutOfOrder(index))
          Swap(index);
        operations++;
      }

    return operations;
  }

  protected abstract void Swap(int index);
  protected abstract bool OutOfOrder(int index);
}


Given BubbleSorter, we can now create simple derivatives that can sort any different kind of object. For example, we could create IntBubbleSorter, which sorts arrays of integers, and DoubleBubbleSorter, which sorts arrays of doubles. See Figure 22-1 and Listings 22-6, and 22-7.

Figure 22-1. Bubble sorter structure

image

The TEMPLATE METHOD pattern shows one of the classic forms of reuse in object-oriented programming. Generic algorithms are placed in the base class and inherited into different detailed contexts. But this technique is not without its costs. Inheritance is a very strong relationship. Derivatives are inextricably bound to their base classes.


Listing 22-6. IntBubbleSorter.cs

public class IntBubbleSorter : BubbleSorter
{
  private int[] array = null;

  public int Sort(int[] theArray)
  {
    array = theArray;
    length = array.Length;
    return DoSort();
  }

  protected override void Swap(int index)
  {
    int temp = array[index];
    array[index] = array[index + 1];
    array[index + 1] = temp;
  }

  protected override bool OutOfOrder(int index)
  {
    return (array[index] > array[index + 1]);
  }
}



Listing 22-7. DoubleBubbleSorter.cs

public class DoubleBubbleSorter : BubbleSorter
{
  private double[] array = null;

  public int Sort(double[] theArray)
  {
    array = theArray;
    length = array.Length;
    return DoSort();
  }

  protected override void Swap(int index)
  {
    double temp = array[index];
    array[index] = array[index + 1];
    array[index + 1] = temp;
  }

  protected override bool OutOfOrder(int index)
  {
    return (array[index] > array[index + 1]);
  }
}


For example, the OutOfOrder and Swap functions of IntBubbleSorter are exactly what are needed for other kinds of sort algorithms. But there is no way to reuse OutOfOrder and Swap in those other sort algorithms. By inheriting BubbleSorter, we have doomed IntBubbleSorter to be forever bound to BubbleSorter. The STRATEGY pattern provides another option.

Strategy

The STRATEGY pattern solves the problem of inverting the dependencies of the generic algorithm and the detailed implementation in a very different way. Consider once again the pattern-abusing Application problem.

Rather than placing the generic application algorithm into an abstract base class, we place it into a concrete class named ApplicationRunner. We define the abstract methods that the generic algorithm must call within an interface named Application. We derive FtoCStrategy from this interface and pass it into the ApplicationRunner. ApplicationRunner then delegates to this interface. See Figure 22-2 and Listings 22-8 through 22-10.

Figure 22-2. STRATEGY structure of the Application algorithm

image

It should be clear that this structure has both benefits and costs over the TEMPLATE METHOD structure. STRATEGY involves more total classes and more indirection than TEMPLATE METHOD. The delegation pointer within ApplicationRunner incurs a slightly higher cost in terms of runtime and data space than inheritance would. On the other hand, if we had many different applications to run, we could reuse the ApplicationRunner instance and pass in many different implementations of Application, thereby reducing the code space overhead.

None of these costs and benefits are overriding. In most cases, none of them matters in the slightest. In the typical case, the most worrisome is the extra class needed by the STRATEGY pattern. However, there is more to consider.

Consider an implementation of the bubble sort that uses the STRATEGY pattern. See Listings 22-11 through 22-13.


Listing 22-8. ApplicationRunner.cs

public class ApplicationRunner
{
  private Application itsApplication = null;

  public ApplicationRunner(Application app)
  {
    itsApplication = app;
  }
  public void run()
  {
    itsApplication.Init();
    while (!itsApplication.Done())
      itsApplication.Idle();
    itsApplication.Cleanup();
  }
}



Listing 22-9. Application.cs

public interface Application
{
  void Init();
  void Idle();
  void Cleanup();
  bool Done();
}



Listing 22-10. FtoCStrategy.cs

using System;
using System.IO;

public class FtoCStrategy : Application
{
  private TextReader input;
  private TextWriter output;
  private bool isDone = false;

  public static void Main(string[] args)
  {
    (new ApplicationRunner(new FtoCStrategy())).run();
  }

  public void Init()
  {
    input = Console.In;
    output = Console.Out;
  }

  public void Idle()
  {
    string fahrString = input.ReadLine();
    if (fahrString == null || fahrString.Length == 0)
      isDone = true;
    else
    {
      double fahr = Double.Parse(fahrString);
      double celcius = 5.0/9.0*(fahr - 32);
      output.WriteLine("F={0}, C={1}", fahr, celcius);
    }
  }

  public void Cleanup()
  {
    output.WriteLine("ftoc exit");
  }

  public bool Done()
  {
    return isDone;
  }
}



Listing 22-11. BubbleSorter.cs

public class BubbleSorter
{
  private int operations = 0;
  private int length = 0;
  private SortHandler itsSortHandler = null;

  public BubbleSorter(SortHandler handler)
  {
    itsSortHandler = handler;
  }

public int Sort(object array)
{
  itsSortHandler.SetArray(array);
  length = itsSortHandler.Length();
  operations = 0;
  if (length <= 1)
    return operations;

  for (int nextToLast = length - 2;
    nextToLast >= 0; nextToLast--)
    for (int index = 0; index <= nextToLast; index++)
    {
      if (itsSortHandler.OutOfOrder(index))
        itsSortHandler.Swap(index);
      operations++;
    }

  return operations;
}



Listing 22-12. SortHandler.cs

public interface SortHandler
{
  void Swap(int index);
  bool OutOfOrder(int index);
  int Length();
  void SetArray(object array);
}



Listing 22-13. IntSortHandler.cs

public class IntSortHandler : SortHandler
{
  private int[] array = null;

  public void Swap(int index)
  {
    int temp = array[index];
    array[index] = array[index + 1];
    array[index + 1] = temp;
  }

  public void SetArray(object array)
  {
    this.array = (int[]) array;
  }

  public int Length()

  {
    return array.Length;
  }

  public bool OutOfOrder(int index)
  {
    return (array[index] > array[index + 1]);
  }
}


Note that the IntSortHandler class knows nothing whatever of the BubbleSorter, having no dependency whatever on the bubble sort implementation. This is not the case with the TEMPLATE METHOD pattern. Look back at Listing 22-6, and you can see that the IntBubbleSorter depended directly on BubbleSorter, the class that contains the bubble sort algorithm.

The TEMPLATE METHOD approach partially violates DIP. The implementation of the Swap and OutOfOrder methods depends directly on the bubble sort algorithm. The STRATEGY approach contains no such dependency. Thus, we can use the IntSortHandler with Sorter implementations other than BubbleSorter.

For example, we can create a variation of the bubble sort that terminates early if a pass through the array finds it in order. (See Figure 22-14.) QuickBubbleSorter can also use IntSortHandler or any other class derived from SortHandler.


Listing 22-14. QuickBubbleSorter.cs

public class QuickBubbleSorter
{
  private int operations = 0;
  private int length = 0;
  private SortHandler itsSortHandler = null;

  public QuickBubbleSorter(SortHandler handler)
  {
    itsSortHandler = handler;
  }

  public int Sort(object array)
  {
    itsSortHandler.SetArray(array);
    length = itsSortHandler.Length();
    operations = 0;
    if (length <= 1)
      return operations;

    bool thisPassInOrder = false;
    for (int nextToLast = length-2;
      nextToLast >= 0 && !thisPassInOrder; nextToLast--)

    {
      thisPassInOrder = true; //potenially.
      for (int index = 0; index <= nextToLast; index++)
      {
        if (itsSortHandler.OutOfOrder(index))
        {
          itsSortHandler.Swap(index);
          thisPassInOrder = false;
        }
        operations++;
      }
    }

    return operations;
  }
}


Thus, the STRATEGY pattern provides one extra benefit over the TEMPLATE METHOD pattern. Whereas the TEMPLATE METHOD pattern allows a generic algorithm to manipulate many possible detailed implementations, the STRATEGY pattern, by fully conforming to DIP, additionally allows each detailed implementation to be manipulated by many different generic algorithms.

Conclusion

TEMPLATE METHOD is simple to write and simple to use but is also inflexible. STRATEGY is flexible, but you have to create an extra class, instantiate an extra object, and wire the extra object into the system. So the choice between TEMPLATE METHOD and STRATEGY depends on whether you need the flexibility of STRATEGY or can live with the simplicity of TEMPLATE METHOD. Many times, I have opted for TEMPLATE METHOD simply because it is easier to implement and use. For example, I would use the TEMPLATE METHOD solution to the bubble sort problem unless I was very sure that I needed different sort algorithms.

Bibliography

[GOF95] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.

[PLOPD3] Robert C. Martin, Dirk Riehle, and Frank Buschmann, eds. Pattern Languages of Program Design 3, Addison-Wesley, 1998.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
44.222.146.114