Labels

Thursday, November 18, 2010

Strategy Design Pattern - Behavioural

1.1     Definition


Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.
               

1.2     Intent


The strategy pattern (also known as the policy pattern) is a particular software design pattern, whereby algorithms can be selected at runtime.
The strategy pattern is useful for situations where it is necessary to dynamically swap the algorithms used in an application.

The strategy pattern is intended to provide a means to define a family of algorithms, encapsulate each one as an object, and make them interchangeable. The strategy pattern lets the algorithms vary independently from clients that use them.

In some programming languages, such as those without polymorphism, the issues addressed by this pattern are handled through forms of reflection, such as the native function pointer or function delegate syntax.

1.3     Motivation


A program that requires a particular service or function and that has several ways of carrying out that function is a candidate for the Strategy pattern. Programs choose between these algorithms based on computational efficiency or user choice. There can be any number of strategies, more can be added, and any of them can be changed at any time.
There are a number of cases in programs where we'd like to do the same thing in several different ways. Some of these are listed in the Smalltalk Companion.

·         Save files in different formats.
·         Compress files using different algorithms
·         Capture video data using different compression schemes.
·         Use different line-breaking strategies to display text data.
·         Plot the same data in different formats: line graph, bar chart, or pie chart.

In each case we could imagine the client program telling a driver module (Context) which of these strategies to use and then asking it to carry out the operation.

The idea behind Strategy is to encapsulate the various strategies in a single module and provide a simple interface to allow choice between these strategies. Each of them should have the same programming interface, although they need not all be members of the same class hierarchy.
However, they do have to implement the same programming interface.

1.4     Applicability


Use the Strategy pattern whenever:
·         Many related classes differ only in their behavior
·         You need different variants of an algorithm
·         An algorithm uses data that clients shouldn't know about. Use the Strategy pattern to avoid exposing complex, algorithm-specific data structures.
·         A class defines many behaviors, and these appear as multiple conditional statements in its operations. Instead of many conditionals, move related conditional branches into their own Strategy class.

1.5     Consequences


Strategy allows you to select one of several algorithms dynamically. These algorithms can be related in an inheritance hierarchy, or they can be unrelated as long as they implement a common interface. Since the Context switches between strategies at your request, you have more flexibility than if you simply called the desired derived class. This approach also avoids the sort of condition statements that can make code hard to read and maintain.

On the other hand, strategies don't hide everything. The client code is usually aware that there are a number of alternative strategies, and it has some criteria for choosing among them. This shifts an algorithmic decision to the client programmer or the user.

Since there are a number of different parameters that you might pass to different algorithms, you have to develop a Context interface and strategy methods that are broad enough to allow for passing in parameters that are not used by that particular algorithm.



1.6     Structure





1.7     Participants

The classes and/or objects participating in this pattern are:

  • Strategy  (SortStrategy)
    • declares an interface common to all supported algorithms. Context uses this interface to call the algorithm defined by a ConcreteStrategy
  • ConcreteStrategy  (QuickSort, ShellSort, MergeSort)
    • implements the algorithm using the Strategy interface
  • Context  (SortedList)
    • is configured with a ConcreteStrategy object
    • maintains a reference to a Strategy object
    • may define an interface that lets Strategy access its data.            


1.8     Sample Code


This structural code demonstrates the Strategy pattern which encapsulates functionality in the form of an object. This allows clients to dynamically change algorithmic strategies.



class Context
    {
        Strategy strategy;

        public Context(Strategy strategy)
        {
            this.strategy = strategy;
        }

        public void ContextInterface()
        {
            strategy.AlgorithmInterface();
        }
    }
abstract class Strategy
    {
        public abstract void AlgorithmInterface();
    }

class ConcreteStrategyA : Strategy
    {
        public override void AlgorithmInterface()
        {
            Console.WriteLine("ConcreteStrategyA");
        }
    }

class ConcreteStrategyB : Strategy
    {
        public override void AlgorithmInterface()
        {
            Console.WriteLine("ConcreteStrategyB");
        }
    }

class ConcreteStrategyC : Strategy
    {
        public override void AlgorithmInterface()
        {
            Console.WriteLine("ConcreteStrategyC");
        }
    }



class MainApp
    {
        static void Main()
        {
            Context context;

            context = new Context(new ConcreteStrategyA());
            context.ContextInterface();

            context = new Context(new ConcreteStrategyB());
            context.ContextInterface();

            context = new Context(new ConcreteStrategyC());
            context.ContextInterface();
        }
    }




1.9     Sample Code 2

