How to apply ordering to a Scala Priority Queue?

2.7k views Asked by At

I've defined a priority queue like so

import scala.collection.mutable.PriorityQueue
...
val queue = new PriorityQueue[(Int,Int)]()

I want to use this ordering:

If we are comparing two items A and B in the queue, A is bigger than B if the first element of its (Int,Int) tuple is larger than B's. If they're the same, then A is bigger than B if the second element of its (Int,Int) tuple is smaller than B's.

How do I define this kind of ordering?

1

There are 1 answers

6
Kolmar On BEST ANSWER

If your elements are Ints, the easiest way to define such an Ordering is by taking a negative of the elements which should be ordered in reverse.

You can create the Ordering, using methods provided by the object Ordering, and pass it to the PriotityQueue either explicitly:

// I'm using the data format, you have provided originally, before the edit
val queue = PriorityQueue(
  (1, (2,3), (4,5)), 
  (2, (3,4), (5,6)), 
  (2, (4,5), (6,7))
)(Ordering.by {
  case (fst, (snd, _), (_, _)) => (fst, -snd)
})

Or implicitly:

implicit val MyOrdering: Ordering[(Int, (Int, Int), (Int, Int))] = 
  Ordering.by {
    case (fst, (snd, _), (_, _)) => (fst, -snd)
  }
val queue = PriorityQueue(
  (1, (2,3), (4,5)), 
  (2, (3,4), (5,6)), 
  (2, (4,5), (6,7)))