I work quite a bit with matrices. I work with them enough that at some point I decided to create my own generic classes for a matrix and a half matrix. Among other things, I wanted my classes to provide a method to calculate the sum of items in a row or column. I immediately had a problem. How does one calculate the sum of two generic objects?
To simplify things, let’s say that we’re working with a descendant of List<T> and we want to add a method called Sum().
We start by deriving a class from List<T>:
class SummableList : List{}
Let’s go ahead and add the Sum()method:
class SummableList : List {
public T Sum() {
T result = default(T);
foreach (T item in this)
result += item;
return result;
}
}
Unfortunately, that will not compile. It won’t compile because the compiler doesn’t know how to add two objects together. In .Net a type parameter (the T in List<T>) that is not constrained is assumed to be of type System.Object and there’s not much you can do with a plain old object.
There are ways to get around this, but they have their problems. My goal is to be able to write my generic classes with the syntax as close to the example above with as little trouble as possible.
Would a constraint help?
So far, we know that our code will not compile because the type parameter is assumed to be an object. What if we were to constrain the type parameter to some type that the compiler does know how to add? Then it is only a matter of picking an appropriate class. Well, rather than trying to find an appropriate class, let’s go ahead and make one ourselves:
/// <summary>
/// An abstract base class that defines all of the mathematical operations we might want to do.
/// </summary>
public abstract class MathClass {
public abstract MathClass Add(MathClass other);
public abstract MathClass Subtract(MathClass other);
public abstract MathClass Divide(MathClass other);
public abstract MathClass Divide(int other);
public static MathClass operator +(MathClass a, MathClass b) {
return a.Add(b);
}
public static MathClass operator -(MathClass a, MathClass b) {
return a.Subtract(b);
}
public static MathClass operator /(MathClass a, MathClass b) {
return a.Divide(b);
}
public static MathClass operator /(MathClass a, int b) {
return a.Divide(b);
}
}
Now all we need to do is derive any class on which we might want to do arithmetic from this new MathClass. Then we can write our SummableList<T> with a constraint on it as follows:
/// <summary>
/// Then we can write our SummableList by placing a constraint on the type parameter.
/// Now our summable list can only contain classes that derive from MathClass
/// </summary>
public class SummableListC<T> : List<T> where T : MathClass, new() {
public T Sum() {
T result = new T();
foreach (T thing in this) {
result = (T)(result + thing);
}
return result;
}
public T Average() {
return (T)(Sum() / Count);
}
}
But, the problem is that we can only work with classes derived from MathClass. We can’t use int or double. Not only that, but the derived classes we have to write aren’t that straightforward:
/// <summary>
/// Then we have to create a new class derived from MathClass for any type that we might
/// want to use in our list.
/// Here is the class that lets us use integers in our list.
/// </summary>
public class IntMathClass : MathClass {
private int fValue = 0;
public IntMathClass(int value) {
fValue = value;
}
public IntMathClass() {
fValue = 0;
}
public static implicit operator IntMathClass(int a) {
return new IntMathClass(a);
}
public static implicit operator int(IntMathClass a) {
return a.fValue;
}
public override MathClass Add(MathClass other) {
if (other is IntMathClass) {
return new IntMathClass(this.fValue + (IntMathClass)other);
}
return this;
}
public override MathClass Subtract(MathClass other) {
if (other is IntMathClass) {
return new IntMathClass(this.fValue - (IntMathClass)other);
}
return this;
}
public override MathClass Divide(MathClass other) {
if (other is IntMathClass) {
return new IntMathClass(this.fValue / (IntMathClass)other);
}
return this;
}
public override MathClass Divide(int other) {
return new IntMathClass(this.fValue / other);
}
}
That’s a lot of work just to be able to use integers in our list. However, it does allow is to do the following:
SummableList<IntMathClass> list = new SummableList<IntMathClass>();
list.Add(4);
list.Add(5);
list.Add(6);
list.Add(7);
//list.Sum() would return 22
//list.Average() would return 5
If you’re an applications programmer and all you need to do is work with this SummableList<T>, then this works pretty well. However, what if you are the one that has to write all the sub-classes of MathClass? There are better ways.
What about an interface constraint?
If we use an interface constraint then we can simply apply the interface to whatever class we need to use. Also, the interface definition is much simpler than the abstract class:
/// <summary>
/// Instead of an abstract base class
/// we define an interface that defines all of the mathematical operations we might want to do.
/// </summary>
public interface IArithmetic<T> {
T Add(T a);
T Subtract(T a);
T Divide(T a);
T Divide(int a);
}
That is much simpler, but we still have to implement this interface in any classes we want to work with. We also have to write replacements for the built in types like int and double because we can’t simply add the interface to those. Here’s the interface that lets us use integers in our SummableList<T>
/// <summary>
/// Them we have to implement that interface in any type that we might
/// want to use in our list.
/// If we want to use any base types, we have to make an entirely
/// new class that wraps the base type.
/// This is OK, but wrapping and unwrapping of base types can get messy.
/// Here is the class that lets us use integers in our list.
/// </summary>
public class IntMathI : IArithmetic<IntMathI> {
private int fValue = 0;
public IntMathI() {
}
public IntMathI(int value) {
fValue = value;
}
public static implicit operator IntMathI(int a) {
return new IntMathI(a);
}
public static implicit operator int(IntMathI a) {
return a.fValue;
}
#region IArithmetic Members
public IntMathI Add(IntMathI a) {
return new IntMathI(this.fValue + a.fValue);
}
public IntMathI Subtract(IntMathI a) {
return new IntMathI(this.fValue - a.fValue);
}
public IntMathI Divide(IntMathI a) {
return new IntMathI(this.fValue / a.fValue);
}
public IntMathI Divide(int a) {
return new IntMathI(this.fValue / a);
}
#endregion
}
Now we can write our SummableList<T> by placing an interface constraint on the type parameter:
/// <summary>
/// Then we can write our SummableList by placing a constraint on the type parameter.
/// Now our summable list can only contain classes that implement the IArithmetic interface
/// </summary>
public class SummableList<T> : List<T> where T : IArithmetic<T>, new() {
public T Sum() {
T result = new T();
foreach (T thing in this) {
result = result.Add(thing);
}
return result;
}
public T Average() {
return Sum().Divide(Count) ;
}
}
Notice, however, that in our generic class we now have to do arithmetic with methods like .Add() and .Divide() instead of using operators like + and /. This is because static methods cannot be defined in an interface and operator overloads are defined as static methods. Without those static methods we cannot use operators in our generic class and we have to use the methods instead.
This does work though and now we can write the following:
SummableList<IntMathI> list = new SummableList<IntMathI>();
list.Add(4);
list.Add(5);
list.Add(6);
list.Add(7);
//list.Sum() would return 22
//list.Average() would return 5
So, this works and it is much simpler than working with the abstract base classes, but it is still limiting. Again, if you are the applications programmer and you only have to work with the SummableList<T>, then this works very well. However, if you are writing your own generic classes, the inability to use operators is a deal breaker. Again, there is a better way.
Introducing Calculator Utility
After much though about this, I came up with a calculator utility that isn’t limited to base classes or interfaces and still allows the class programmer to work with familiar syntax and operators.
The utility has three parts:
- interface ICalculator<T> defines all of the operations that can be done.
- struct implementations of ICalculator<T> define how the operations are done for any particular type.
- class Number<T> stands in for any number in a generic class.
It uses reflection to automatically create the correct ICalculator<T> based on the type of T.
It has operation method implementation as defined in interface ICalculator<T> to be performed.
It defines operators to make arithmetic easy for the classes programmer.
ICalculator<T>
The ICalculator<T> interface defines all of the operations that can ever be done in a generic class that uses this utility.
/// <summary>
/// This interface defines all of the operations that can be done in generic classes
/// These operations can be assigned to operators in class Number<T>
/// </summary>
/// <typeparam name="T">Type that we will be doing arithmetic with</typeparam>
public interface ICalculator<T> {
T Sum(T a, T b);
T Difference(T a, T b);
int Compare(T a, T b);
T Multiply(T a, T b);
T Divide(T a, T b);
T Divide(T a, int b); //for doing integer division which is needed to do averages
}
While this is indeed an interface, the utility does not require that any classes implement it. The interface is used internal to the utility.
Struct implementations of ICalculator<T>
For each type on which might do arithmetic there must be an implementation of ICalculator<T>. The attached code includes implementations for int32, int64, single, double and string.
Here is what the implementation of int32 looks like:
/// <summary>
/// ICalculator<T> implementation for Int32 type
/// </summary>
struct Int32Calculator : ICalculator<Int32> {
public Int32 Sum(Int32 a, Int32 b) {
return a + b;
}
public Int32 Difference(Int32 a, Int32 b) {
return a - b;
}
public int Compare(Int32 a, Int32 b) {
return Difference(a, b);
}
public int Multiply(Int32 a, Int32 b) {
return a * b;
}
public int Divide(Int32 a, Int32 b) {
return a / b;
}
}
This is pretty straight forward code that simply defines how to do the operations for any given type. Any programmer that wanted to use types that are not already included in the utility could easily add a struct for any other type. In fact, the utility includes a struct implementation for string. I included it to show that any type could be added to without having to modify the type itself.
Class Number<T>
Class Number<T> is where all of the work is done. The programmer using this utility uses Number<T> to stand in for the numbers in his generic class. When the Number<T> is used, it uses reflection to create an instance of the correct ICalculator<T>. It is this instance of the ICalculator<T> that does the actual calculations.
There is an if chain to decide which ICalculator<T> to create, but Number<T> uses a static variable and a singleton pattern to ensure that the if chain is only entered once per type.
Here is the code for Number<T>:
/// <summary>
/// This class uses reflection to automatically create the correct
/// ICalculator<T> that is needed for any particular type T.
/// </summary>
/// <typeparam name="T">Type that we will be doing arithmetic with</typeparam>
public class Number<T> {
private T value;
public Number(T value) {
this.value = value;
}
/// <summary>
/// Big IF chain to decide exactly which ICalculator needs to be created
/// Since the ICalculator is cached, this if chain is executed only once per type
/// </summary>
/// <returns>The type of the calculator that needs to be created</returns>
public static Type GetCalculatorType() {
Type tType = typeof(T);
Type calculatorType = null;
if (tType == typeof(Int32)) {
calculatorType = typeof(Int32Calculator);
}
else if (tType == typeof(Int64)) {
calculatorType = typeof(Int64Calculator);
}
else if (tType == typeof(Double)) {
calculatorType = typeof(DoubleCalculator);
}
else if (tType == typeof(string)) {
calculatorType = typeof(StringCalculator);
}
else {
throw new InvalidCastException(String.Format("Unsupported Type- Type {0} does not have a partner implementation of interface ICalculator<T> and cannot be used in generic arithmetic using type Number<T>", tType.Name));
}
return calculatorType;
}
/// <summary>
/// a static field to store the calculator after it is created
/// this is the caching that is refered to above
/// </summary>
private static ICalculator<T> fCalculator = null;
/// <summary>
/// Singleton pattern- only one calculator created per type
///
/// </summary>
public static ICalculator<T> Calculator {
get {
if (fCalculator == null) {
MakeCalculator();
}
return fCalculator;
}
}
/// <summary>
/// Here the actual calculator is created using the system activator
/// </summary>
public static void MakeCalculator() {
Type calculatorType = GetCalculatorType();
fCalculator = Activator.CreateInstance(calculatorType) as ICalculator<T>;
}
/// These methods can be called by the applications programmer if no operator overload is defined
/// If an operator overload is defined these methods are not needed
#region operation methods
public static T Sum(T a, T b) {
return Calculator.Sum(a, b);
}
public static T Difference(T a, T b) {
return Calculator.Difference(a, b);
}
public static int Compare(T a, T b) {
return Calculator.Compare(a, b);
}
public static T Multiply(T a, T b) {
return Calculator.Multiply(a, b);
}
public static T Divide(T a, T b) {
return Calculator.Divide(a, b);
}
public static T Divide(T a, int b) {
return Calculator.Divide(a, b);
}
#endregion
/// These operator overloads make doing the arithmetic easy.
/// For custom operations, an operation method may be the only way to perform the operation
#region Operators
//IMPORTANT: The implicit operators allows an object of type Number<T> to be
//easily and seamlessly wrap an object of type T.
public static implicit operator Number<T>(T a) {
return new Number<T>(a);
}
//IMPORTANT: The implicit operators allows an object of type Number<T> to be
//easily and seamlessly wrap an object of type T.
public static implicit operator T(Number<T> a) {
return a.value;
}
public static Number<T> operator +(Number<T> a, Number<T> b) {
return Calculator.Sum(a.value, b.value);
}
public static Number<T> operator -(Number<T> a, Number<T> b) {
return Calculator.Difference(a, b);
}
public static bool operator >(Number<T> a, Number<T> b) {
return Calculator.Compare(a, b) > 0;
}
public static bool operator <(Number<T> a, Number<T> b) {
return Calculator.Compare(a, b) < 0;
}
public static Number<T> operator *(Number<T> a, Number<T> b) {
return Calculator.Multiply(a, b);
}
public static Number<T> operator /(Number<T> a, Number<T> b) {
return Calculator.Divide(a, b);
}
public static Number<T> operator /(Number<T> a, int b) {
return Calculator.Divide(a, b);
}
#endregion
}
Final SummableList<T>
With all three pieces in place SummableList<T> can now be written without using any constraints, abstract classes or interfaces.
class SummableList<T> : List<T> {
public T Sum() {
Number<T> result = default(T);
foreach (T item in this)
result += item;
return result;
}
public T Average() {
Number<T> sum = Sum();
return sum / Count;
}
}
This looks very much like the first example that we said wouldn’t compile. The difference is that the result variable in the Sum() method is of type Number<T> instead of just type T. Also, I’ve thrown in an Average() method for good measure.
You may notice that the Sum() method is supposed to return a T while the last line of code returns the variable result which is a Number<T>. This is possible because class Number<T> defined two implicit operators that tell the compiler how to implicitly convert a T into a Number<T>.
//IMPORTANT: The implicit operators allows an object of type Number<T> to be
//easily and seamlessly wrap an object of type T.
public static implicit operator Number<T>(T a) {
return new Number<T>(a);
}
public static implicit operator T(Number<T> a) {
return a.value;
}
It is this that allows the classes programmer to seamlessly use the Number<T> in place of a T. Also, because the Number<T> has arithmetic methods and operators defined for it, it allows the programmer to do arithmetic where he normally wouldn’t be able.
Adding Types or Operations
Since there are no base classes or interfaces that need to be used in order to use this utility, it is fairly self contained. However there may come a time when you want to use this utility with a type that is not included or you want to perform some arithmetic operation that isn’t already defined. Here’s how you can do it:
Adding Types
- Add type to Number<T>.GetCalculatorType(Type tType);
- Create an implementation of I Calculator<T>
Adding Operations
- Add operation to ICalculator<T> interface.
- Add operation to each implementation of ICalculator<T>.
- Add operation and operator overload to Class Number<T>.
Performance
The attached solution includes a SpeedTest that will add any number of random numbers together using each of the three methods described in this article and show the elapsed time. At ten million iterations the utility comes out about .2 or .3 seconds faster.
MiscUtil
There is another way to go about this that is completely different. This way requires .Net 3.5 and uses LINQ classes to generate expressions and compile them on the fly. It uses the operator overloads on any class to generate the required expressions. This means that it can work with any class that implements suitable operators.
Compiling code on the fly can be very slow, but Jon Skeet and Marc Gravell have put together a project called MiscUtil that among other things includes a framework that caches the compiled expressions to make it very fast. In my crude speed test at 1 million iterations it is not as fast as my utility, but having it work on any class that implements operators is very attractive. Also, using LINQ this way is very, very cool.
References
The following articles really helped me when I was trying to figure out what I was going to do about my matrices.
- Gunnerson, Eric. “Generics Algorithms” Eric Gunnerson’s C# Compendium.
November 13, 2003.
http://blogs.msdn.com/ericgu/archive/2003/11/14/52852.aspx - Klaehn, Rüdiger. “Using generics for calculations” The Code Project.
October 11, 2004.
http://www.codeproject.com/KB/cs/genericnumerics.aspx - Skeet, Jon and Gravell, Mark. “Generic operators” Jon Skeet’s C# and .NET articles and links.
Last accessed July 13, 2008.
http://www.yoda.arachsys.com/csharp/genericoperators.html