Creating a generic list of composite generic subtypes in C#

Question

I have implemented the following hierachical data structure: Tree<T> → Branch<T> → T.

UPDATE: Lots of people asked: Why don't you use object instead of <T> (or <dynamic> or whatever)? So I modified my question to state my "constraints". Here we go...

Here are example Trees:

*
├─Negative
│ ├─-2
├─0
│ ├─0
├─Positive
│ ├─2
│ ├─12
│ ├─2147483647

*
├─Spring
│ ├─Mar
│ ├─Apr
│ ├─May
├─Summer
│ ├─Jun
│ ├─Jul
│ ├─Aug
├─Fall
│ ├─Sep
│ ├─Oct
│ ├─Nov
├─Winter
│ ├─Dec
│ ├─Jan
│ ├─Feb

The implementation in C#:

public class Tree<T>
{
    public readonly List<Branch<T>> Branches = new List<Branch<T>>();
}

public class Branch<T>
{
    public readonly List<T> Leaves = new List<T>();
    public string Name { get; set; }
}

public class StringLeaf
{
    public StringLeaf(string value) { Label = value; }
    public string Label { get; private set; }
    public override string ToString() { return Label; }
}

public class PositiveIntLeaf
{
    private readonly int _value;
    public PositiveIntLeaf(int value) { _value = value; }

    public string Value
    {
        get { return _value < 0 ? "-" : _value.ToString(); }
    }
    public override string ToString() { return Value; }
}

public class IntTree : Tree<IntLeaf>
{
    private readonly Branch<IntLeaf> _negatives = new Branch<IntLeaf> { Name = "Negative" };
    private readonly Branch<IntLeaf> _zeros = new Branch<IntLeaf> { Name = "0" };
    private readonly Branch<IntLeaf> _positives = new Branch<IntLeaf> { Name = "Positive" };

    public IntTree()
    {
        Branches.AddRange(new []{
            _negatives,
            _zeros,
            _positives
        });
    }

    public void Add(int value)
    {
        if (value < 0) _negatives.Leaves.Add(new IntLeaf(value));
        else if (value > 0) _positives.Leaves.Add(new IntLeaf(value));
        else _zeros.Leaves.Add(new IntLeaf(value));
    }
}

Assuming I have different trees, I'am incapable to put them into a list:

IntTreeintTree = new IntTree();
intTree.Add(-2); intTree.Add(2); intTree.Add(0); intTree.Add(12); intTree.Add(int.MaxValue);
Tree<StringLeaf> months = new Tree<StringLeaf>{ Branches =
{
    new Branch<StringLeaf> { Name = "Spring", Leaves = { new StringLeaf( "Mar"),new StringLeaf("Apr") ,new StringLeaf("May")} },
    new Branch<StringLeaf> { Name = "Summer", Leaves = {  new StringLeaf( "Jun"),new StringLeaf("Jul") ,new StringLeaf("Aug")} },
    new Branch<StringLeaf> { Name = "Fall", Leaves = { new StringLeaf( "Sep"),new StringLeaf("Oct") ,new StringLeaf("Nov")} },
    new Branch<StringLeaf> { Name = "Winter", Leaves = { new StringLeaf( "Dec"),new StringLeaf("Jan") ,new StringLeaf("Feb")} }
}};

var list = new [] { intTree, months };
var currentTree = list[0];
// Work with the current tree:
var count = currentTree.Branches.Count;
Display(currentTree);

The errors is: No best type found for implicitly-typed array

How can I get a list out of all this trees?

I'd like to underline that I just want to put them in a list, maybe iterate through it and access the current tree and all its branches (e.g. to display their names). I don't care whether T is an object or an abstract base class! Assume that I just call .ToString(). The concrete type is just important for sub types like the IntTree.

Answer 1

An alternative would be to use the dynamic type. Try the following:

