Today, I am writing about a design problem related to C# generics that I’ve seen arise a few times. The problem occurs when we need to manipulate a generic class given a reference to its non-generic base class. For example, if a generic class Node<T> inherits from a non-generic class Node, and we are holding a Node reference to a Node<T> object, we cannot just cast the object to Node<T> because we do not have access to T.

I realize that the description is a bit abstract; let’s look at an example right away! It may look like a bit of code, but the classes are very simple and do just what you’d expect:

// Abstract node in a linked list
public abstract class Node {
	private Node m_next;
	public Node Next { get { return m_next; } }
	public Node(Node next) { m_next = next; }
}    

// Node in a linked list. Different nodes in the same list may carry data
// of different types.
public class Node<T> : Node {
	private T m_data;
	public T Data { get { return m_data; 	} }
	public Node<T>(T data, Node next) : base(next) {
		m_data = data;
	}
}    

// Abstract pair.
public abstract class Pair { }    

// Pair containing two values, possibly of different types.
public class Pair<TFirst, TSecond> : Pair {
	private TFirst m_first;
	private TSecond m_second;
	public Pair(TFirst first, TSecond second) {
		m_first = first;
		m_second = second;
	}
}

Here, Node is a node in a linked list where each node may contain a different type of data. Pair is just a pair of two values.

Now, suppose that we want to implement this method:

// Returns a pair containing the first two values from a linked list
public static Pair FirstTwoValues(Node node) {
	if (node == null) throw new ArgumentException();
	if (node.Next == null) throw new ArgumentException();    

	// Compilation error:
	return new Pair<U,V>((Node<U>)node, (Node<V>)node.Next);
}

Unfortunately, what I wrote on the last line is not valid C# because we cannot introduce a type variable in a cast. It is clear what we need to do: we have two Node objects which we assume to be instances of Node<U> and Node<V> respectively, and we would like to invoke some generic method – in this case a Pair<U,V> constructor – using both U and V as generic type parameters for the method. So how can we implement this?

Solution 1
The easiest solution is to use big nested if statements:

public static Pair FirstTwoValues(Node node) {
	// [...]
	if (node is Node<int>) {
		if (node.Next is Node<int>) return new Pair<int,int>(
			(Node<int>)node, (Node<int>)node.Next);
		}
		else if (node.Next is Node<string>) ...
		...
	}
	else if (node is Node<string>) ...
}

Obviously, this solution only works when the set of possible node data is constrained and very small, and even then the code is quite ugly.

Solution 2

Another possible solution is to use reflection. Reflection is very powerful, but it should be considered a last-resort technique because of its huge negative impact on the performance and general ugliness.

Solution 3

There is a third solution, that is in many cases preferable over the two I already mentioned. One way to “get access” to the type parameter T of the Node<T> is through a virtual method call. Node implements an abstract method, which Node<T> overrides. Calling the method on a Node reference results in that method executing in the context of Node<T> and we finally get access to that elusive type parameter T!

But, what if we need to get access to multiple generic type parameters coming from multiple objects, just like when trying to call a Pair<U,V> constructor given Node<U> and Node<V>? We can have multiple chained virtual methods, where each one fixes one of the generic parameters:

public abstract class Node {
	private Node m_next;
	public Node Next { get { return m_next; } }
	public Node(Node next) { m_next = next; }
	public abstract Pair ConstructPair(Node other);
	public abstract Pair ConstructPair<TFirst>(Node<TFirst> other);
}    

public class Node<T> : Node {
	private T m_data;
	public T Data { get { return m_data; } }
	public Node<T>(T data, Node next) : base(next) {
		m_data = data;
	}    

	public override Pair ConstructPair(Node secondNode) {
		return other.ConstructPair<T>(this);
	}    

	public override Pair ConstructPair<TFirst>(Node<TFirst> firstNode) {
		return new Pair<TFirst,T>(firstNode, this);
	}
}

