Introduction
When version 2.0 of .NET was released, there was a lot of fuss about the fact that it had Generics included with it, along with some other stuff, and to be honest, this was mostly greeted with a shrug and a so what on my part. Largely, this is due to being a professional Windows programmer in the nineties when MFC was all the rage and people mostly forgot everything they ever knew about templates because they weren't supported by the Microsoft compilers.
Then .NET came out and I started doing a lot of C# programming, and it didn't have templates in it either, and to be honest, I never really missed them in either C# or in the MFC days as most of the business logic I was required to write didn't really need them anyway. Sure if they had been available I might have used them in some projects, if only so I could put them on my C.V. and make out I was the true expert in everything under the sun that seem to be the requirement to get a job these days.
These days however, some ideas for future projects could benefit from a template or a generic implementation. Not that these projects couldn't be done using the C# object model; the implementations would, coming from a templates background, be more logically cleaner if developed generically. So I figured that I'd better poke these Generics just to see what they can do and if in the implementation they match up to what I wanted out of them. Also, I wanted to see how they compare in a head to head with the object model, so as some future projects are going to be relying on a data structure that is similar to the tree data structure, I thought the ideal starting place would be to implement a simple tree using the object model and then convert it to the generic model to see what the gains if any where.
Tree Basics
A tree is a data structure that stores the data in nodes that branch out depending on the value contained within the data held in the node.
So if we assume that each of the blue circles is a node and the numbers in them represent the data, we can see that the node that we are starting with contains the lower value 5 and the node to the left of our starting node contains the value 4, while the node to the right contains the higher value 6, and this is how trees work. The node on the left of the node we are currently at will contain a smaller value than the current node, and the node on the right will contain a higher value. Of course, if you want to get more involved with tree data structures, you can start getting into balancing and organising the tree so that the left and right sides from the root nodes are equal, which makes searching quicker, but for our purposes, left lower, right higher will do.
The implementation we are going to be using is a C# translation of the BasicTree
code in Namir Clement Shammas' book Advanced C++ Progrogramming, published in 1992. This, as the name suggests, is about the most basic implementation of a tree you can get, and there are much more complex trees available on this site, both using the object and the Generics models of implementation.
The Object Model Implementation
To start with, we define the data that we are going to use:
public class SimpleTreeData : IComparer
{
private string strData;
public string Data
{
public SimpleTreeData( string data )
{
Data = data;
}
public int Compare( object simpleTreeDataOne, object simpleTreeDataTwo )
{
if( ( SimpleTreeData )simpleTreeDataOne <
( SimpleTreeData )simpleTreeDataTwo )
return -1;
if( ( SimpleTreeData )simpleTreeDataOne >
( SimpleTreeData )simpleTreeDataTwo )
return 1;
return 0;
}
public static bool operator ==( SimpleTreeData simpleTreeDataOne,
SimpleTreeData simpleTreeDataTwo )
{
public static bool operator !=( SimpleTreeData simpleTreeDataOne,
SimpleTreeData simpleTreeDataTwo )
{
public static bool operator >( SimpleTreeData simpleTreeDataOne,
SimpleTreeData simpleTreeDataTwo )
{
public static bool operator >=( SimpleTreeData simpleTreeDataOne,
SimpleTreeData simpleTreeDataTwo )
{
public static bool operator <( SimpleTreeData simpleTreeDataOne,
SimpleTreeData simpleTreeDataTwo )
{
public static bool operator <=( SimpleTreeData simpleTreeDataOne,
SimpleTreeData simpleTreeDataTwo )
{
public override int GetHashCode()
{
public override bool Equals(object obj)
{
}
We start the SimpleTreeData
class by declaring it as implementing the IComparer
interface. This means that we have to implement the Compare
function which compares two objects returning 1 if the first object to be compared is greater than the second object, 0 if both objects are equal, and -1 if the second object is greater than the first. Although the only data in the class is a string and we could implement this a lot more easily by just using the string compare function in the SimpleTreeData
class Compare
function, both the object model and the generic versions are implemented as if they are a much more complex class and therefore have a full compliment of overloaded operators.
Nodes
The way a tree tracks and stores its data, so as I said before, if we consider each blue circle in the picture above as a node, then this is the declaration for the node class:
public class SimpleTreeNode
{
private SimpleTreeNode parentNode;
private SimpleTreeNode leftNode;
private SimpleTreeNode rightNode;
private object data;
If we look again at the picture above and imagine that we are looking from the first node that contains the number 5, then the data for the number five would be held in the private object data
, leftNode
would point to the node containing the value 4, and rightNode
would point to the node containing the value 6. For this node, the parentNode
would be null
, but for both the nodes containing the values 4 and 6, the parentNode
would point to the node containing the value 5.
The SimpleTree Class
The main characteristics of the SimpleTree
class are:
public class SimpleTree
{
private SimpleTreeNode stnRootNode;
private SimpleTreeNode stnCurrentNode;
private int nNumberOfNodes;
...
public SimpleTree()
{
public SimpleTree( SimpleTreeNode rootNode ) : this()
{
public bool Insert( IComparer data )
{
public SimpleTreeNode SearchBinaryTree( IComparer data )
{
public SimpleTreeNode SearchBinaryTree( IComparer data, int occurance )
{
public bool Remove( IComparer data )
{
public bool Remove( IComparer data, int occurance )
{
public SimpleTreeNode GetSuccessor( SimpleTreeNode node )
{
public SimpleTreeNode GetPredecessor( SimpleTreeNode node )
{
public void ClearNode( SimpleTreeNode root )
{
public SimpleTreeNode GetLowestNode()
{
Here we have the SimpleTree
class stripped to all that is important. We have a root node that is the start of the tree, or the node that would hold the five in the picture above, and the current node which is used when moving around the tree, and a number of nodes counter. In terms of functionality, we have the compulsory Insert
and Remove
functions, along with searching for a specific node, and the GetSuccessor
and GetPredecessor
functions for moving through the tree, and finally, the GetLowestNode
function which is what you would do if you were going to use an enumerator to move through the list. Basically, it calls GetPredecessor
until it gets to the lowest node of the tree, and then you call GetSuccessor
to move through the nodes in the tree.
Comparisons
For our purposes, the IComparer
interface is important in that we will be using the IComparer<T>
interface when we get to the Generic implementation of the class. The IComparer
interface defines only one function and that is the Compare
function that we must implement. In the object model code, it looks like this:
public int Compare( object simpleTreeDataOne, object simpleTreeDataTwo )
{
if( ( SimpleTreeData )simpleTreeDataOne < ( SimpleTreeData )simpleTreeDataTwo )
return -1;
if( ( SimpleTreeData )simpleTreeDataOne > ( SimpleTreeData )simpleTreeDataTwo )
return 1;
return 0;
}
As you can see from the above code, the object model requires us to declare the items passed in as objects, even though as we know our class automatically inherits the Object
class. Trying to put a proper class declaration here will result in a compiler error. This is because the interface definition for the Compare
function explicitly declares that the parameters are to be object
s, which means that in the test code, you could quite easily pass in a SimpleGenericTreeData
class object to this function and there would be no compiler error as that also inherits from the class Object
. Of course, as soon as we try to compile the code, the compiler would notify us that the SimpleGenericTreeData
class could not be cast to a SimpleTreeData
class.
As stated above, this function returns 1 if the first item is greater than the second, and -1 if the second item is greater than the first. This is purely arbitrary on my part as the function definition requires that the value returned if the first item is greater should be greater than 0, and less than 0 if the second item is greater.
Inserting a Node
The Insert
function for the object model is:
public bool Insert( IComparer data )
{
SimpleTreeNode stnNewData = new SimpleTreeNode( data );
stnCurrentNode = stnRootNode;
SimpleTreeNode stnTempData = null;
NumberOfNodes++;
while( stnCurrentNode != null )
{
stnTempData = stnCurrentNode;
if( ( ( IComparer )stnNewData.Data ).Compare(
stnNewData.Data, stnTempData.Data ) <= 0 )
stnCurrentNode = stnCurrentNode.LeftNode;
else
stnCurrentNode = stnCurrentNode.RightNode;
}
stnNewData.ParentNode = stnTempData;
if( stnTempData == null )
{
stnRootNode = stnNewData;
}
else
{
if( ( ( IComparer )stnNewData.Data ).Compare(
stnNewData.Data, stnTempData.Data ) <= 0 )
stnTempData.LeftNode = stnNewData;
else
stnTempData.RightNode = stnNewData;
return true;
}
return false;
}
To insert a node into the tree, we call the Insert
function with a data object that inherits from IComparer
. We then insert this data into a new node and then try to find where to put it. We do this by working through the tree from the root node, and if the data is greater than or equal to the data stored in the current node, we move to the left. If it is greater than the data in the current node, then we move to the right. Note straight away that a class that inherits from the SimpleTreeData
class would have no problems here.
As we move through the tree, we maintain track of the current node with the stnTempData
node which, once we have found a place for the node, is set to the new parent node. If we have gone nowhere at all and the stnTempData
node is equal to null
, then we set the new node to be the root node.
If we already have nodes in the tree, then we decide if we need to place it to the left or to the right of the current node.
Removing a Node
The Remove
function for the object model is:
public bool Remove( IComparer data, int occurance )
{
stnCurrentNode = stnRootNode;
SimpleTreeNode stnTempNodeOne = null;
SimpleTreeNode stnTempNodeTwo = null;
if( occurance == 0 )
occurance = 1;
if( occurance > NumberOfNodes )
return false;
stnCurrentNode = SearchBinaryTree( data, occurance );
if( stnCurrentNode != null )
{
if( stnCurrentNode.LeftNode == null || stnCurrentNode.RightNode == null )
stnTempNodeOne = stnCurrentNode;
else
stnTempNodeOne = GetSuccessor( stnCurrentNode );
if( stnTempNodeOne.LeftNode != null )
stnTempNodeTwo = stnTempNodeOne.LeftNode;
else
stnTempNodeTwo = stnTempNodeOne.RightNode;
if( stnTempNodeTwo != null )
{
if( stnTempNodeTwo.ParentNode != null )
stnTempNodeTwo.ParentNode = stnTempNodeOne.ParentNode;
}
if( stnTempNodeOne.ParentNode == null )
{
stnRootNode = stnTempNodeTwo;
NumberOfNodes--;
}
else
{
if( stnTempNodeOne.ParentNode.LeftNode != null )
{
if( ( ( IComparer )stnTempNodeOne.Data ).Compare( stnTempNodeOne.Data,
stnTempNodeOne.ParentNode.LeftNode.Data ) == 0 )
stnTempNodeOne.ParentNode.LeftNode = stnTempNodeTwo;
else
stnTempNodeOne.ParentNode.RightNode = stnTempNodeTwo;
}
else
{
stnTempNodeOne.ParentNode.RightNode = stnTempNodeTwo;
}
NumberOfNodes--;
}
if( stnTempNodeOne != stnCurrentNode )
stnCurrentNode.Data = stnTempNodeOne.Data;
return true;
}
return false;
}
As with the Insert
function, we pass in a class object that inherits from the IComparer
interface and we pass in an integer to specify which occurrence of the data we are deleting. If 0 or no second parameter is included in the function call, then we set the value for the occurrence to one after setting up some temporary variables.
We find out where the data is in the tree by calling SearchBinaryTree
which is dealt with next. And then if we manage to find the data in question, we test to see if there are any nodes branching off the current node. If there aren't, we set the first temporary node to the next node in the tree with a call to GetSuccessor
.
Next, we set the value of the second temporary node to either the left or the right of the first temporary node.
Then if the second temporary node, which is the node after the node we wish to remove - the first temporary node, is valid and it has a valid parent, we shift the parent to be the parent of the first temporary node which is the node we are about to remove.
Finally, we test the parent node of the first temporary node, and if it is null
, then the node to be removed is the root node, so we simply replace the current root node with the second temporary node. If it is not equal to null
, we set the secondary temporary node to either the left or the right of the parent node of the node which we wish to remove, therefore replacing the node to be removed.
All we have to do then is copy the data and the function exits.
Searching for a Node
The search function really isn't all that complicated.
public SimpleTreeNode SearchBinaryTree( IComparer data, int occurance )
{
int nCount = 0;
stnCurrentNode = stnRootNode;
if( occurance == 0 )
occurance = 1;
if( occurance > NumberOfNodes )
return null;
while( stnCurrentNode != null && nCount < occurance )
{
if( ( ( IComparer )data ).Compare( data, stnCurrentNode.Data ) > 0 )
{
stnCurrentNode = stnCurrentNode.RightNode;
}
else if( ( ( IComparer )data ).Compare( data, stnCurrentNode.Data ) < 0 )
{
stnCurrentNode = stnCurrentNode.LeftNode;
}
else
{
nCount++;
if( nCount < occurance )
stnCurrentNode = stnCurrentNode.LeftNode;
}
}
if( stnCurrentNode != null )
return stnCurrentNode;
return null;
}
Once you get past the setup variables and the checking for the number of occurrences, then it is a simple while
loop that compares the data in the tree and moves to the left or the right of the current node depending on the result, until the matching node is found.
The GetSuccessor
and GetPredecessor
are straightforward, simply getting the getting the next higher or lower node from the current node without using any comparison of the data in the node.
The Generic Implementation
As with the object model, we declare our data:
public class SimpleGenericTreeData : IComparer< SimpleGenericTreeData >
{
private string strData;
public string Data
{
public SimpleGenericTreeData()
{
public SimpleGenericTreeData( string data )
{
public int Compare( SimpleGenericTreeData dataOne, SimpleGenericTreeData dataTwo )
{
if( dataOne < dataTwo )
return -1;
if( dataOne > dataTwo )
return 1;
return 0; }
public static bool operator ==( SimpleGenericTreeData simpleTreeDataOne,
SimpleGenericTreeData simpleTreeDataTwo )
{
public static bool operator !=( SimpleGenericTreeData simpleTreeDataOne,
SimpleGenericTreeData simpleTreeDataTwo )
{
public static bool operator >( SimpleGenericTreeData simpleTreeDataOne,
SimpleGenericTreeData simpleTreeDataTwo )
{
public static bool operator >=( SimpleGenericTreeData simpleTreeDataOne,
SimpleGenericTreeData simpleTreeDataTwo )
{
public static bool operator <( SimpleGenericTreeData simpleTreeDataOne,
SimpleGenericTreeData simpleTreeDataTwo )
{
public static bool operator <=( SimpleGenericTreeData simpleTreeDataOne,
SimpleGenericTreeData simpleTreeDataTwo )
{
public override int GetHashCode()
{
public override bool Equals(object obj)
{
}
As you can see, the generic tree data class inherits from the IComparer<T>
interface which is just the generic version of the IComparer
interface. The only difference being that in the declaration, the T
in brackets must be the type that is being compared, which to be honest is more often than not going to be the class type that is using the interface. This means that the compiler then enforces that a compare function of the type of the class given is used. So in the example file, we have:
public class SimpleGenericTreeData : IComparer< SimpleGenericTreeData >
and with this header, we must declare a Compare
function of the type:
public int Compare( SimpleGenericTreeData dataOne, SimpleGenericTreeData dataTwo )
which is quite straightforward and in keeping with the idea that a class that implements IComparer< T >
must implement the class given as T
. But the question is why have the T
there at all. Surely it would make sense to just have it the way the object model does? Well, the answer to that is that if you want to compare more than one class in the class that implements IComparar< T >
, you can. For example, declare a completely unrelated class. Note here that standard object rules apply so that in our example, any class that inherits from the SimpleGenericTreeData
class will automatically be cast to its base class. Then add the unrelated class to the class declaration. E.g.:
public class SimpleGenericTreeData : IComparer< SimpleGenericTreeData >,
IComparer< UnrelatedGenericTest >
Of course, this means that you must declare the Compare
function to handle the new data type:
public int Compare( UnrelatedGenericTest dataOne, UnrelatedGenericTest dataTwo )
With the data classes declared, their implementation is as you would expect, in that you create a new SimpleTreeData
object with:
new SimpleTreeData( "First Data String" )
and as the SimpleGenericTreeData
class is not specified with a template parameter, it is instantiated in exactly the same way.
new SimpleGenericTreeData( "First Data String" )
Nodes
The nodes class declaration is essentially the same as SimpleTreeNodes
, except for the type T
parameter:
public class SimpleGenericTreeNode< T > where T : IComparer< T >
{
private SimpleGenericTreeNode< T > parentNode;
private SimpleGenericTreeNode< T > leftNode;
private SimpleGenericTreeNode< T > rightNode;
private T data;
As you can see, the class is declared as SimpleGenericTreeNode< T >
where T
is the type parameter for the class, which works in exactly the same way as the type parameter for the IComparer< T >
class we just looked at. This means that when we declare an object of the SimpleGenericTreeNode
class, we must include the type parameter as well so whereas the object model declaration for a SimpleTreeNode
is:
SimpleTreeNode stnNewData = new SimpleTreeNode( data );
the SimpleGenericTreeNode
class is declared as:
SimpleGenericTreeNode< T > stnNewData = new SimpleGenericTreeNode< T >( data );
At first, this looks like you can just create a SimpleGenericTreeNode
with any type as we have not specified a type here, but there are two things to take into consideration. The first is that the SimpleGenericTreeNode
class is declared as:
public class SimpleGenericTreeNode< T > where T : IComparer< T >
The section after the declaration of the the class reads:
where T : IComparer< T >
This is called a constraint, and what it means to the compiler is that the type T
can only be a type that implements the IComparer< T >
interface. The second thing to consider is the positioning of the line:
SimpleGenericTreeNode< T > stnNewData = new SimpleGenericTreeNode< T >( data );
This line of code is taken from the Insert
function of the SimpleGenericTree
class, and it is here that we declare the type that the class uses.
The SimpleGenericTree Class
The class is declared as:
public class SimpleGenericTree< T > where T : IComparer< T >
{
SimpleGenericTreeNode< T > stnRootNode;
SimpleGenericTreeNode< T > stnCurrentNode;
private int nNumberOfNodes;
...
public SimpleGenericTree()
{
public SimpleGenericTree( SimpleGenericTreeNode< T > rootNode ) : this()
{
public bool Insert( T data )
{
public SimpleGenericTreeNode< T > SearchBinaryTree( T data, int occurance )
{
public bool Remove( T data, int occurance )
{
public SimpleGenericTreeNode< T > GetSuccessor( SimpleGenericTreeNode< T > node )
{
public SimpleGenericTreeNode< T > GetPredecessor( SimpleGenericTreeNode< T > node )
{
public void ClearNode( SimpleGenericTreeNode< T > root )
{
public SimpleGenericTreeNode< T > GetLowestNode()
{
The generic implementation of the tree is functionally identical to the object implementation of the SimpleTree
class. The main difference being that in the class declaration, the SimpleGenericTree
class has the constraint that type T
must implement the IComparer< T >
interface.
All the functions are declared to take an object of type T
; whether it is as a straight class object T
or as a SimpleGenericTreeNode< T >
, they are all the same type. This means that when we declare a SimpleTree
, we don't have to provide any information about the type of data that we are storing, so we can instantiate the tree as:
SimpleTree tree = new SimpleTree();
We can't do this with the SimpleGenericTree
class though as we have to specify the type and it has to be a type that implements the IComparer< T >
interface, so it is instantiated as:
SimpleGenericTree< SimpleGenericTreeData > tree =
new SimpleGenericTree<SimpleGenericTreeData >();
Declaring the tree as using the SimpleGenericTreeData
class means that for our program, any attempt to pass in a class that is not of or derived from the SimpleGenericTreeData
class will result in a compiler error.
Comparisons
The comparison function for the SimpleGenericData
class is:
public int Compare( SimpleGenericTreeData dataOne, SimpleGenericTreeData dataTwo )
{
if( dataOne < dataTwo )
return -1;
if( dataOne > dataTwo )
return 1;
return 0; }
The only difference between the object model implementation and the generic implementation is that the generic implementation declares the class types in the function declaration so we don't need to cast the passed in parameters from object
s to the required types.
Inserting a Node
As we have seen, the call to insert a node is identical for both classes; the object model is:
tree.Insert( new SimpleTreeData( "First Data String" ) );
and the generic version is:
tree.Insert( new SimpleGenericTreeData( "First Data String" ) );
The only real difference within the function is the casting when calling the Compare
function; with the object model reading:
if( ( ( IComparer )stnNewData.Data ).Compare( stnNewData.Data, stnTempData.Data ) <= 0 )
and the generic model reading:
if( stnNewData.Data.Compare( stnNewData.Data, stnCurrentNode.Data ) <= 0 )
Removing a Node and Searching for a Node
The differences in the code for removing/searching a node are identical to those for inserting a node, with the only difference being the casting in the calls to the Compare
function.
Conclusions
OK, for those expecting anything earth shattering, there isn't anything. Putting it simple, the strengths of using Generics come from the declarations and the strong type checking that forces you to think more closely about the types you are using right at the start of programming the class. Implementation wise, they offer nothing new apart from not having to cast object
s to class types.
So the answer to the question "What can I do with Generics that I can't do without them?" is not a lot really. You could, in the given example, define a single class that implements the Compare
functions for all your classes by implementing multiple IComparer< T >
, IComparer< L >
types, but we're stretching a bit and still not implementing anything that couldn't be done with the object model.
At the end of the day, if you choose to use the object model over the generic model, it is your choice, although Generics might look good on your CV and you can't escape the fact that Generics is just a cleaner and more organised way of doing things.
History
- 12 June 2007: First release.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.