[Generic Arrays]

Arrays and Generic Types

Sunday, August 22, 2004

With the introduction of generic types in .NET 2005, can we try and give up on arrays just yet? One might have preferred using an array over, say, a System.Collections.ArrayList because of type safety. But let's list all of the qualities of arrays that distinguish them from other containers:

There are some other features, such as the fact that arrays are of a fixed size, that element write access is always possible, etc. But these details are easily implemented in any container class if one so wishes.

What's the advantage of using collection classes instead of array? For one, a collection may have a variety of other features, such as disallowing null references, imposing a given ordering, publishing events, and anything else one would like to have in a container. Secondly, while .NET tries hard to make the differences between arrays and collections transparent (with features like interfaces, foreach and indexers), there's still a gap in usage patterns (like Length vs. Count, etc.).

So let's address these qualities listed above one by one, and see if we can use a generic type for the same purposes.

Type Safety

This one is a no brainer. Type safety is a major reason we have generic types. Type parameters may even be array types, allowing for nesting. Moreover, if the element type is a value type, the values may be stored as efficiently as in an array, because the CLR instantiates an implemetation for every value type, avoiding boxing.

Multiple Dimensions

Here it gets interesting. The number of dimensions is supposed to be part of the type. But how can one write a generic type, when the number of parameters to the indexer (as well as to the constructor) is not known until instantiation?

public class Array<ItemType> {

    public Array(params int[] lengths){
    }

    public ItemType this[params int[] indices]{
        get{}
        set{}
    }

}