static void Main(string[] args)
{
    Tree<dynamic> intTree = CreateTree<dynamic>
        (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15);
    Tree<dynamic> charTree = CreateTree<dynamic>
        ('1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'C', 'E');
    Tree<dynamic> months = CreateTree<dynamic>
        ("Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec");
    IEnumerable<Tree<object>> list = 
        new List<Tree<object>> { intTree, charTree, months };
}

private static Tree<T> CreateTree<T>(params T[] values)
{
    var t = new Tree<T>();
    var b = new Branch<T>();

    // some branching logic
    for (int i = 0; i < values.Length; i++)
    {
        if (i % 4 == 3)
        {
            b.Leaves.Add(values[i]);
            t.Branches.Add(b);
            b = new Branch<T>();
        }
        else

            b.Leaves.Add(values[i]);
    }
    if (b.Leaves.Count != 0)
        t.Branches.Add(b);

    return t;
}

You could also create an extension method for your purpose:

public static Tree<dynamic> MakeDynamic<T>(this Tree<T> inputTree)
{
    var newTree = new Tree<dynamic>();
    for (int i = 0; i < inputTree.Branches.Count; i++)
    {
        var newBranch=new Branch<dynamic>();
        newTree.Branches.Add(newBranch);
        for (int j = 0; j < inputTree.Branches[i].Leaves.Count; j++)
        {
            dynamic d = inputTree.Branches[i].Leaves[j];
            inputTree.Branches[i].Leaves[j] = d;
        }
    }
    return newTree;
}

In this latter case, you might preserve your original types and have this sample usage:

IEnumerable<Tree<object>> list = new List<Tree<object>> { 
    intTree.MakeDynamic(), 
    charTree.MakeDynamic(), 
    months.MakeDynamic() 
};

Answer 2

The one common collection will know only one type of element. Just like List<int> knows its element is int, List<T> knows its element is T.

So, if you know that all your Trees will be of the same type, but you don't know which, you have to abstract from that type:

class MyTreeHandler<T>
{
    public List<Tree<T>> myListOfTrees = new List<Tree<T>>();
}

and "here you go". Of course it will NOT work when trying to put heterogenous trees into that list, since T is one type of an item.

So, as collections like List know only one type of their item, before you can put heterogenous objects into one common list/collection, you have to find "common denominator" for all of them.

The simplest common denominator is an object, well, of course it is. So, the most dumb and always-working approach is:

List<object>

and you can put there any Trees of anything.

But, surely, you didn't want to hear it either. It's just to show you the common-denominator thing.

What common denominator your Trees have? As you presented - none. Of course, they are Trees<T> aka Tree``1 (one backtick should be, but I dont know how to write it here), but mind that except for a very few cases, you cannot use unparameterized type Tree<> in C#. And, you cannot use Tree<T> without defining the T to something. And after you define it, the Tree<T1> and Tree<T2> will be treated as two separate class hierarchies, unless T1==T2 or unless you use some in/out variance specifiers (like IEnumerable<out> does, hence IEnumerable<Kangaroo> is castable to a IEnumerable<object>). I assume you want a mixed-variance, so not an option. But if you want your tree to be input-only or output-only, use the co/contravariance specifiers at once!

So, let's leave generics and their variances. To provide a common-base understandable to C# language/compiler, you have to introduce something more .. basic.

Common abstract base other than object, some common interface. Whatever you deem least dirty.

When I really had to mix&store generics of different type, I usually introduced a simple dual interface:

public interface IMyThing //Typeless
{
    Type TypeParam {get;}

    object Operation(object a);
    object Property {get;set;}
}

public interface IMyThing<T> //TypeD
{
    T Operation(T a);
    T Property {get;set;}
}

public class MyThing<T> : IMyThing<T>, IMyThing
{
    public T Operation(T a) { .. }
    public T Property {get;set;}

    Type IMyThing.TypeParam {get{return typeof(T);}}
    object IMyThing.Operation(object a){return this.Operation((T)a);}
    object IMyThing.Property {get{return this.Property;}set{this.Property=(T)value;}}
}

Now I can cast every Thing to common IMyThing and store them as mixed, typeless List<IMyThing>. Thanks to explicit-interface-implementation, I will not see any "untyped" members unless I actually cast it, so other T-aware places will look as usual.

But, when I have to mix the types, I can now cast them to common typeless interface, and thanks to the interface I will still have access to the operations/properties. Assuming I will somehow guarantee that the args are castable to the correct T. But I can always check the TypeParam and handle it manually.

So, pure nuisance. As wrong as it feels, note that IEnumerable<T> and IEnumerable do exactly the same!

Cries for dynamic, but actually, without dynamic (i.e. have .Net 3.5 platform with no DLR?) there is little room for other solutions.

Answer 3

You can't really. This is a problem known as covariance and contravariance in generics. You can't stuff giraffes and tygers into a list of animals and hope that everything will be all right just because your collection is a list of animals.

So many articles written about this problem that I won't describe it to details. Just check out MSDN or google another articles.