Constraints on Type parameter(Type set to IComparable but unable to send Type as argument to a method that takes IComparable)

Question

Here is my code

public class UnOrderedMaxPQ<Key> where Key : IComparable
 {
    private Key[] array;
    private int N;
    public UnOrderedMaxPQ(int size)
      {
        array = new Key[size];
       }
         .......
     public Key DelMax()
      {  
InsertionSort.Sort(array);//Error cannot convert from 'Key[]' to IComparable[]' 

   return array[--N];
   }
  }

And here is insertion sort code

 public class InsertionSort
 {
     public static void Sort(IComparable[] array)
    {
        for (int i = 0; i < array.Length-1; i++)
        {
            for (int j = i + 1; j <=0;j--)
            {
                if (Less(array[j], array[i]))
                {
                    Exchange(array, j, i);
                }
                else
                    break;
            }
        }
    }

So my question is when I have constrained the "Key" to be IComparable, why can't I pass it to Sort method which takes IComparable as parameter? What changes I have to make to make it work?

Answer 1

You are trying to take advantage of array covariance -- the idea that you can substitute an array of a derived type when an array of a base type is required. However, in c#, this only works for reference types. From the docs:

For any two reference-types A and B, if an implicit reference conversion (Section 6.1.4) or explicit reference conversion (Section 6.2.3) exists from A to B, then the same reference conversion also exists from the array type A[R] to the array type B[R], where R is any given rank-specifier (but the same for both array types). This relationship is known as array covariance. Array covariance in particular means that a value of an array type A[R] may actually be a reference to an instance of an array type B[R], provided an implicit reference conversion exists from B to A.

Thus if you constrain your Key type to a class -- a reference type -- your code will compile:

public class UnOrderedMaxPQ<Key> where Key : class, IComparable
{
}

Of course, this means you wouldn't be able to use a value type such as int as a Key, so you probably don't want to do this.

Alternatively, you could eliminate the need for array covariance by declaring your Sort method (and the methods Exchange and Less) to be generic also:

public class InsertionSort
{
    public static void Sort<TComparable>(TComparable[] array) where TComparable : IComparable
    {
    }

    private static void Exchange<TComparable>(TComparable[] array, int j, int i) where TComparable : IComparable
    {
    }

    private static bool Less<TComparable>(TComparable iComparable, TComparable iComparable_2) where TComparable : IComparable
    {
    }
}

Now your code will compile and work for both reference and value types. This solution also avoids boxing of reference types, as is explained here: Benefits of Generics (C# Programming Guide).

Update

One reason that array covariance does not work for value types, but generic methods do work, is that value types can have different sizes but reference type references all have the same size. All reference type variables TComparable foo occupy 4 (32 bit) or 8 (64 bit) bytes on stack no matter the specific type of TComparable (though of course the managed memory to which they refer can occupy any size). But a comparable value type, say DateTime, may have a different size on the stack than another comparable value type, e.g. Int16. Thus MSIL generated for one need not work for the other.

Generics handle this difference nicely as is described here:

Generics in the Run Time (C# Programming Guide)

When a generic type or method is compiled into Microsoft intermediate language (MSIL), it contains metadata that identifies it as having type parameters. How the MSIL for a generic type is used differs based on whether the supplied type parameter is a value type or reference type.

When a generic type is first constructed with a value type as a parameter, the runtime creates a specialized generic type with the supplied parameter or parameters substituted in the appropriate locations in the MSIL. Specialized generic types are created one time for each unique value type that is used as a parameter.

...

Generics work somewhat differently for reference types. The first time a generic type is constructed with any reference type, the runtime creates a specialized generic type with object references substituted for the parameters in the MSIL. Then, every time that a constructed type is instantiated with a reference type as its parameter, regardless of what type it is, the runtime reuses the previously created specialized version of the generic type. This is possible because all references are the same size.

Incidentally, rather than constraining Key to implement IComparable, you might want to constrain it to implement IComparable<Key>. This guarantees type safety in your comparisons and also avoids boxing of value types.