如何在插入列表時執行基於規則的對象排序

Question

我有一個接口IRenderable和一個管理呈現實現接口的類的所有實例的類。

我在我的代碼中有很多類，並期望別人創建實現相同接口的類。

由於渲染的本質，我想說的是「在此類的實例之前繪製此類的實例」。

典型的方法是讓每一個類實現一個DrawOrder財產，但是我不喜歡這一點，因爲類沒有一個明確的抽籤順序值，它是相對順序的事項。如果我給每個班級一個DrawOrder屬性，那麼實現該接口的任何人都需要知道所有班級的價值。顯然，如果很多人能夠實施他們自己的課程，這是不可能的。

---

我想什麼是能夠定義規則說「ClassA的ClassB的前，ClassA的前ClassC」，然後制定出在平局順序/添加情況下，我可以推斷出正確的繪製順序。其他實現接口的人可以添加他們自己的規則，這些規則與內置的實現和他們自己的添加相關

---

編輯：什麼我希望的是一些管理規則和管理維護的順序，像下面的類：

class Renderer 
{ 
    private List<Rule> Rules; 

    private List<IRenderable> Renderables; 

    // Adds to list of rules 
    void EnforceBefore(Type FirstClass, Type SecondClass); 

    // Inserts items ensuring all rules are followed. 
    void Insert(IRenderable ClassInstance); 

    void RenderAll(); 
} 

類可以再添加規則，適當的（或我可以有一個返回它們的接口方法）。

下面是一個快速測試不起作用

using System; 
using System.Collections.Generic; 
using System.Linq; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     List<string> MyList = new List<string> { "wherever", "second", "first", "third", "first", "third", "second" }; 

     RuleBasedComparer<string> RuleComparer = new RuleBasedComparer<string>(); 

     // I want to ensure all instances of "first" appear in the list before all instances of "second" 
     // and all instances of "second" appear in the list before all instances of "third". 
     // I don't care where "wherever" appears (or anything beyond the above rules) 

     RuleComparer.AddRule("first", "second"); 
     RuleComparer.AddRule("second", "third"); 

     MyList.Sort(RuleComparer); 

     foreach (var item in MyList) 
      Console.WriteLine(item); 
     Console.ReadKey(); 
    } 
} 

public class RuleBasedComparer<T> : Comparer<T> 
{ 
    private class OrderRule 
    { 
     public readonly T Before; 
     public readonly T After; 

     public OrderRule(T before, T after) 
     { 
      Before = before; 
      After = after; 
     } 
    } 

    private List<OrderRule> _Rules = new List<OrderRule>(); 

    public void AddRule(T before, T after) 
    { 
     _Rules.Add(new OrderRule(before, after)); 
    } 

    public override int Compare(T x, T y) 
    { 
     // Find the applicable rule for this pair (if any) 
     var ApplicableRule = _Rules.Where(or => or.After.Equals(x) && or.Before.Equals(y) || 
               or.After.Equals(y) && or.Before.Equals(x)).SingleOrDefault(); 

     if (ApplicableRule != null) 
     { 
      // If there is a rule then if x should be before y then return -1, otherwise return 1 
      if (ApplicableRule.Before.Equals(x)) 
       return -1; 
      else 
       return 1; 
     } 
     else 
     { 
      // If no rule exists then say they are equal 
      return 0; 
     } 
    } 
} 

---

TL; DR：我如何從這樣說：「ClassB的前ClassA的」規則去確定排序的實例/類。
由缺乏完整的規則而產生的含糊不應該是重要的，我只想遵守現有的規則。

Answer 1

我已經設法弄清楚了一種似乎可行的方法（下面的完整代碼示例）。

基本上，我添加了我的規則，然後通過將它們逐個插入到列表中來分配規則中包含的所有內容，並在添加每個規則時觀察規則。該項目在列表中的位置成爲排序。當比較列表中的2件事（不是規則）時，我只返回0.

using System; 
using System.Collections.Generic; 
using System.Linq; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     List<string> MyList = new List<string> { "second", "first", "second2", "wherever", "third", "second2", "third", "second", "first" }; 

     RuleBasedComparer<string> RuleComparer = new RuleBasedComparer<string>(); 

     // I want to ensure all instances of "first" appear in the list before all instances of "second" and "second2" 
     // and all instances of "second" and "second2" appear in the list before all instances of "third". 
     // I don't care where "wherever" appears (or anything beyond the above rules) 

     RuleComparer.AddRule("first", "second"); 
     RuleComparer.AddRule("first", "second2"); 
     RuleComparer.AddRule("second", "third"); 
     RuleComparer.AddRule("second2", "third"); 

     MyList.Sort(RuleComparer); 

     foreach (var item in MyList) 
      Console.WriteLine(item); 
     Console.ReadKey(); 
    } 
} 

public class RuleBasedComparer<T> : Comparer<T> 
{ 
    private class OrderRule 
    { 
     public readonly T Before; 
     public readonly T After; 

     public OrderRule(T before, T after) 
     { 
      Before = before; 
      After = after; 
     } 
    } 

    private List<OrderRule> _Rules = new List<OrderRule>(); 

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

    private bool _NeedToCalculateOrdering = true; 