This real-world code demonstrates the Strategy pattern which encapsulates sorting algorithms in the form of sorting objects. This allows clients to dynamically change sorting strategies including Quicksort, Shellsort, and Mergesort.



class MySortedList
{
       private ArrayList list = new ArrayList();
       private SortStrategy sortstrategy;

       public void Add(string name)
       {
              list.Add(name);
       }

       public void SetSortStrategy(SortStrategy sortstrategy)
       {     
              this.sortstrategy = sortstrategy;
       }

       public void Sort()
       {
              sortstrategy.Sort(list);

              foreach (string name in list)
              {
                     Console.WriteLine(" " + name);
              }
              Console.WriteLine();
       }
}
    abstract class SortStrategy
    {
        public abstract void Sort(ArrayList list);
    }
    class QuickSort : SortStrategy
    {
        public override void Sort(ArrayList list)
        {
            list.Sort(); // Default is Quicksort
            Console.WriteLine("QuickSorted list ");
        }
    }

class ShellSort : SortStrategy
    {
        public override void Sort(ArrayList list)
        {
            //list.ShellSort(); not-implemented
            Console.WriteLine("ShellSorted list ");
        }
    }
class MergeSort : SortStrategy
    {
        public override void Sort(ArrayList list)
        {
            //list.MergeSort(); not-implemented
            Console.WriteLine("MergeSorted list ");
        }
    }




class MainApp
    {
        static void Main()
        {
            MySortedList studentRecords = new MySortedList ();

            studentRecords.Add("Samual");
            studentRecords.Add("Jimmy");
            studentRecords.Add("Sandra");
            studentRecords.Add("Vivek");
            studentRecords.Add("Anna");

            studentRecords.SetSortStrategy(new QuickSort());
            studentRecords.Sort();

            studentRecords.SetSortStrategy(new ShellSort());
            studentRecords.Sort();

            studentRecords.SetSortStrategy(new MergeSort());
            studentRecords.Sort();

            // Wait for user
            Console.Read();
        }
    }

1.10  Sample Code 3

Frequently with applications many of the operations they perform are dynamic depending on several factors. Think about a common scenario, sales tax. Tax amounts are based off the place where you live. There are many different tax rates in each country. A good method of implementing dynamic patterns like taxes is needed. The strategy pattern covers this gap for us.

The strategy pattern is very useful when a dynamic formula or data is needed. In our situation it will allow us to swap out different tax objects when needed. The pattern lets a class take on many different behaviors depending on the context in which it is used.

The strategy patterns starts with an interface that defines the methods that each different behavior defines. Our tax interface is simple, only one method that returns the (full amount of the price) * (the tax amount.).




namespace StrategyPattern
{
    public interface ITaxStrategy
    {
        double CalculateTax(double amount);
    }
}
This interface will be implemented in all of our tax strategy classes to give them a common base.

Two simple classes are then created for calculating taxes for the USA and the UK. Both tax rates are made up, 5% for the USA and 7% for the UK.

namespace StrategyPattern
{
    public class USATax : ITaxStrategy
    {
        public USATax()
        {
        }

        public double CalculateTax(double amount)
        {
            return amount * 1.05;
        }
    }
}

namespace StrategyPattern
{
    public class UKTax : ITaxStrategy
    {
        public UKTax()
        {
        }

        public double CalculateTax(double amount)
        {
            return amount * 1.07;
        }
    }
}

To demonstrate the use of the two classes, we will create a simple inventory item class that represents an item in our stores inventory. The class will just hold the price of the item.

namespace StrategyPattern
{
    public class InventoryItem
    {
        private ITaxStrategy _ItemTax;
        private double _ItemAmount;

        public InventoryItem()
        {
        }

        public void SetTax(ITaxStrategy tax)
        {
            _ItemTax = tax;
        }

        public double ItemAmount
        {
            get { return _ItemAmount; }
            set { _ItemAmount = value; }
        }
        public double ItemWithTax
        {
            get { return _ItemTax.CalculateTax(_ItemAmount); }
        }
    }
}



Now lets examine the code that makes the class use the strategy pattern. A private variable names _ItemTax is declared as type ITaxStrategy. This is our internal representation of which strategy we want the class to use. The SetTax method allows us to set whichever strategy object we need to the inventory item. The property ItemWithTax returns the item's amount with the tax added into it by calling the CalculateTax method on our strategy object.

To see the classes in motion this code can be used.

InventoryItem itm;
itm = new InventoryItem();
itm.ItemAmmount = (double)10;

