CODEWITHSUNDEEP
scalapriority-queueimplicits
Tombstone
Tombstone

Reputation: 177

Trouble using Implicit Ordered with PriorityQueue (Scala)

I'm trying to create a data structure that has a PriorityQueue in it. I've succeeded in making a non-generic version of it. I can tell it works because it solves the A.I. problem I have.
Here is a snippet of it:

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]()
...

I'm trying to make it generic, but if I use this version it stops solving the problem:

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]
...

I've also tried what's commented out instead of using [T <% Ordered[T]]

Here is the code that calls 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)

I've also tried moving the implicit def into the Node object (and importing it), but essentially the same problem.

What am I doing wrong in the generic version? Where should I put the implicit?

Solution The problem was not with my implicit definition. The problem was the implicit ordering was being picked up by a Set that was automatically generating in a for(...) yield(...) statement. This caused a problem where the yielded set only contained one state.

Upvotes: 0

Views: 784

Answers (2)

Randall Schulz
Randall Schulz

Reputation: 26486

What's wrong with simply defining an Ordering on your Node (Ordering[Node]) and using the already-generic Scala PriorityQueue?

As general rule, it's better to work with Ordering[T] than T <: Ordered[T] or T <% Ordered[T]. Conceptually, Ordered[T] is an intrinsic (inherited or implemented) property of the type itself. Notably, a type can have only one intrinsic ordering relationship defined this way. Ordering[T] is an external specification of the ordering relationship. There can any be any number of different Ordering[T].

Also, if you're not already aware, you should know that the difference between T <: U and T <% U is that while the former includes only nominal subtype relations (actual inheritance), the latter also includes the application of implicit conversions that yield a value conforming to the type bound.

So if you want to use Node <% Ordered[Node] and you don't have a compare method defined in the class, an implicit conversion will be applied every time a comparison needs to be made. Additionally, if your type has its own compare, the implicit conversion will never be applied and you'll be stuck with that "built-in" ordering.

Addendum

I'll give a few examples based on a class, call it CIString that simply encapsulates a String and implements ordering as case-invariant.

/* 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]()

Upvotes: 1

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297205

Well, one possible problem is that your Ordered[Node] is not a Node:

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

I'd try with an Ordering[Node] instead, which you say you tried but there isn't much more information about. PQ would be declared as PQ[T : Ordering].

Upvotes: 0

Related Questions