Thursday, October 18, 2007

Strategy Pattern in C# 2.0

Strategy pattern is very convenient when it comes to algorithms selection. The selection is possible because algorithm is encapsulated in single class, so it is easier to handle multiple algorithms.

There is a C# sample of Strategy pattern on the Wikipedia. Strategies there are passed as objects into the context. With the emergence of generics in the .NET 2.0 it is possible to specify strategy as a type parameter.

In this post I'll show sample list class "SmartList" that can be tuned with different allocation strategies. Such list can be used when developer needs full control on how memory is consumed by the list. For simplicity, there is no error handling and list class has limited functionality.

So, at first we define our algorithm's interface or contract.


interface IAllocationSrategy<T>
{
T[] Allocate(T[] data)
;
}


Then we define two allocation strategies: DoubleAllocator and FixedAllocator.
DoubleAllocator when doing allocation doubles the initial memory count, while FixedAllocator makes constant increment.


class DoubleAllocator<T> : IAllocationSrategy<T>
{
#region IAllocationSrategy Members

public T[] Allocate(T[] data)
{
int length = data.Length * 2;
T[] newData = new T[length];
Buffer.BlockCopy(data, 0, newData, 0, data.Length);
return
newData;
}

#endregion
}

class FixedAllocator<T> : IAllocationSrategy<T>
{
int fixedIncrement = 20;
#region
IAllocationSrategy Members

public T[] Allocate(T[] data)
{
int length = data.Length + fixedIncrement;
T[] newData = new T[length];
Buffer.BlockCopy(data, 0, newData, 0, data.Length);
return
newData;
}

#endregion
}

SmartList provides list functionality. Items can be added to the list and obtained by index.


class SmartList<A, T> where A : IAllocationSrategy<T>, new()
{
A allocator
= new A();

T[] innerList;
int
size = 0;

public
SmartList() : this(1)
{ }

public SmartList(int? capacity)
{
innerList
= new T[capacity ?? 1];
}

public void Add(T item)
{
if (size == innerList.Length)
innerList
= allocator.Allocate(innerList);
innerList[size++] = item;
}

public T this[int index]
{
get { return innerList[index]; }
}

public int Size
{
get { return size; }
}

public int Capacity
{
get { return innerList.Length; }
}
}



And finally, sample code that uses SmartList class with FixedAllocator and int type as item type.


class Sample
{
public Sample()
{
SmartList<FixedAllocator<
int>, int> smartList =
new
SmartList<FixedAllocator<int>, int>();

smartList.Add(1);
smartList.Add(2);
smartList.Add(3);

Console.WriteLine(smartList.Capacity);
}
}

2 comments:

  1. How does this relate to c# delegates and use of first class functions? In wikipedia article, python implementation is much simpler... can't same approach be taken with c#? I am a newbie trying to figure it out.

    ReplyDelete
  2. In C# similar thing can be done using delegates. However, delegate is not a class.

    In strategy pattern an algorithm has to be encapsulated into the class. Thus using delegates (delegate will just point to a method) can be infeasible if algorithm is complex enough.

    ReplyDelete