USATax usaTax;
usaTax = new USATax();

UKTax ukTax;
ukTax = new UKTax();

itm.SetTax(usaTax);
MessageBox.Show(itm.ItemWithTax.ToString());

itm.SetTax(ukTax);            
MessageBox.Show(itm.ItemWithTax.ToString());

The first thing we do is create an object of the InventoryItem class. We then create a US tax object and a UK tax object. After setting the tax object to our inventory class, the message boxes show the result. You will get 10.5 for the first tax and 10.7 for the second showing the different strategies in action.

While this is just a demonstration, in a real world application the tax objects would be created dynamically based on a registry key, configuration file, or based on the findings of a reflection call. One technique I have used is to use reflection to query the install directory for a class that implements the ITaxStrategy interface. When the product is installed, the user chooses what region they are in and the correct dll with the tax class is installed. Reflection can then find this class and create an instance of it on the fly to pass to the inventory class.

1.11  Strategy in MSDN


Both Array and ArrayList provide the capability to sort the objects contained in the collection via the Sort method. In fact, ArrayList.Sort just calls Sort on the underlying array. These methods use the QuickSort algorithm. By default, the Sort method will use the IComparable implementation for each element to handle the comparisons necessary for sorting. Sometimes, though, it is useful to sort the same list in different ways. For example, arrays of strings might be sorted with or without case sensitivity.
To accomplish this, an overload of Sort exists that takes an IComparer as a parameter; IComparer.Compare is then used for the comparisons. This overload allows users of the class to use any of the built-in IComparers or any of their own making, without having to change or even know the implementation details of Array, ArrayList, or the QuickSort algorithm.

Leaving the choice of comparison algorithm up to the user of the class like this is an example of the Strategy pattern. The use of Strategy lets a variety of different algorithms be used interchangeably. QuickSort itself only requires a way to compare objects to each other. By calling Compare through a provided interface, the caller is free to substitute whatever particular comparison algorithm fits its specific needs. The code for the QuickSort can remain unchanged.

Note: In this example, the IComparer interface is implemented using the System.Collections.CaseInsensitiveComparer class to reverse the order of the contents of the ArrayList.




using System;
using System.Collections;

public class SamplesArrayList  {

   public class myReverserClass : IComparer  {

      int IComparer.Compare( Object x, Object y ) 
      {
          return( (new CaseInsensitiveComparer()).Compare( y, x ) );
      }

   }

   public static void Main()  {

      // Creates and initializes a new ArrayList.
      ArrayList myAL = new ArrayList();
      myAL.Add( "The" );
      myAL.Add( "quick" );
      myAL.Add( "brown" );
      myAL.Add( "fox" );
      myAL.Add( "jumps" );
      myAL.Add( "over" );
      myAL.Add( "the" );
      myAL.Add( "lazy" );
      myAL.Add( "dog" );

      // Displays the values of the ArrayList.
      Console.WriteLine( "The ArrayList initially contains the following values:" );
      PrintIndexAndValues( myAL );

      // Sorts the values of the ArrayList using the default comparer.
      myAL.Sort();
      Console.WriteLine( "After sorting with the default comparer:" );
      PrintIndexAndValues( myAL );

      // Sorts the values of the ArrayList using the reverse case-insensitive comparer.
      IComparer myComparer = new myReverserClass();
      myAL.Sort( myComparer );
      Console.WriteLine( "After sorting with the reverse case-insensitive comparer:" );
      PrintIndexAndValues( myAL );

   }

   public static void PrintIndexAndValues( IEnumerable myList )  {
      int i = 0;
      foreach ( Object obj in myList )
         Console.WriteLine( "\t[{0}]:\t{1}", i++, obj );
      Console.WriteLine();
   }

}



/*
This code produces the following output.
The ArrayList initially contains the following values:
        [0]:    The
        [1]:    quick
        [2]:    brown
        [3]:    fox
        [4]:    jumps
        [5]:    over
        [6]:    the
        [7]:    lazy
        [8]:    dog

After sorting with the default comparer:
        [0]:    brown
        [1]:    dog
        [2]:    fox
        [3]:    jumps
        [4]:    lazy
        [5]:    over
        [6]:    quick
        [7]:    the
        [8]:    The

After sorting with the reverse case-insensitive comparer:
        [0]:    the
        [1]:    The
        [2]:    quick
        [3]:    over
        [4]:    lazy
        [5]:    jumps
        [6]:    fox
        [7]:    dog
        [8]:    brown
*/



Thanks & Regards,
Arun Manglick

No comments:

Post a Comment