Template Delegate Pattern

I've had to use this pattern a few times, most recently in Behave#.  It's similar to the Template Method pattern, but doesn't resort to using subclassing for using a template method.  Instead, a delegate is passed to the Template Method to substitute different logic for portions of the algorithm.

The pattern

Two methods in unrelated classes perform similar general algorithms, yet some parts of the algorithm are different.

Generalize the algorithm by extracting their steps into a new class, then extract methods for the specialized parts into delegates to be passed in to the new class.

Motivation

Helper methods tend to clutter a class with responsibilities orthogonal to its true purpose.  Additionally, several methods in one class might need to perform the same algorithm in slightly different ways.  While Template Method is concerned with removing behavioral duplication, algorithmic duplication can be just as rampant. 

Removing algorithmic duplication through Template Method can make the code more obtuse, as often the abstraction of the template class doesn't add any meaning to the system.  Additionally, sometimes duplicate algorithms are in completely separate classes, and it would be impossible or unwise to try to extract a common subclass from the two classes.  We can remove algorithmic duplication by consolidating the algorithm into its own method or class, and pass in parts of the algorithm that might vary.

Mechanics

• Use Extract Method to separate the purely algorithmic section of each method from any surrounding behavioral code.
• Compile and test.
• Decompose the methods in each algorithm so that all of the steps in the algorithm are identical or completely different.
• For each step in the algorithm that is completely different, use Extract Method to pull out the varying logic.  Name these extracted methods the same.
• Compile and test.
• Optionally, use Introduce Parameter Object for each extracted algorithm method that does not match the same number of parameters for the other different algorithm steps.  Compile and test.
• If there is not an existing delegate type that matches the extracted variant methods of the algorithm, create a delegate type that matches both extracted methods.
• Use Add Parameter and add a new parameter of the delegate type created earlier, and modify the algorithm to use the delegate method to execute the varying logic.  Repeat for both algorithm methods.  Each algorithm method should look exactly the same at this point, except for parameter and return types.
• Compile and test.
• Use Extract Class and Move Method to move the two algorithm methods to a new, generalized (and optionally generic) class.  Modify the calling class to use the new class and methods.
• Compile and test.

Example

Suppose I find the two methods in different classes in a large codebase that do recursive searches.  One finds a Control based on an ID, and the other searches for XmlNodes based on an attribute value:

private Control FindControl(ControlCollection controls)
{
    foreach (Control control in controls)
    {
        if (control.ID == txtControlID.Text)
            return control;

        return FindControl(control.Controls);
    }
}

private XmlNode FindElement(XmlNodeList nodes)
{
    foreach (XmlNode node in nodes)
    {
        if (node.Attributes["ID"].Value == "4564")
            return node;

        return FindElement(node.ChildNodes);
    }
}

Both of these methods perform the exact same logic, a recursive search, but the details are slightly different.

In this example, the first step is already complete and each method contains only the algorithm I'm interested in.  From looking at these methods, it looks like there are 3 distinct parts: the loop, the comparison, and the actual matching logic.  The two differing parts I see in the algorithm are:

• Match
• Get the children based on the current item in the loop

I'll apply Extract Method to pull out the varying logic and name these methods the same.  Here are the extracted methods:

private bool IsMatch(Control control)
{
    return control.ID == txtControlID.Text;
}

private bool IsMatch(XmlNode node)
{
    return node.Attributes["ID"].Value == "4564";
}

private ControlCollection GetChildren(Control control)
{
    return control.Controls;
}

private XmlNodeList GetChildren(XmlNode node)
{
    return node.ChildNodes;
}

Note that the names of each method is the same, as well as the number of parameters.  Now the original algorithm methods call these extracted varying methods:

private Control FindControl(ControlCollection controls)
{
    foreach (Control control in controls)
    {
        if (IsMatch(control))
            return control;

        return FindControl(GetChildren(control));
    }
}

private XmlNode FindElement(XmlNodeList nodes)
{
    foreach (XmlNode node in nodes)
    {
        if (IsMatch(node))
            return node;

        return FindElement(GetChildren(node));
    }
}

These algorithm methods are starting to look very similar.  Next, I need to find a delegate type to represent the varying methods, namely "IsMatch" and "GetChildren".  Since I'm working with Visual Studio 2008, some good candidates already exist with the Func delegate types.  I like these delegate types as they are generic and may lend to some better algorithm definitions in the future, so I'll stick with Func.  Here's the FindControl method after I use Add Parameter to pass in the varying algorithm logic:

private Control FindControl(IEnumerable<Control> controls, 
    Func<Control, bool> predicate,
    Func<Control, IEnumerable<Control>> childrenSelector)
{
    foreach (Control control in controls)
    {
        if (predicate(control))
            return control;

        return FindControl(childrenSelector(control), predicate, childrenSelector);
    }
}

I changed the type of the "controls" parameter to IEnumerable<Control> from ControlCollection, to reduce the number of types seen in the algorithm method.  I change the client code of this algorithm to pass in the new parameters, compile and test:

private void SetLabelText()
{
    string text = txtLabelText.Text;
    string controlID = txtControlID.Text;

    if (string.IsNullOrEmpty(text) || string.IsNullOrEmpty(controlID))
        return;

    Control control = FindControl(page.Controls, IsMatch, GetChildren);
}

Note that the "IsMatch" and "GetChildren" are method names in this class, so I'm passing the matching and children algorithms to the FindControl method for execution when needed.  Finally, I use Extract Class and Move Method to move the two virtually identical algorithm methods to a single method on a new class.  Here's the final result, with some minor changes to use extension methods:

public static T RecursiveSearch<T>(this IEnumerable<T> items,
    Func<T, bool> predicate,
    Func<T, IEnumerable<T>> childrenSelector)
{
    foreach (T item in items)
    {
        if (predicate(item))
            return item;

        return RecursiveSearch(childrenSelector(item), predicate, childrenSelector);
    }

    return default(T);
}

 

I've made the method generic, as the only final variant between the extracted algorithm methods was the type of the item I was finding.  By making the method generic, the return type is strongly typed to the item I'm searching for.  The final client code doesn't look too much different from earlier:

private void SetLabelText()
{
    string text = txtLabelText.Text;
    string controlID = txtControlID.Text;

    if (string.IsNullOrEmpty(text) || string.IsNullOrEmpty(controlID))
        return;

    Control control = page.Controls.Cast<Control>().RecursiveSearch(IsMatch, GetChildren);
}

The client code for the "FindElement" looks exactly the same, and now there is no duplication of the recursive search logic.  I've extracted the varying logic into methods which can be passed in as delegates to the new, generic extracted algorithm.  Since I'm using C# 3.0, I can go as far as using lambda expressions instead of the extracted "IsMatch" and "GetChildren" methods.

Conclusion

The Template Delegate pattern is used quite extensively with the new Enumerable extension methods (such as the Where method).  With delegate creation in C# 3.0 becoming much simpler with lambda expressions, it's becoming easier to compose generalized algorithms where varying portions are passed in as delegate parameters.  By using the Template Delegate pattern, I can reduce the number of junk algorithmic methods into a single generic class that serves the needs of current and future client code.