Template method comes under Behavioral design pattern.
Template methods define the flow of an Algorithm.
The algorithm can be split into smaller parts that can vary
for each implementations.
Behaviour & Advantages
Defines the skeleton of an algorithm in an operation, deferring some steps to subclasses.
Sub classes can override or redefine the implementation for any step.
It avoids algorithm code duplication.
Though subclasses have different implementations for each step, Algorithm flow remains the same.
This example shows binary search implementation using recursive and non recursive algorithms.
Binary Search interface is shown below,
/**
* Binary search algorithm.
*/ public interface IBinarySearch { public int search(int [] list, int searchEle);
}
AbstractBinarySearch class defines four abstract methods (algorithm steps) which has to be
implemented by sub classes. The search method acts as a template method and
defines flow of algorithm. We have taken sort as one of the algorithm steps as we know that
the list has to be sorted to perform binary search.
public abstract class AbstractBinarySearch implements IBinarySearch {
/**
* Individual steps defined by template
* which has to be implemented by subclasses.
*/ public abstract String getAlgorithmName(); public abstract void sort(int[] list); public abstract int searchInternal(int[] list, int searchEle); public abstract void showSearchResults(int[] list, int searchEle, int resultIndex);
@Override public int search(int[] list, int searchEle) {
/**
* Flow/Algorithm defined by template
*/
init(getAlgorithmName());
sort(list); int resultIndex = searchInternal(list, searchEle);
showSearchResults(list, searchEle, resultIndex);
return resultIndex;
}
/**
* Common behavior across all implementations.
* @param list
*/ private void init(String algorithmName) {
System.out.println("Searching using : " + algorithmName);
}
}
Recursive Binary Search implementation is shown below,
@Override public void showSearchResults(int[] list, int searchEle, int resultIndex) {
System.out.println(searchEle + " found in the array : " +
Arrays.toString(list) + " at index : " + resultIndex);
}
@Override public void sort(int[] list) {
Arrays.sort(list);
}
@Override public int searchInternal(int[] list, int searchEle) { return binarySearchRecursive(list, 0, list.length, searchEle);
}
private int binarySearchRecursive(int[] sortedList, int startIndex, int endIndex, int searchEle) { if (startIndex > endIndex) { return -1;
}
int midIndex = startIndex + (endIndex - startIndex)/2;
public class NonRecursiveBinarySearch extends AbstractBinarySearch {
@Override public String getAlgorithmName() { return "Binary Search - Non Recursive method";
}
@Override public void showSearchResults(int[] list, int searchEle, int resultIndex) {
System.out.println("In the array " +
Arrays.toString(list) + " element " + searchEle + " found at index : " + resultIndex);
}
@Override public void sort(int[] list) {
Arrays.sort(list);
}
@Override public int searchInternal(int[] list, int searchEle) { return binarySearchNonRecursive(list, 0, list.length, searchEle);
}
private int binarySearchNonRecursive(int[] sortedList, int startIndex, int endIndex, int searchEle) { while (startIndex <= endIndex) { int midIndex = startIndex + (endIndex - startIndex)/2;
IBinarySearch searchAlg = new RecursiveBinarySearch();
searchAlg.search(list, 8);
System.out.println();
searchAlg = new NonRecursiveBinarySearch();
searchAlg.search(list, 9);
}
}
It gives the following output,
Searching using : Binary Search - Recursive method
8 found in the array : [0, 2, 3, 4, 5, 6, 8, 9, 12, 13] at index : 6
Searching using : Binary Search - Non Recursive method
In the array [0, 2, 3, 4, 5, 6, 8, 9, 12, 13] element 9 found at index : 7