Strategy Design Pattern C#

Posted on Posted in Uncategorized

So now that we’ve got a few different algorithms (i.e. more than one), let’s see if we can’t streamline adding new ones. In particular, let’s try and give them a generic interface so when we make a new one, all we have to do is add a few lines of code.

What is it?

The strategy design pattern is ideal for problems that have multiple solutions.

Think of it like a war.

In the 18th century nation’s could choose an offensive, defensive, or balanced strategy. This could be further broken down based on the balance between land and sea units the nation wanted to employ.

For Britain, a largely naval based offensive strategy was the order of the day because it played to their strengths and inclinations, whereas France practiced a land based offensive strategy.

In the same way (kind of), we’re going to let the user choose what sorting strategy they prefer.

Note: The below example can be found on github.

How It Works

So far we have two sorting algorithms, insertion sort (github) and merge sort (github), each in its own class.

Anytime you’re looking to give a user one place to choose one (or multiple) items, an interface or base class may be a good idea.

And that’s exactly what we’ll explore here.

At a high level we’ll have a common abstraction that both algorithms leverage. This will give them a common parent object that lets us abstract away the details we don’t care about in the calling function.

Base or Interface?

So our first choice is whether we want to use an interface or a base class.

If we choose an interface then we’ll be using dynamic (each child class will define the details) polymorphism (and the details will be housed in the structure defined in the parent). Here the response to the function is determined at run-time, since the response is based on the implementation of the algorithm in the concrete class derived from the interface (only at runtime is the concrete class chosen, at compile time only the interface is ‘chosen’).

In other words the interface defines the common properties and methods, but doesn’t do anything but state their names/types/signatures.

But if we choose a base class then we’ll be using static (the common details are defined once) polymorphism (the child classes only contain any extension details needed). In this case we have early, or static, binding where the functions in the object are linked during compile time (when compiling, the base class’s functions are leveraged).

Which is just a fancy way of saying the base class has the common details, and then the derived classes add whatever details they need (and can also reference the base class functions as needed).

In our case we’re going to go the interface route because here it’s a bit simpler.

Interface Away

So looking at both of our sort classes, we’ve got a couple commonalities to start out with. Each of them have a name, a Random object, and an integer array that gets populated. That gives us a nice starting point for our interface.

public interface ISort
{
 /// <summary>
 /// The name of the sort algorithm
 /// </summary>
 string Name { get; set; }

 /// <summary>
 /// A random class variable used to populate the array
 /// </summary>
 Random rand { get; set; }

 /// <summary>
 /// A random array of integers
 /// </summary>
 int[] intArrRandom { get; set; }
}

Now each of our sort classes also have to initialize those integer arrays. They’ll also need a way to kick off their sorting algorithms; that sounds like another method to me. So let’s add two methods to our interface.

public interface ISort
{
 /// <summary>
 /// The name of the sort algorithm
 /// </summary>
 string Name { get; set; }

 /// <summary>
 /// A random class variable used to populate the array
 /// </summary>
 Random rand { get; set; }

 /// <summary>
 /// A random array of integers
 /// </summary>
 int[] intArrRandom { get; set; }

 /// <summary>
 /// Initalize the random array of integers
 /// </summary>
 void InitalizeArray();

 /// <summary>
 /// Begin to sort an array
 /// </summary>
 void SortArray();
}

Implement Away

Now we’ve got to go implement our interface. So let’s go into our sort classes and have them inherit from the interface.

public class MergeSort : ISort

....

public class InsertionSort : ISort

So let’s start by making sure that all the properties are implemented for our derived classes.

public class InsertionSort : ISort

{

