Saturday, June 27, 2009

Template Method Pattern & IEnumerable

An Analysis Through C#'s Evolution

The template method is a very useful pattern commonly used within Data Access Layers. It's one of the simplest patterns within the gang of four, very similar to Command and Strategy and also belongs to the behavioral patterns. It makes good use of polymorphism in a simple class hierarchy.

Template Method's UML

Diagram copied from data & object factory.

A template method defines the skeleton of an algorithm delegating specific operations in it to subclasses. Whenever a process within an object is very similar between different siblings, then a Template Method is a candidate. I don't want to bore you with the details so I'll dig right into some code.

Consider the following abstract class for games:

protected abstract void InitializeGame();
protected abstract ArrayList GetPlayers();
protected abstract void MakeMove(Player player);
protected abstract bool GameEnded { get; }
protected abstract void DisplayResults();

public void Play()

    InitializeGame();
    while (!GameEnded)
    {
        foreach (Player player in GetPlayers())
        {
            MakeMove(player);
        }
    }
    DisplayResults();
}

And a simple Player class:

public class Player
{
    private readonly string name;

    public string Name
    {
        get { return this.name; }
    }

    public Player(string name)
    {
        this.name = name;
    }

    public override bool Equals(object obj)
    {
        Player player = obj as Player;
        return (player != null) && object.Equals(this.Name, player.Name);
    }

    public override int GetHashCode()
    {
        return this.Name == null ? 0 : this.Name.GetHashCode() * 53;
    }

}

The Play method is a Template Method, wherein InitializeGame, GetPlayers, MakeMove, GameEnded and DisplayResult are Primitive Operations.

Here's a basic implementation of a High Card game:

public class HighCard : GameBase
{

    private int rounds;
    private ArrayList players;
    private int currentRound;
    private Random random;
    private Card[] currentHand;

    public HighCard()
    {
        players = new ArrayList();
        random = new Random();
    }

    protected override void InitializeGame()
    {
        players.Clear();
        currentRound = 0;
        Hashtable names = new Hashtable();
        Console.WriteLine("-------------------------------------------------------------------------");
        Console.WriteLine(" Welcome to the Increbile High Card game. Please buckle your seat belts.");
        Console.WriteLine("-------------------------------------------------------------------------");
        Console.WriteLine();
        bool keepAsking = true;
        while (keepAsking)
        {
            if (players.Count < 2)
            {
                Console.Write("Enter player's name: ");
            }
            else
            {
                Console.Write("Enter player's name (leave blank for no more players): ");
            }
            string playerName = Console.ReadLine();
            if (playerName.Length > 0)
            {
                if (names.ContainsKey(playerName))
                {
                    Console.WriteLine("I'm sorry, but we already have a contestant named {0}.", playerName);
                }
                else
                {
                    Player player = new HighCardPlayer(playerName);
                    players.Add(player);
                    names.Add(playerName, null);
                }
            }
            else
            {
                if (players.Count >= 2)
                {
                    keepAsking = false;
                }
            }
        }
        currentHand = new Card[players.Count];
        Console.WriteLine();
        Console.Write("How many rounds would you like to play? ");
        while (!int.TryParse(Console.ReadLine(), out rounds))
        {
            Console.Write("I'm sorry, I don't understand what you mean by that. How many rounds? ");
        }
        Console.WriteLine();
    }

    protected override ArrayList GetPlayers()
    {
        return players;
    }

    protected override void MakeMove(Player player)
    {
        int playerIndex = players.IndexOf(player);

        Console.Write("{0} gets the... ", player.Name);
        Thread.Sleep(random.Next(500, 1000));

        Card card = GetNewCard();

        Console.WriteLine("{0} of {1}", card.Value, card.Suit);
        currentHand[playerIndex] = card;

        if (playerIndex == players.Count - 1)
        {
            EvaluateRound();
        }
    }

    protected override bool GameEnded
    {
        get 
        { 
            return rounds == currentRound; 
        }
    }

    protected override void DisplayResults()
    {
        Console.WriteLine("GAME OVER");
        Console.WriteLine();
        Console.WriteLine("Final Scores:");

        ArrayList winners = new ArrayList();
        int winnerScore = int.MinValue;
        for (int i = 0; i < players.Count; i++)
        {
            HighCardPlayer player = (HighCardPlayer)players[i];
            Console.WriteLine("* {0}: {1} points", player.Name, player.Score);
            if (player.Score > winnerScore)
            {
                winnerScore = player.Score;
                winners.Clear();
                winners.Add (player);
            }
            else if (player.Score == winnerScore)
            {
                winners.Add (player);
            }
        }
        Console.WriteLine();
        if (winners.Count != players.Count)
        {
            if (winners.Count == 1)
            {
                Console.Write("And the winner is: ");
            }
            else
            {
                Console.Write("And the winners are: ");
            }
            Console.ForegroundColor = ConsoleColor.White;
            Console.Write(((Player)winners[0]).Name.ToUpper());
            for (int i = 1; i < winners.Count; i++)
            {
                Console.Write(" - {0}", ((Player)winners[i]).Name.ToUpper());
            }
            Console.WriteLine();
            Console.ForegroundColor = ConsoleColor.Gray;
        }
        else
        {
            Console.WriteLine("There are NO winners! It's an all tie!");
        }
    }

