C# Generics: Inserting T as the where T : IComparable<T> interface conflict

Question

This is a challenge for the C# generics / design patterns masters.

I'm trying to implement a generic heap, and then a priority queue that uses the heap.

My heap's signature is:

class Heap<TKey, TValue> where TKey : IComparable<TKey>

My priority queue class is:

public delegate IComparable<T> Evaluator<T>(T item);

class PriorityQueue<T> : IQueue<T>
{
    Evaluator<T> Evaluate;
    Heap<IComparable<T>, T> m_heap;

    public PriorityQueue(Evaluator<T> evaluateFunction)
    {
        Evaluate = evaluateFunction;
        m_heap = new Heap<int, T>(HeapType.MinHeap);
    }

    ...

    public void Insert(T element)
    {
        m_heap.Insert(Evaluate(element), element);
    }

    ...

But when doing so, the compiler (justifiably) complains that ICompareble doesn't implement the ICompareble interface, hence

Heap<IComparable<T>, T> m_heap;

conflicts with

where TKey : IComparable<TKey>

What can you do to solve this?!

full compiler error:

The type 'System.IComparable<T>' cannot be used as type parameter 'TKey' in the generic type or method 'Heap<TKey,TValue>'. There is no implicit reference conversion from 'System.IComparable<T>' to 'System.IComparable<System.IComparable<T>>'.

Answer 1

I think if you replace..

class Heap<TKey, TValue> where TKey : IComparable<TKey>

..with..

class Heap<TKey, TValue> where TKey : IComparable<TValue>

..it will work as you intend it to work.

Answer 2

Your implementation is pretty muddled. It seems to me like this is sufficient:

// replaces existing Evaluator signature.  I would personally ditch this
// definition and just use Func<TValue, TKey> instead
public delegate TKey Evaluator<TKey, TValue>(TValue item);

class PriorityQueue<T>
{
    Evaluator<int, T> Evaluate;
    Heap<int, T> m_heap;

    public PriorityQueue(Evaluator<int, T> evaluateFunction)
    {
        Evaluate = evaluateFunction;
        m_heap = new Heap<int, T>(HeapType.MinHeap);
    }

    public void Insert(T element)
    {
        m_heap.Insert(Evaluate(element), element);
    }
}

Is there some reason the priority queue should have a generic key? If so, then you should specify PriorityQueue<TKey, TValue> instead and replace int with TKey, adding the constraint that TKey : IComparable<TKey> (just like in your heap's signature.)

Basically, your priority queue's definition should either look like your heap's definition, if you want the key to be of any type, or the same but not parameterized on the key type.

Answer 3

I think it would be much better if you relied on an IComparer<T> rather than your Evaluator<T> delegate. In any case, as a direct answer to your question:

class Heap<TKey, TValue> where TKey : IComparable<TKey> { }

public delegate TOutput Evaluator<TInput, TOutput>(TInput item) where TOutput : IComparable<TOutput>;

class PriorityQueue<TInput, TTransformComparable> where TTransformComparable : IComparable<TTransformComparable>
{
    Evaluator<TInput, TTransformComparable> Evaluate;
    Heap<TTransformComparable, TInput> m_heap;

    public PriorityQueue(Evaluator<TInput, TTransformComparable> evaluateFunction)
    {
        Evaluate = evaluateFunction;
        m_heap = new Heap<TTransformComparable, TInput>(HeapType.MinHeap);
    }     

    public void Insert(TInput element)
    {
        m_heap.Insert(Evaluate(element), element);
    }    
}