Scala: Is there a way to use PriorityQueue like I would in Java?

Question

I have a class that I would like to use in a scala.collection.mutable.PriorityQueue, but I don't want to make it Ordered[A] just for this one purpose. I don't consider the ordering I want to use with respect to the PriorityQueue as the natural ordering of the class.

class MyObject (sequence: Int, values: List[String]) ...

So, in my PriorityQueue, I would like the values to be ordered by 'sequence'. However, just because two objects have the same sequence doesn't make them naturally equal since the contents of their 'values' may be different.

This is where, in Java, it's nice to be able to supply an alternate Comparator object to the PriorityQueue. My Comparator would simply order the objects with respect to their 'sequence' and ignores their 'values'.

The PriorityQueue class must be parameterized with a "A <% Ordered[A]"

class PriorityQueue[A <% Ordered[A]] extends ...

From what I've read, this means my class must extend Ordered[A] or I must provide an "implicit def" type conversion to Ordered[A], which, honestly, feels inelegant.

The Java solution seems more "functional" allowing me to pass a Comparator function-like object instead of forcing me into a class hierarchy or monkeypatching my class.

I realize there are alternatives to using PrioirityQueue, but I feel like I may be bumping up against the Scala learning curve here and don't want to give up without exploring this design decision fully.

Is this just an unfortunate decision in the Scala library or am I misunderstanding some sort of calling convention that makes PriorityQueue more usable and 'functional'?

Thanks

Answer 1

The conversion function of A to Ordered[A] can play the role of Java comparator. The function needs to be visible only in the scope where you create PriorityQueue, so it's not going to become "natural ordering" for your object.

Answer 2

The syntax

class PriorityQueue[A <% Ordered[A]] ...

is really just a light sugaring on top of

class PriorityQueue[A]()(implicit convert: A => Ordered[A]) ...

This means you can write your own method A => Ordered[A]

case class Foo(n: Int)
def orderedFoo(f: Foo): Ordered[Foo] = new Ordered[Foo] {
  def compare(other: Foo) = f.n.compare(other.n)
}

And manually pass it into your PriorityQueue constructor

new PriorityQueue[Foo]()(orderedFoo)

Answer 3

Combining both (correct) answers before this one into compilable code:

object o {
  case class Foo(n: Int)
  implicit def orderedFoo(f: Foo): Ordered[Foo] = new Ordered[Foo] {
    def compare(other: Foo) = f.n.compare(other.n)
  }

  val x = new scala.collection.mutable.PriorityQueue[Foo]()
}

His example wouldn't compile for you only because (I am supposing) you threw it at the compiler as-is. You can't compile top level methods in scala, everything has to be in an object.

Answer 4

The scalgorithms project on Google Code might be of interest. It has binomial and Fib heaps, among a number of other data structures and algorithms.

Answer 5

In scala 2.8.0, the PriorityQueue changes to

class  PriorityQueue[A](implicit ord : Ordering[A])

And the Ordering[A] in Scala is similar to Comparator in Java