 public string Name { get; set;}
 public Random rand { get; set; }
 public int[] intArrRandom { get; set; }

....

Now let’s start in on those methods. The first one, IntializeArray, sounds pretty easy so let’s knock that one out. All we’re looking to do here is just populate the array, so this can be the exact same for both derived classes. Note, if we were building a base class this would fit perfectly with that implementation too.

public void InitalizeArray()
{
 // Create an array with a random length
 intArrRandom = new int[rand.Next(2, 100)];
 // For each place in the array
 for (int i = 0; i < intArrRandom.Length; i++)
 {
  // Put a random number in it
  intArrRandom[i] = rand.Next(0, 100);
 }
}

Next up, one SortArray method.

Here we have to really look at the different algorithms and what would be the easiest way to build and maintain them.

The MergeSort is based on recursion and passing variables around. A method that doesn’t take any parameters doesn’t really seem like a great candidate to recurse on… So let’s just have it call a method specific to that derived class that kicks the recursion sort off. Notice that here we’re extending the MergeSort class beyond the scope of the interface, we’ll come back to this point again later.

public void SortArray()
{
 intArrRandom = StartMergeSort(intArrRandom, 0, intArrRandom.Length - 1);
}

Now the InsertionSort doesn’t rely on recursion, it just relies on a loop. So in this case we can be lazy and just put the actual implementation of the sort into the SortArray method. Separating it out into another function doesn’t buy us anything at the moment.

public void SortArray()
{
 // For each place in the array
 for (int intCurrentLocation = 0; intCurrentLocation <  intArrRandom.Count(); intCurrentLocation++)

 {

  // Get the value of the current location
  int intCurrentValue = intArrRandom[intCurrentLocation];

  // Get the prior location
  int intPriorLocation = intCurrentLocation - 1;

  // If the prior location is the first or greater positon
  // And the prior location's value is greater than the current value
  while (intPriorLocation >= 0 && intArrRandom[intPriorLocation] > intCurrentValue)

  {

   // Then we need to move the prior value up one, since it's greater than our current value
   intArrRandom[intPriorLocation + 1] = intArrRandom[intPriorLocation];

   // And move back down the list, looking for a value smaller than our current value
   intPriorLocation = intPriorLocation - 1;

  }

  // Once we've either come to the end of the list or found the current  values proper location
  intArrRandom[intPriorLocation + 1] = intCurrentValue;
 }
}

The User’s Always Right

So we just built an interface! Great! So…. why’d we do all that work again?

Well if we now change our Main function to leverage the interface, it’ll make it about 10x easier to add new algorithms for the user to choose.

Since we’re just using a simple console app for now, we’ll just let the user enter a number to select an algorithm. So we need to correspond a number to an algorithm. Hmmm… a number and an algorithm. That sounds like a basic key-value pair to me, does a List sound good to you? I thought so, let’s do it.

InsertionSort insertSort = new InsertionSort();
MergeSort mergeSort = new MergeSort();

List<ISort> lstr_SortingStrategies = new List<ISort>();

// Add the algorithms to the list
lstr_SortingStrategies.Add(insertSort);
lstr_SortingStrategies.Add(mergeSort);

Now we’ve got to tell the user about their options somehow. Well, this is a console app so we’ve got to write to the console. So let’s make the directions that we’ll give to the user about the numbers (indexes) and the algorithms (names) that they can choose.

string strDirections = "\r\nType 'exit' at any time to close the program.\r\n";
 
// Will hold the algorithm the user chooses to use
ISort sortSelected;

InsertionSort insertSort = new InsertionSort();
MergeSort mergeSort = new MergeSort();

List<ISort> lstr_SortingStrategies = new List<ISort>();

// Add the algorithms to the list
lstr_SortingStrategies.Add(insertSort);
lstr_SortingStrategies.Add(mergeSort);

// Create the directions for them
 foreach(ISort algorithm in lstr_SortingStrategies)
{
 strDirections += string.Format("Press {0} for {1}.\r\n"
 , lstr_SortingStrategies.IndexOf(algorithm)
 , algorithm.Name);
}

Let’s allow the user to sort as many times as they want. So if we just know the user wants to sort at least once, and then keep sorting until they don’t, then we basically have a true/false condition. I don’t know about you, but that sounds an awful like a do/while loop to me.

So let’s start by telling the user about their options and finding out what they’ve selected.

do
{
 // Wait for user to hit a key to continue
 Console.WriteLine(strDirections);

 string strUserInput = Console.ReadLine();

 bool bValidNumber = Int32.TryParse(strUserInput, out iSelectedAlgorithm);
}
 // While the user hasn't entered exit
 while (!String.Equals(strUserInput, "exit", StringComparison.OrdinalIgnoreCase));

So now that the user has selected something we’ve got to validate it and call the appropriate algorithm.

To call the algorithm, we’ll have to get it out of the list based on the number (index) the user selected. Then we’ll have to initialize its array and sort it. Let’s show the user the initial array and the sorted array too, just so they can compare.

do
{
 // Wait for user to hit a key to continue
 Console.WriteLine(strDirections);

 string strUserInput = Console.ReadLine();

 bool bValidNumber = Int32.TryParse(strUserInput, out iSelectedAlgorithm);

 // If it's a valid number, is greater than or equal to zero, and less than the total number of strategies
 if (bValidNumber &&
 iSelectedAlgorithm >= 0 &&
 iSelectedAlgorithm < lstr_SortingStrategies.Count)

{
 // Get the selected algorithm
 ISort sortSelected =    lstr_SortingStrategies[Convert.ToInt32(iSelectedAlgorithm)];

 // Create the random values
 sortSelected.InitalizeArray();

 // Write the random array to the console
 Console.WriteLine("\r\nRandom Array:");
 WriteArrayToConsole<int>(sortSelected.intArrRandom);

 // Sort the array
 sortSelected.SortArray();

 // Write the sorted array to the console
 Console.WriteLine("\r\nSorted Array:");
 WriteArrayToConsole<int>(sortSelected.intArrRandom);

 }
}
// While the user hasn't entered exit
while (!String.Equals(strUserInput, "exit", StringComparison.OrdinalIgnoreCase));

Now let’s put it all together.

static void Main(string[] args)
{
 string strDirections = "\r\nType 'exit' at any time to close the  program.\r\n";
 string strUserInput = "";
 int iSelectedAlgorithm;
 bool bValidNumber;
 
// Will hold the algorithm the user chooses to use
ISort sortSelected;

InsertionSort insertSort = new InsertionSort();
MergeSort mergeSort = new MergeSort();

List<ISort> lstr_SortingStrategies = new List<ISort>();

// Add the algorithms to the list
lstr_SortingStrategies.Add(insertSort);
lstr_SortingStrategies.Add(mergeSort);

// Create the directions for them
 foreach(ISort algorithm in lstr_SortingStrategies)
{
 strDirections += string.Format("Press {0} for {1}.\r\n"
 , lstr_SortingStrategies.IndexOf(algorithm)
 , algorithm.Name);
}

// Do the following at least once
do
{
 // Wait for user to hit a key to continue
 Console.WriteLine(strDirections);

 strUserInput = Console.ReadLine();

 bValidNumber = Int32.TryParse(strUserInput, out iSelectedAlgorithm);

 // If it's a valid number, is greater than or equal to zero, and less than the total number of strategies
 if (bValidNumber &&
 iSelectedAlgorithm >= 0 &&
 iSelectedAlgorithm < lstr_SortingStrategies.Count)

{
 // Get the selected algorithm
 sortSelected = lstr_SortingStrategies[Convert.ToInt32(iSelectedAlgorithm)];

 // Create the random values
 sortSelected.InitalizeArray();

 // Write the random array to the console
 Console.WriteLine("\r\nRandom Array:");
 WriteArrayToConsole<int>(sortSelected.intArrRandom);

 // Sort the array
 sortSelected.SortArray();

 // Write the sorted array to the console
 Console.WriteLine("\r\nSorted Array:");
 WriteArrayToConsole<int>(sortSelected.intArrRandom);

 }
}
// While the user hasn't entered exit
while (!String.Equals(strUserInput, "exit", StringComparison.OrdinalIgnoreCase));
}

/// <summary>
/// Write a generic object array to the console, this lets us handle
/// generic string/int/etc... array objects
/// This works because all basic arrays that have a lower bound of zero 
/// leverage the IList<T> interface.
/// </summary>
/// <param name="genericArray"></param>
public static void WriteArrayToConsole<T> (IList<T> genericArray)
{
 // for each object in the generic array
 for (int index = 0; index < genericArray.Count; index++)
 {

 // If it's not the last item, or the only item, in the array then add a comma
 if (index < genericArray.Count - 1 && 
 genericArray.Count > 1)

 Console.Write(string.Format("{0},", genericArray[index]));

 // Otherwise it's either alone or at the end, so it needs no trailing comma
 else

 Console.Write(genericArray[index]);

 }
}

So What?

So what’s all that mean in the grand scheme of things?

Now we can just create a new algorithm in a class derived from ISort. Then all we have to do is add the new algorithm to the list and we’re done.

The entire point of this was to make it super easy to extend our application.

This comes back to the principles of the SOLID paradigm, in particular the O part.

The O is the Open-Closed principle. Which boils down to being open for extensibility, but closed for modification.

In our case this means we can extend the derived classes (like we did with MergeSort) but we can’t modify the interface ISort.

We don’t want to modify the interface ISort because this is what the client is coupled to. In our case the client is just our Main function, but even that simple example has given us value. It’s letting us worry about the details of each algorithm in their own classes, while not having to change a thing in the calling function.

By minimizing the amount of coupling the calling function has to worry about (in other words there are as few points of interaction as possible), we’re effectively only revealing a ‘useful fiction’. This lets the calling function program to the interface, not the implementation.

Think about it

Why might putting all the logic of the Insertion Sort algorithm in the SortArray method not be a great idea?

Note: This example can be found on github.

Leave a Reply