    private Card GetNewCard()
    {
        Card card = null;
        do
        {
            card = new Card(random.Next(1, 14), random.Next(1, 5));
        } while (CardIsInHand(card));

        return card;
    }

    private bool CardIsInHand(Card card)
    {
        for (int i = 0; i < currentHand.Length; i++)
        {
            if (card.Equals(currentHand[i]))
            {
                return true;
            }
        }
        return false;
    }

    private void EvaluateRound()
    {
        currentRound++;
        HighCardPlayer player = GetRoundsWinner();
        Console.WriteLine();
        Console.WriteLine("Congratulations {0}! You won this round!", player.Name);
        Console.WriteLine();
        player.Score++;
        ClearHand();
    }

    private HighCardPlayer GetRoundsWinner()
    {
        int winnerIndex = 0;
        for (int i = 1; i < currentHand.Length; i++)
        {
            if (currentHand[i].CompareTo(currentHand[winnerIndex]) > 0)
            {
                winnerIndex = i;
            }
        }
        return (HighCardPlayer)players[winnerIndex];
    }

    private void ClearHand()
    {
        for (int i = 0; i < currentHand.Length; i++)
        {
            currentHand[i] = null;
        }
    }

}

public class Card: IComparable
{

    int valueIndex;
    int suitIndex;

    private static string[] suits = new String[] { "Clubs", "Diamonds", "Hearts", "Spades" };
    private string[] values = new string[] { "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A" };

    public Card(int value, int suit)
    {
        if ((value < 1) || (value > 13)) throw new ArgumentOutOfRangeException("value");
        if ((suit < 1) || (suit > 4)) throw new ArgumentOutOfRangeException("suit");

        this.suitIndex = suit - 1;
        if (value == 1)
        {
            this.valueIndex = 12;
        }
        else
        {
            this.valueIndex = value - 2;
        }
    }

    public string Value
    {
        get { return values[valueIndex]; }
    }

    public string Suit
    {
        get { return suits[suitIndex]; }
    }

    public override bool Equals(object obj)
    {
        Card card = obj as Card;
        return (card != null) && object.Equals(card.Value, this.Value) && object.Equals(card.Suit, this.Suit);
    }

    public override int GetHashCode()
    {
        int code = 13;
        code = (code * 23) + (this.Value != null ? this.Value.GetHashCode() : 0);
        code = (code * 23) + (this.Suit != null ? this.Suit.GetHashCode() : 0);

        return code;
    }

    public int CompareTo(object obj)
    {
        Card card = obj as Card;
        if (obj == null) throw new ArgumentNullException("obj");
        if (card == null) throw new ArgumentException("The object has to be a card.", "obj");

        if (this.valueIndex.Equals(card.valueIndex))
        {
            return this.suitIndex.CompareTo(card.suitIndex);
        }
        else
        {
            return this.valueIndex.CompareTo(card.valueIndex);
        }
    }
}

class HighCardPlayer: Player
{
    private int score;

    public int Score
    {
        get { return this.score; }
        set { this.score = value; }
    }

    public HighCardPlayer(string name): base(name)
    { }

}

A couple of things to notice:

  • To really get the benefits of the Template Method Pattern, the method itself would have to be complex, relying on simple Primitive Operations implemented on derived classes. This example does a very bad job illustrating this. A good example for this is the Insert method of a data access object that would rely on derived classes operations like GetTableName and GetFieldMappings.
  • This implementation is done to work with the first .NET Framework. This is on purpose. The reason for this lies right ahead.
  • This game's implementation is not a very good one. It has a few flaws, but I didn't want the code to be more complex than it needed to. A Deck class and refactoring Card would be recommended, plus as it is, there is a better chance of having repeated value cards in the same hand than it should. This is beyond the scope of this post, so I'll leave it at that. (Originally planned on implementing Rock, Paper & Scissors, but it seemed too cliché).

From here onwards, the focus will be on the GetPlayers primitive operation.

C# 1.0 - Where it all Started

The GetPlayers method returns an ArrayList. All we do with the returned list is enumerating through it so changing it to return an IEnumerable makes perfect sense. This adds an extra drop of flexibility to game implementers. They can use an array, an ArrayList, or even their own IEnumerable implementation. To be fair, this isn't an extremely compelling reason, and I admit that on my C# 1.0 days, I would use ArrayLists for pretty much everything. Not one of the smartest practices, I reckon, but did it anyways. Anyhow, this is the modified abstract method:

protected abstract IEnumerable GetPlayers();

This adds no extra complexity to our previous implementation, although it does break it. We need to change our return type. New game implementations will thank us.

C# 2.0 - If I Wanted to do all this Castings, I'd be in the Acting Industry

