Priority queue with custom ordering

Question

I have this case class:

case class Offer(id: Int, amount: Int, interestRate: Double) extends Ordered[Offer] {

  def compare(that: Offer) = interestRate.compareTo(that.interestRate)
}

As you can see, I defined the ordering based upon Offer.interestRate. I want the ordering to be increasing.

I created these offers:

Offer(1, 5, 4.0)
Offer(2, 5, 0.5)
Offer(3, 5, 1.5)

and added them to a priority queue:

val currentOffers: mutable.PriorityQueue[Offer] = mutable.PriorityQueue.empty[Offer]

The problem is that when I do currentOffers.dequeue() I get Offer(1, 5, 4.0).

Instead, I would like to get:

Offer(2, 5, 0.5)

What do I need to change?

score 7 · Accepted Answer · answered Sep 06 '16 at 08:17

As others hinted without much explaining, the problem is your comparison function:

def compare(that: Offer) = this.interestRate.compareTo(that.interestRate)

This matches the natural ordering for numbers where -1 < 0 < 1.

When you create a priority queue in Scala it uses an Ordering which is implicitly derived from the Order you've defined. The thing that you're missing is that the priority queue will consider the "higher" value as having the highest priority (basically it sorts descending).

The easiest fix for this would be to change the compare function to its inverse:

def compare(that: Offer) = that.interestRate.compareTo(this.interestRate)

Note the inversion of that and this.

Another option would be to provide the Ordering when building the queue:

val q = mutable.PriorityQueue(
  Offer(1, 5, 4.0),
  Offer(2, 5, 0.5),
  Offer(3, 5, 1.5)
)(Ordering.by[Offer, Double](_.interestRate).reverse)

What this does is: "create an ordering for Offers by sorting the interest rate in reverse".

I like the second option better because it provides better granularity and allows to have multiple orderings used when necessary.

Priority queue with custom ordering

1 Answers1