The parameter array, while legal, obviously defeats the purpose. While the length(s) of an array are not part of its type (and thus indices are not checked at compile time), the number of dimensions is, and therefore it should be a compile error if the number of parameters passed to the constructor is different from the number of parameters passed to the indexer (of course, with the implementation above, that isn't even feasable to prove for the compiler).

The solution: a special type as indexer input

So, what are we to do? It took me a while to find the solution, but the idea is this: if we want to have type checking, we need to use specific types as constructor/indexer parameters. Types, parameters - generics are parameterized types, so our array template should require that the user provide a type that describes the lengths/indices. Such a type should declare an appropriate constructor, ensuring the right number of indices is passed in. The generic type should be able to interpret these indices in a general way. Thus, the descriptor type must have a given base class; the generic type should declare an appropriate constraint.

So here's a compilable demonstration of a generic array type:

using System;
using System.Text;

namespace GenericArray {

// helper classes

public abstract class IndexDescriptorBase {

    private int[] m_Values;

    protected IndexDescriptorBase(params int[] values){
        m_Values = values;
    }

    public int DimensionCount{
        get{
            return m_Values.Length;
        }
    }

    public int GetValue(int dim){
        return m_Values[dim];
    }
    internal int GetTotalLength(){
        int total = 1;
        for(int i = 0; i < this.DimensionCount; i++){
            total *= this.GetValue(i);
        }
        return total;
    }
    internal int GetTotalIndex(IndexDescriptorBase lengthDescriptor){
        if(lengthDescriptor == null){
            throw new ArgumentNullException("No length descriptor given.");
        }
        int[] lengths = lengthDescriptor.m_Values;
        int[] indices = this.m_Values;
        if(lengths.Length != indices.Length){
            throw new ArgumentException("Wrong number of dimensions.");
        }
        int offset = 0;
        int factor = 1;
        for(int i = lengths.Length - 1; i >= 0; i--){
            if(indices[i] < 0 || indices[i] >= lengths[i]){
                throw new IndexOutOfRangeException();
            }
            offset += indices[i] * factor;
            factor *= lengths[i];
        }
        return offset;
    }
    public override string ToString(){
        StringBuilder sb = new StringBuilder(m_Values.Length * 10);
        for(int i = 0; i < m_Values.Length; i++){
            if(i > 0){
                sb.Append(", ");
            }
            sb.Append(m_Values[i]);
        }
        return "Index descriptor {" + sb.ToString() + "}";
    }
    public override bool Equals(object obj){
        if(obj.GetType().Equals(typeof(IndexDescriptorBase))){
            IndexDescriptorBase that = (IndexDescriptorBase) obj;
            if(this.m_Values.Length == that.m_Values.Length){
                for(int i = 0; i < this.m_Values.Length; i++){
                    if(this.m_Values[i] != that.m_Values[i]){
                        return false;
                    }
                }
            }
            return true;
        }
        return false;
    }
    public override int GetHashCode(){
        int iRet = 0;
        for(int i = 0; i < m_Values.Length; i++){
            iRet ^= m_Values[i];
        }
        return iRet;
    }

} // class IndexDescriptorBase

public class SingleDimension : IndexDescriptorBase {

    public SingleDimension(int value) : base(value) {
    }

} // class SingleDimension

public class DoubleDimension : IndexDescriptorBase {

    public DoubleDimension(int value1, int value2) : base(value1, value2) {
    }

} // class DoubleDimension

// generic type

public class Array<ItemType, IndexDescriptorType>
             where IndexDescriptorType : IndexDescriptorBase {

    private ItemType[] m_Elements;
    private IndexDescriptorBase m_LengthDescriptor;

    public Array(IndexDescriptorType lengthDescriptor){
        m_Elements = new ItemType[lengthDescriptor.GetTotalLength()];
        m_LengthDescriptor = lengthDescriptor;
    }

    public ItemType this[IndexDescriptorType desc]{
        get{
            return m_Elements[desc.GetTotalIndex(m_LengthDescriptor)];
        }
        set{
            m_Elements[desc.GetTotalIndex(m_LengthDescriptor)] = value;
        }
    }

} // class Array<ItemType, IndexDescriptorType>

// user code

public class Test {

    public static void Main(string[] args){

        Array<int, DoubleDimension> ai = new Array<int, DoubleDimension>
                                              (new DoubleDimension(3, 5));

        ai[new DoubleDimension(0, 0)] = 42;
        W(ai[new DoubleDimension(0, 0)]);
        
        ai[new SingleDimension(0)] = 13; // error
    }
    
    private static void W(object obj){
        Console.WriteLine(obj);
    }

} // class Test

} // namespace GenericArray

Various index descriptor types

A bonus: with the index descriptor classes, indices need not be integers. One can also use descriptive strings, or mix 'n match:

arr[new DateIndexDescriptor("February", 23)] = true;

Of couse, the DateIndexDescriptor class would have to map the month strings to indices in the highest rank, because the IndexDescriptorBase class only knows how to handle ints. Note that for this to work, we'd need another, parameterless, constructor in IndexDescriptorBase, as well as access to the indices array, so we'd have a change to do the mapping.

We could also use an index descriptor that works with System.DateTime in the first place:

arr[new DateIndexDescriptor(DateTime.Now)] = true;

Specialization by inheritance

Another option is to specialize the generic type by the number of dimensions:

public class SingleDimensionArray<ItemType> : Array<ItemType, SingleDimension> {

    public SingleDimensionArray(int length) : base(new SingleDimension(length)) {
    }

    public ItemType this[int index]{
        get{
            return this[new SingleDimension(index)];
        }
        set{
            this[new SingleDimension(index)] = value;
        }
    }

} // class SingleDimensionArray<ItemType>

Covariance

Hardly surprising, a generic type instantiation is not assignment compatible to another one merely because the type parameters are compatible:

public class Holder<T> {

    public T Value;

} // class Holder<T>

public class Test {

    public static void Main(string[] args){

        Holder<object> oh = new Holder<string>(); // error

    }

} // class Test

If a class inherits from a generic type instantiation, it cannot change the type parameter either. But it could introduce another type parameter, and use the trick of faking return type covariance through member hiding. But even with fake covariance, it's a bit like the situation before .NET 2005, when we used to specialize collections by their element type. This would hardly be less work than deriving a class from, say, System.Collections.CollectionBase, and writing and Add method and an Item property.

So this is where arrays still have an edge over generic collections.

Nevertheless, I'll keep an eye one this enum in System.Reflection, and the property that returns it:

[Flags]
public enum GenericParameterAttributes{
    NoSpecialConstraint = 0,
    NonVariant = 0,
    Covariant = 1,
    Contravariant = 2,
    VarianceMask = 3
    ReferenceTypeConstraint = 4,
    ValueTypeConstraint = 8,
    DefaultConstructorConstraint = 16,
    SpecialConstraintMask = 28,
}