I will absolutely not engage in a discussion about all the benefits of strong typed collections introduced at this point. I'll just say the world is now a better place thanks to generics and its very welcome nasty breaking changes. Unless there were an awful lot of game implementations out there, and little more to come, changing the method to return IEnumerable<Player> is a must!

protected abstract IEnumerable<Player> GetPlayers();

Admittedly, this does add extra complexity to our HighCard class. I chose to make the players field a List<HighCardPlayer>. This does avoid a whole lot of extra casts that had to be done before along the entire class, but the GetPlayers method did become longer:

protected override IEnumerable<Player> GetPlayers()
{
    return players.ConvertAll<Player>(delegate(HighCardPlayer player)
    {
        return player;
    });
}

Still, let analyze what the advantages are:

For one, if our players list was of the Player type, no extra code would've been required. Also, as for now, on our implementations we can take advantage on the newly incorporated yield keyword. If you don't like anonymous methods, the GetPlayers method can also be written this way:

protected override IEnumerable<Player> GetPlayers()
{
    foreach (Player player in players)
    {
        yield return player;
    }
}

Yes, it is that simple. But it gets even better; consider that the game you are implementing has a constant amount of players. You could be creating a backgammon game with player1 and player2. This would look just like this:

protected override IEnumerable<Player> GetPlayers()
{
    yield return player1;
    yield return player2;
}

Although this is two lines of code, it is way more readable than what we would've done before:

protected override IEnumerable<Player> GetPlayers()
{
    return new Player[] { player1, player2 };
}

Even for a solitaire game, return a 1 item enumeration is simpler, and in the probably not applicable case of a no playered game:

protected override IEnumerable<Player> GetPlayers()
{
    yield break;
}

So the yield keyword will offer our implementers a whole new universe of possibilities.

C# 3.0 – Linqing the OOP World with the Functional World

As you've already guessed, now C# 3.0 came along, and even more flexibility is added to our GetPlayers method. Thanks to the functional programming fellows, extension methods, lambda expressions and linq is introduced. Now more complex games, with say eliminations between rounds are pretty simple to implement.

protected override IEnumerable<Player> GetPlayers()
{
    return players
        .Where(player => !player.IsEliminated)
        .OrderByDescending(player => player.Score)
        .Cast<Player>();
}

Or even in query language:

protected override IEnumerable<Player> GetPlayers()
{
    return from highCardplayer in players
           let player = (Player)highCardplayer
           where !highCardplayer.IsEliminated
           orderby highCardplayer.Score descending
           select player;
}

Even our version in HighCard gets slightly simplified due to extension methods:

protected override IEnumerable<Player> GetPlayers()
{
    return players.Cast<Player>();
}

The beauty in this is that we have introduced no breaking changes what so ever, in fact, our GameBase class hasn't even changed.

C# 4.0 – A Peek into the Future

With C# 4.0 we will be able to take advantage of the covariant aspect of IEnumerable<T>. Basically, an IEnumerable<HighCardPlayer> can be implicitly converted to IEnumerable<Player>. This takes us back to our method being as simple as it started out being:

protected override IEnumerable<Player> GetPlayers()
{
    return players;
}

Notice how players is List<HighCardPlayer> which in turn is an IEnumerable<HighCardPlayer>, and thanks to covariance, it is also an IEnumerable<Player>.

Our GameBaseclass didn't change and no breaking changes were introduced. Still, interesting enough, there is a chance that switching to C# 4.0 will introduce a breaking change. If we had something like this:

IEnumerable playerEnum = players;

if (playerEnum is IEnumerable<Player>)
{
    // Do something
}
else if (playerEnum is IEnumerable<HighCardPlayer>)
{
    // Do something else
}

Now, the second block will be unreachable since every IEnumerable<HighCardPlayer> is in fact also an IEnumerable<Player>.

The Reason behind this Post

I've been working on a code generation project. For example, the class generator makes full use of Template Methods that use operations like GetFields, GetMethods, GetProperties and even GetDecorators. These operations have changed during time taking advantage of everything noted above, and I found it very interesting. I thought I'd share.

Random thoughts: The template method pattern isn't really the reason of all the things that were shown here, the responsible is the IEnumerable<T> interface. I might as well have used an interface with IEnumerable<T> methods or properties, but took this opportunity to talk a little about this pattern. I usually find it extremely useful, and the simplicity of it makes it yet more desirable. Pretty much like everything else, the value is benefit/complexity. Having such low complexity makes it very valuable, and I love the KISS principle.

On a personal note, I wish my very good friend Gonzalo a very happy birthday. I hope you enjoy this post and good luck on your future endeavors!

2 comments:

  1. You forced me to post a comment :)
    Thanks for the note on my birthday!

    Great article as always!

    ReplyDelete
  2. Yeah! Great post my friend. Yield keyword is fantastic. Now we are working with IEnumerable at some projects, and I think this post would help us understanding how this works.
    JR.

    ReplyDelete