    public void AddRule(T before, T after) 
    { 
     if (!_NeedToCalculateOrdering) 
      throw new InvalidOperationException("Cannot add rules once this comparer has."); 

     _Rules.Add(new OrderRule(before, after)); 
    } 

    private void CalculateOrdering() 
    { 
     _NeedToCalculateOrdering = false; 

     var ItemsToOrder = _Rules.SelectMany(r => new[] { r.Before, r.After }).Distinct(); 


     foreach (var ItemToOrder in ItemsToOrder) 
     { 
      var MinIndex = 0; 
      var MaxIndex = DesiredOrdering.Count; 

      foreach (var Rule in _Rules.Where(r => r.Before.Equals(ItemToOrder))) 
      { 
       var indexofAfter = DesiredOrdering.IndexOf(Rule.After); 

       if (indexofAfter != -1) 
       { 
        MaxIndex = Math.Min(MaxIndex, indexofAfter); 
       } 
      } 

      foreach (var Rule in _Rules.Where(r => r.After.Equals(ItemToOrder))) 
      { 
       var indexofBefore = DesiredOrdering.IndexOf(Rule.Before); 

       if (indexofBefore != -1) 
       { 
        MinIndex = Math.Max(MinIndex, indexofBefore + 1); 
       } 
      } 

      if (MinIndex > MaxIndex) 
       throw new InvalidOperationException("Invalid combination of rules found!"); 

      DesiredOrdering.Insert(MinIndex, ItemToOrder); 
     } 
    } 

    public override int Compare(T x, T y) 
    { 
     if (_NeedToCalculateOrdering) 
      CalculateOrdering(); 

     if (x == null && y != null) 
     { 
      return -1; 
     } 
     else if (x != null && y == null) 
      return 1; 
     else if (x == null && y == null) 
      return 0; 

     // Find the applicable rule for this pair (if any) 
     var IndexOfX = DesiredOrdering.IndexOf(x); 
     var IndexOfY = DesiredOrdering.IndexOf(y); 

     if (IndexOfX != -1 && IndexOfY != -1) 
     { 
      // We have a definite order 
      if (IndexOfX > IndexOfY) 
       return 1; 
      else if (IndexOfX < IndexOfY) 
       return -1; 
      else 
       return 0; 
     } 
     else if (IndexOfX != -1) 
     { 
      return -1; 
     } 
     else if (IndexOfY != -1) 
     { 
      return 1; 
     } 
     else 
     { 
      return 0; // Or maybe compare x to y directly 
      //return Comparer<T>.Default.Compare(x, y); 
     } 
    } 
} 

Answer 2

您可以添加兩個屬性，這將需要一個類型作爲參數，並要求目標類爲IRenderable。

[Before(typeof(MyClass))] 

[After(typeof(MyClass))] 

然後你必須獲取實現IRenderable所有類和檢索這些屬性。

然後，你所要做的就是按照正確的順序對它們進行排序（我依靠一個算法專家在這個算法上找到一個奇特的算法名稱）。

如果結果不明確（即：兩個類在同一個類之後），您必須決定如何處理。

當然，你可以通過相同的接口實現類似的邏輯，但是這在我看來略微超出了IRenderable的職責範圍，所以我會做另一個。

HTH，

巴布。

Answer 3

渲染器能否確定所有類的排序，甚至那些還沒有實現的類？如果是這樣，那麼你可以創建一個IComparer<IRenderable>。如果你不知道將來實現的類的期望順序是什麼，那麼這比依靠實施者明確指定繪製順序更不可行！

通常對於例如渲染時，通常可以確定對象的屬性的繪製順序，因此您可以有一個比較器根據已知的渲染屬性（例如透明度，UI層等）決定渲染順序。

public class RenderOrderComparer : IComparer<IRenderable> 
{ 
    public int Compare(IRenderable a, IRenderable b) 
    { 
     if (a.IsOverlay && !b.IsOverlay) 
     return -1; 
     if (b.IsOverlay && !a.IsOverlay) 
     return 1, 
     if (a.IsTransparent && !b.IsTransparent) 
     return -1; 
     if (b.IsTransparent && !a.IsTransparent) 
     return 1; 
     // ...and so on. 

     return 0; 
    } 
} 

（請注意，您應該考慮延長的Comparer而不是實施的IComparer，看到MSDN Documentation on IComparer）

另一種選擇是一個比較規則基於每個類的解決方案，你讓所有的類決定通過實現了IComparable接口。這使得每個班級都有機會在其他（已知）班級之前/之後進行自我排序。這裏的缺點當然是它不能爲它不知道存在的類提供規則。另外，您不能確定ClassA是否應該在ClassB之前呈現它，而ClassB是否應該在ClassA之前呈現它。像這樣的方案要求您維護所有類型的順序，以確保它是一致的。基本上你最終會得到一個分佈在所有類中的比較器實現，這可能是一件壞事。

public interface IRenderable : IComparable<IRenderable> 
{ 
    int Id { get; } 
} 

public class SomeRenderable : IRenderable 
{ 
    public int CompareTo(IRenderable other) 
    { 
     if (other is SomeRenderable) 
     return 0; 
     if (other is OtherRenderableType) 
     return 1; 
    } 
}