AnhHao Trần - 8 months ago 48

C# Question

I'm new in C#. I tried to create a heap structure and I came up with this question: How do I pass a "compare-class" to my heap structure? I mean, I want to create a heap like:

`Heap<int, cmp<int>> heap = new Heap<int, cmp<int>>();`

`public class Heap<T, Priority>`

where Priority : IPriority<T>, new()

where T : IComparable

{

private List<T> storage = new List<T>();

private Priority HeapPriority = new Priority();

private void UpHeap(int position)

{

for(var i = position; i > 0; i = (i - 1) >> 1)

{

// Check whether storage[i] is more Priority than storage[(i - 1) >> 1]

if (HeapPriority.MorePriority(storage[i], storage[(i - 1) >> 1])

.CompareTo(storage[i]) == 0)

{

storage.Swap(i, (i - 1) >> 1);

}

else break;

}

}

}

and here is the IPriority interface:

`public interface IPriority<T>`

where T : IComparable

{

T MorePriority(T a, T b);

}

and I used the Heap like this:

`public class Min<T> : IPriority<T>`

where T : IComparable

{

public Min() { }

public T MorePriority(T a, T b)

{

return a.CompareTo(b) <= 0 ? a : b;

}

}

static public void TestHeap()

{

var heap = new Heap<Pair<long, int>, Min<Pair<long, int>>>();

heap.Add(Pair<long, int>(10, 20));

heap.Add(Pair<long, int>(21, 100));

// ...

}

but I want a heap that sorts the items by any way that I want, not only max-min order. Moreover, is there a way to use "Ipriority.MorePriority" as a static method?, because it's working just like a static method. Can anyone give me some advices?

Sorry for my bad English.

Answer

I suggest treating `IComparer<T>`

as a *dependence* and pass it to constructor; something like this:

```
// You can create a heap of any type, right?
// But in some cases (e.g. Heap<Button>) you should provide a comparer:
// how to compare Button instances
public class Heap<T> {
//TODO: implement here Heap as well as Unheap method having IComparer<T> m_Comparer
...
private IComparer<T> m_Comparer;
// comparer = null - if comparer is not provided, try to use default one
// if it's possible (e.g. in case of Heap<double>)
public Heap(IComparer<T> comparer = null): base() {
// Do we have a default comparer (e.g. for int, double, string)?
if (null == comparer)
if (typeof(IComparable).IsAssignableFrom(typeof(T)) ||
typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
comparer = Comparer<T>.Default;
if (null == comparer)
throw new ArgumentNullException("comparer", string.Format(
"There's no default comparer for {0} class, you should provide it explicitly.",
typeof(T).Name));
m_Comparer = comparer;
}
...
}
```

So you can create heaps

```
// heap of integers, default comparer
Heap<int> heap1 = new Heap<int>();
// heap of integers, custom comparer (via lambda)
Heap<int> heap2 = new Heap<int>(Comparer<int>.Create((x, y) => -x.CompareTo(y)));
// heap of Buttons, custome comparer
Heap<Button> heap3 = new Heap<Button>(Comparer<Button>.Create((x, y) => ...));
```

And this will *throw exception*: no default comparer for `Button`

class

```
Heap<Button> heapErr = new Heap<Button>();
```