使用Implicit排序問題使用PriorityQueue（斯卡拉）

Question

我試圖創建一個其中包含PriorityQueue的數據結構。我成功地製作了它的非通用版本。我可以告訴它，因爲它解決了A.I.我有問題。
這裏是它的一個片段：

class ProntoPriorityQueue { //TODO make generic 

implicit def orderedNode(node: Node): Ordered[Node] = new Ordered[Node] { 
    def compare(other: Node) = node.compare(other) 
} 

val hashSet = new HashSet[Node] 
val priorityQueue = new PriorityQueue[Node]() 
... 

我試圖使它通用，但如果我用這個版本，它停止解決問題：

class PQ[T <% Ordered[T]] { 
//[T]()(implicit val ord: T => Ordered[T]) { 
//[T]()(implicit val ord: Ordering[T] { 

val hashSet = new HashSet[T] 
val priorityQueue = new PriorityQueue[T] 
... 

我也試過什麼評論而不是使用[T <% Ordered[T]]

這裏走出來的是調用PQ代碼：

//the following def is commented out while using ProntoPriorityQueue 
implicit def orderedNode(node: Node): Ordered[Node] = new Ordered[Node] { 
    def compare(other: Node) = node.compare(other) 
} //I've also tried making this return an Ordering[Node] 

val frontier = new PQ[Node] //new ProntoPriorityQueue 
//have also tried (not together): 
val frontier = new PQ[Node]()(orderedNode) 

我也嘗試將隱式def移動到Node對象（並導入它），但基本上是同樣的問題。

我在做什麼錯誤的通用版本？我應該在哪裏隱含？

---

解決方案 這個問題是不是與我的隱含定義。問題在於隱含的排序被Set拾取，該排列在for(...) yield(...)語句中自動生成。這在導致集合只包含一個狀態的情況下引起了一個問題。

Answer 1

簡單地在您的Node（Ordering[Node]）上定義Ordering並使用已有的通用Scala PriorityQueue？

作爲一般規則，最好使用Ordering[T]而不是T <: Ordered[T]或T <% Ordered[T]。從概念上講，Ordered[T]是類型本身的內在（繼承或實現）屬性。值得注意的是，一種類型可以只有一種以這種方式定義的內在排序關係。 Ordering[T]是訂購關係的外部規格。可以有任何數量的不同Ordering[T]。另外，如果您還沒有意識到，您應該知道T <: U和T <% U之間的區別在於前者只包含名義上的子類型關係（實際繼承），後者還包括應用隱式轉換，一個符合類型綁定的值。

所以，如果你想使用Node <% Ordered[Node]和你沒有在類中定義的方法compare，隱式轉換將每一個比較需要進行時應用。此外，如果您的類型有它自己的compare，則隱式轉換將永遠不會應用，並且您將陷入「內置」排序。

附錄

我給基於一類的幾個例子，稱之爲CIString，簡單地封裝了String和工具作爲訂貨情況不變。

/* Here's how it would be with direct implementation of `Ordered` */ 

class CIString1(val s: String) 
extends Ordered[CIString1] 
{ 
    private val lowerS = s.toLowerCase 

    def compare(other: CIString1) = lowerS.compareTo(other.lowerS) 
} 

/* An uninteresting, empty ordered set of CIString1 
    (fails without the `extends` clause) */ 
val os1 = TreeSet[CIString1]() 


/* Here's how it would look with ordering external to `CIString2` 
    using an implicit conversion to `Ordered` */ 

class CIString2(val s: String) { 
    val lowerS = s.toLowerCase 
} 

class CIString2O(ciS: CIString2) 
extends Ordered[CIString2] 
{ 
    def compare(other: CIString2) = ciS.lowerS.compareTo(other.lowerS) 
} 

implicit def cis2ciso(ciS: CIString2) = new CIString2O(ciS) 

/* An uninteresting, empty ordered set of CIString2 
    (fails without the implicit conversion) */ 
val os2 = TreeSet[CIString2]() 


/* Here's how it would look with ordering external to `CIString3` 
    using an `Ordering` */ 

class CIString3(val s: String) { 
    val lowerS = s.toLowerCase 
} 

/* The implicit object could be replaced by 
    a class and an implicit val of that class */ 
implicit 
object CIString3Ordering 
extends Ordering[CIString3] 
{ 
    def compare(a: CIString3, b: CIString3): Int = a.lowerS.compareTo(b.lowerS) 
} 

/* An uninteresting, empty ordered set of CIString3 
    (fails without the implicit object) */ 
val os3 = TreeSet[CIString3]() 

Answer 2

那麼，一個可能的問題是，你的Ordered[Node]不是一個Node：

implicit def orderedNode(node: Node): Ordered[Node] = new Ordered[Node] { 
    def compare(other: Node) = node.compare(other) 
} 

我想嘗試用Ordering[Node]代替，你說你嘗試過，但沒有太多有關更多信息。 PQ將被宣佈爲PQ[T : Ordering]。