tl  tr
  Home | Tutorials | Articles | Videos | Products | Tools | Search
Interviews | Open Source | Tag Cloud | Follow Us | Bookmark | Contact   
 Design Patterns > Java Design Patterns > Template Method

Template Method 

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,

File Name  :  
com/bethecoder/tutorials/dp/template/IBinarySearch.java 
   
package com.bethecoder.tutorials.dp.template;

/**
 * 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.

File Name  :  
com/bethecoder/tutorials/dp/template/AbstractBinarySearch.java 
   
package com.bethecoder.tutorials.dp.template;

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,

File Name  :  
com/bethecoder/tutorials/dp/template/RecursiveBinarySearch.java 
   
package com.bethecoder.tutorials.dp.template;

import java.util.Arrays;

public class RecursiveBinarySearch extends AbstractBinarySearch {

  @Override
  public String getAlgorithmName() {
    return "Binary Search - Recursive method";
  }

  @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;

    if (searchEle < sortedList[midIndex]) {
      return binarySearchRecursive(sortedList, startIndex, midIndex-1, searchEle);
    } else if (searchEle > sortedList[midIndex]) {
      return binarySearchRecursive(sortedList, midIndex+1, endIndex, searchEle);
    }

    //means searchEle == sortedList[midIndex]
    return midIndex;
  }
}
   

Non Recursive Binary Search implementation is shown below,

File Name  :  
com/bethecoder/tutorials/dp/template/NonRecursiveBinarySearch.java 
   
package com.bethecoder.tutorials.dp.template;

import java.util.Arrays;

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;

      if (searchEle < sortedList[midIndex]) {
        endIndex = midIndex - 1;
      } else if (searchEle > sortedList[midIndex]) {
        startIndex = midIndex + 1;
      } else {
        //means searchEle == sortedList[midIndex]
        return midIndex;
      }
    }

    return -1;
  }
}
   

Template usage is shown below,

File Name  :  
com/bethecoder/tutorials/dp/template/Test.java 
   
package com.bethecoder.tutorials.dp.template;

public class Test {

  /**
   * @param args
   */
  public static void main(String[] args) {

    int [] list = { 3, 2, 4, 6, 8, 0, 12, 5, 9, 13};
    
    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



 
  


  
bl  br