비교 클래스를 제네릭 형식으로 전달하는 C#.

Question

C#의 새로운 기능입니다. 나는 힙 구조를 만들려고했는데이 질문을 생각해 냈습니다 : 어떻게하면 힙 구조에 "비교 클래스"를 전달할 수 있습니까? 제 말은 다음과 같이 힙을 생성하고 싶습니다. Heap<int, cmp<int>> heap = new Heap<int, cmp<int>>(); "cmp"는 우선 순위에 따라 힙을 만드는 비교 클래스입니다 (C++의 priority_queue에 대한 아이디어를 가졌습니다).

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; 
     } 
    } 
} 

여기에 iPriority의 인터페이스입니다 : 나는 최대 분 비교자를 소요 힙 만들기에 (내가 생각하는) 성공이

public interface IPriority<T> 
    where T : IComparable 
{ 
    T MorePriority(T a, T b); 
} 

와 나는이 같은 힙을 사용 :

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)); 
     // ... 
    } 

하지만 원하는 방식으로 항목을 정렬하는 힙을 원하지만, 최대 최소 순서가 아닙니다. 게다가 정적 메서드처럼 "Ipriority.MorePriority"를 정적 메서드로 사용하는 방법이 있습니까? 아무도 내게 어떤 조언을 줄 수 있습니까? 나쁜 영어로 죄송합니다.

Answer 1

IComparer<T>을 의존성으로 처리하여 생성자에게 전달하는 것이 좋습니다. 이 같은 : Button 클래스에 대한 기본 비교가

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

Answer 2

당신은 단지 IComparer<T>를 사용해서는 안 :

// 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; 
    } 
    ... 
    } 

그래서 당신은 힙

// 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) => ...)); 

그리고이 것 던져 예외를 만들 수 있습니다 .NET의 모든 컬렉션이 사용하는 것입니다. 예를 들어 :

public class Heap<T> 
{ 
    private IComparer<T> comparer; 
    private List<T> storage = new List<T>();  

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

    public Heap(IComparer<T> comparer) 
    { 
     this.comparer = comparer; 
    } 

    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 (comparer.Compare(storage[i], storage[(i - 1) >> 1]) > 0) 
      { 
       storage.Swap(i, (i - 1) >> 1); 
      } 
      else break; 
     } 
    } 
} 

이 몇 가지 장점이 있습니다 :

• 당신은 다른 방법에 힙을 참조 할 때 훨씬 더 편리한 비교 자에 대한 별도의 형식 매개 변수가 필요하지 않습니다.
• T을 IComparable으로 제한 할 필요가 없습니다.
• 그러나 (Int32처럼) ICompatable을 구현하면 Comparer<T>.Default이 해당 구현을 사용합니다.