0

我正在尝试创建一个包含其中的数据结构PriorityQueue。我已经成功地制作了它的非通用版本。我可以说它有效，因为它解决了我遇到的 AI 问题。
这是它的一个片段：

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中自动生成的 a拾取。for(...) yield(...)这导致产生的集合仅包含一个状态的问题。

4

2 回答 2

1

Ordering简单地在您的Node( ) 上定义 anOrdering[Node]并使用已经通用的 Scala 有什么问题PriorityQueue？

作为一般规则，最好使用Ordering[T]than T <: Ordered[T]or T <% Ordered[T]。从概念上讲，Ordered[T]是类型本身的内在（继承或实现）属性。值得注意的是，一个类型只能有一个以这种方式定义的内在排序关系。Ordering[T]是排序关系的外部规范。可以有任意数量的不同Ordering[T].

此外，如果您还没有意识到，您应该知道 和 之间的区别在于T <: U，T <% U前者仅包括名义子类型关系（实际继承），后者还包括应用隐式转换产生符合类型的值边界。

因此，如果您想使用Node <% Ordered[Node]并且没有在类中定义方法，则每次需要进行比较时compare都会应用隐式转换。此外，如果您的类型有自己的，则永远不会应用隐式转换，并且您将被“内置”排序所困扰。compare

附录

我将给出一些基于类的示例，称之为CIString简单地封装 aString并将排序实现为大小写不变的类。

/* 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]()
于 2013-02-13T04:23:44.757 回答
0

好吧，一个可能的问题是您的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].

于 2013-02-13T05:58:01.093 回答