使用带有PriorityQueue的隐式排序的困难(Scala)
我正在尝试创建一个包含PriorityQueue的数据结构。我成功地制作了一个非通用的版本。我可以说它有效是因为它解决了我的人工智能问题。
下面是它的一个片段：
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(...)获取了隐式排序。这导致了一个问题，即生成的集合只包含一个状态。
回答 2
Stack Overflow用户
发布于 2013-02-13 04:23:44
简单地在Ordering上定义Node (Ordering[Node])并使用已经泛型的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]()Stack Overflow用户
发布于 2013-02-13 05:58:01
嗯，一个可能的问题是您的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]。
https://stackoverflow.com/questions/14846182
复制相似问题
腾讯云开发者
