Generics and IComparable - error CS00301

Question

I've tried to develop a generic class "MinHeap(T)" implementing IComparable. It works fine when generic is "int" or another class "Code". Going further and using for T a generic class "Node(Code)" leads to the error mentioned below.

I'm probably too new and not understanding subtle differences between IComparable and IComparable(T). Does someone have an idea ? Thanks in advance for your help, LJ

public class MinHeap<T> where T : IComparable
{
...
}
public class Node<T> where T : IComparable
{
    T data
...
    public int CompareTo(object obj)
    {
        Node<T> otherNode = obj as Node<T>;
        return this.data.CompareTo(otherNode.data);
    }
...
}
public class Code : IComparable
{
    public int freq;
...
    public int CompareTo(object obj)
    {
        Code otherCode = obj as Code;
        return this.freq.CompareTo(otherCode.freq);
    }
}
static void Main(string[] args)
{
    MinHeap<int> hInt = new MaxHeap<int>(heapSeed); // works fine
    MinHeap<Code> hCode = new MinHeap<Code>(codeList); // works fine
...
    Node<Code>[] nodeCodeList = new Node<Code>[freqList.Length]; // ok        
    MinHeap<Node<Code>> h = new MinHeap<Node<Code>>(nodeCodeList); // Error
...
}

Error message:

Error 2 The type 'Algorithms.Node(Algorithms.Code)' cannot be used as type parameter 'T' in the generic type or method 'Algorithms.MinHeap(T)'. There is no implicit reference conversion from 'Algorithms.Node(Algorithms.Code)' to 'System.IComparable'.

Answer 1

The class Node<T> does not implement IComparable. It just haves a constraint for the type of T.

It looks like you've tried to implement the decorator pattern. Implement the interface as well and then map the methods to the decorated object.

Answer 2

You're probably better off defining your generic class so that it doesn't require the type to implement IComparable<T>. That's how the .NET generic classes are implemented. They will use the default comparison for the type, or use the IComparer<T> that you pass in. For example, SortedList has these constructors (among others):

SortedList<TKey, TValue>(); // uses default comparer for TKey
SortedList<TKey, TValue>(IComparer<T> comparer); // uses supplied comparer

It's easy enough to implement:

public class MinHeap<T>
{
    private IComparer<T> _comparer;

    public MinHeap<T>(IComparer<T> comp)
    {
        _comparer = comp;
    }

    public MinHeap<T>()
        : this(Comparer<T>.Default)
    {
    }
}

That way, your clients can use MinHeap<T> to hold instances of classes that do not implement IComparable<T>.

When you do your comparisons, you call _comparer.Compare(item1, item2)

On another note, there's no particular need for your heap to require a node. You can implement a binary heap in an array. See, for example, A Generic BinaryHeap Class.

Answer 3

You should implement IComparable interface within Node class, like this:

  public class Node<T>: IComparable<Node<T>> // <- IComparable<Node<T>> implemented  
    where T: IComparable  {

    T data;

    ...

    #region IComparable<Node<T>> Members

    // interface implementation, not just a method
    public int CompareTo(Node<T> other) {
      // Let us be accurate with possible nulls:  
      if (Object.ReferenceEquals(null, other))
        return 1; // <- or -1 if you think it's right
      else if (Object.ReferenceEquals(data, other.data))   
        return 0;
      else if (Object.ReferenceEquals(null, data))   
        return -1; // <- or 1 if you think it's right

      return data.CompareTo(other.data);
    }

    #endregion IComparable<Node<T>> Members
  }

depending on algorithm of min heap, you may have to implement IComparable> in MinHeap class as well