Unfortunately, in order for this solution to be applicable, we need to have control over all types that could possibly be specified as the generic parameter, and they also need to share a common base class or implement a common interface that we can modify. Another disadvantage is that the type parameter class (in our case, Node) needs to know how to perform a possibly unrelated action (in our case, to construct a Pair). This may or may not be ideal from the design perspective.

Despite the disadvantages, I personally found this little trick quite useful. The problems I applied it to were related to abstract syntax tree manipulations, but I would expect similar issues to arise in other problem domains like data structures, data binding, etc. If you run into a similar design problem with generics, let me know whether you were able to apply this trick or not.

Tags:

29 Comments to “Fun with C# generics: down-casting to a generic type”

  1. Sashirekha says:

    good one !! so the “this” returns the next node as in,

    #
    public override Pair ConstructPair(Node firstNode) {
    #
    return new Pair(firstNode, this);
    #
    }

  2. hamed ahmadi says:

    Hi

    That’s something
    but as you know class Node has to be aware of class Pair and
    this depedancy cannot be tolerated in oop.

  3. S Zelenkov says:

    Igor,
    change line
    return new Pair((Node)node, (Node)node.Next);
    to
    return new Pair(node as Node, node.Next as Node);
    and be happy.

  4. Arul says:

    Your solution seems great! Cool!
    I was trying to write a generic MethodResult class, that could return different datatypes, the only way out for this is to use abstract class approach!

  5. Arul: I’m happy to hear this post helped you solve your problem!

  6. orastem says:

    Hi,

    what about casting an object to a generic type? I’m using reflection to dynamically create a generic method. This method returns a List, but the Invoke() on MethodInfo returns an object. How to cast it back to my list?

    Thanks

  7. orastem:

    Declare a generic method, e.g. ManipulateList<T>(List list). At runtime, you will use reflection to determine the T of your List<T>, and then call ManipulateList<T>(myList). Does that make help?

  8. Chad says:

    Very nice. I am still trying to get a feel for generic classes, so excuse the ignorance.

    Is one of the reasons for the abstract Node so that you can consume a generic list of nodes: List myModes;

    And it would be on the consumer to check the type of of the individual concrete nodes in the list?

  9. Chad:

    Yes, you could have a list of non-generic nodes. In the scenario I encountered, I actually had a tree of them.

  10. Chad says:

    Thanks. Follow-up: when operating on your tree of nodes, did you ever need to get to the Data? Seems like the only way to get at the Data would be your Solution #1.

    Context of my question: If your nodes were stored in a DB, and you wanted to expose them to a consumer, as some kind of generic collection, the collection would have to be typed to the abstract class, and the consumer would have to down-cast the nodes in order to get to the Data. I think similar to your solution #1.

    Do you have a solution for getting at the data more along the lines of your Solution #3?

  11. You can get on the data in solution #3… that’s actually the point. The trick is to add a virtual method DoSomething on the non-generic Node class, and then override it in the Node<T> generic class. In DoSomething in the derived generic class, you can access T (the data) in a type-safe way.

    My approach #3 requires that you are able to add a method to the Node class. If you can’t do that, use approach #2. See my explanation to orastem for some details on how to do that.

  12. Wigy says:

    I am just catching up with your blog, Igor. Congrats, you have great content.

    The problem you described here is quite interesting. Having a heterogeneous collection like your linked list and depending on the type of 2 elements is not trivial.

    Knowing you have a single algorithm (building pairs) and that you have only a single generic class that implements the Node interface, it is quite elegant to just ask the abstract Node class for some help. This way you could avoid implementing a 3-way dispatch by generalizing the visitor pattern.

  13. MASHA says:

    Hi there!
    Good idea. But …I still had compilation error untill changed this:
    return new Pair<TypedNode, TypedNode>(firstNode, this);
    Anyway, I solved my problem, so thanks! :-)

  14. MASHA says:

    Hmmmm…
    Why did browser skipped my post in thi strange way ?
    Ok, i just ment that when return new Pair i am to use type not TFirst, but (i’ve just called it not to have Classes with the same names, so i have not Node and Node but Node and TypedNode)
    TypedNode and TypedNode instead of just .
    Thats all)
    ps Fix this browser’s strange behavior!)

  15. MASHA says:

    Ok i see…but it wasnt tags ) last one

    i just ment that when return new Pair i am to use type not TFirst, but (i’ve just called it not to have Classes with the same names, so i have not Node and Node’T’ but Node and TypedNode’T’)
    TypedNode’TFirst’ and TypedNode’T’ instead of just ‘T’.

    ps why skipping text in angular brackets…

  16. Andrew Borodin says:

    Small typo
    public override Pair ConstructPair(Node secondNode) {
    return other.ConstructPair(this);
    }

  17. Andrew Borodin says:

    Usefulll casting, btw. Thx (:

  18. Ihar Bury says:

    Actually you probably don’t need FirstTwoValues method to return Pair. Non-generic Pair (or even Pair) should be enough in most cases.

  19. Dave says:

    Why not do an intermediate cast to object?

    return new Pair<U,V>((Node<U>)(object)node, (Node<V>)(object)node.Next);

  20. Dave: Casting to object will not resolve the problem. The issue is that the U and V type variables do not exist in the current context. You only have the node objects, whose static type is the non-generic Node base class.

    To get into a context where U and V type variables are available, you need to use one of the techniques described in the article (i.e., big switch statement, reflection, or virtual method call).

  21. enrique says:

    thank you for your great article………
    i got what search ….
    thank you very much….but keep on updating

  22. Olawn says:

    hello admin!
    Your article is very useful for who is learning c#.
    have a Good time..

  23. Andrey Tamelo says:

    That’s an interesting approach! Thanks for sharing, Igor.

    But there is a fourth option ;)

    Recently I was solving just about the same problem. Here is what I came up with:

    public static Pair FirstTwoValues(Node node)
    {
    if( node == null ) throw new ArgumentException();
    if( node.Next == null ) throw new ArgumentException();

    dynamic first = node;
    dynamic next = node.Next;

    return MakePair(first, next);
    }

    private static Pair MakePair(Node first, Node next)
    {
    return new Pair<Node, Node>(first, next);
    }

    That trick relies on DLR being able to figure out (under the hood) the exact runtime types of the nodes.

    This is somewhat similar to the reflection-based approach and should have the same performance penalties.. But looks much nicer from the C# code perspective and devoid of the downsides of the 3rd option you outlined.

    Hope that will also be useful to the readers of your blog.

    Andrey

  24. Andrey Tamelo says:

    A fix to my previous post (the content between the angle brackets < > has been skipped):

    public static Pair FirstTwoValues(Node node)
    {
    if( node == null ) throw new ArgumentException();
    if( node.Next == null ) throw new ArgumentException();

    dynamic first = node;
    dynamic next = node.Next;

    return MakePairImpl(first, next);
    }

    private static Pair MakePairImpl<TFirst, TNext>(Node<TFirst> first, Node<TNext> next)
    {
    return new Pair<Node<TFirst>, Node<TNext>>(first, next);
    }

  25. Andrey: Great point! Yes, the solution via dynamic typing is a lot like reflection, but a lot cleaner. Also, dynamic typing should have better performance in typical cases than reflection.

    Back when I wrote the article, dynamic typing wasn’t yet available in C#.

  26. vishaka opatha says:

    hi,
    could you please explain me the simple way of casting a generic object to another different object.
    Thanks in advance.

  27. Neel says:

    Hello Igor,

    This article gave me an idea about how I can create something like boost::any in C#. See http://stackoverflow.com/quest.....o-boostany. Only thing I am not able to figure out is how to have a method in the class T Get() but which I can access from Any and it will return correct data based on dynamic type of AnyInternal this Any object holds! Any ideas?

  28. Sami CHNITER says:

    Thank you for this great article

  29. […] -> A Heterogeneous Collection Issue , Issue with heterogeneous Tree (the best option to handle this scenario to build a heterogeneous […]

Leave a Reply

You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>