Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 403
Joe Holloway Avatar asked Apr 25 '09 16:04

Joe Holloway


4 Answers

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)
like image 72
Jorge Ortiz Avatar answered Nov 09 '22 08:11

Jorge Ortiz


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.

like image 38
Yardena Avatar answered Nov 09 '22 07:11

Yardena


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.

like image 2
psp Avatar answered Nov 09 '22 06:11

psp


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

like image 2
Eastsun Avatar answered Nov 09 '22 06:11

Eastsun