How to use priority queues in Scala?
priority-queue, scala, scala-collections, tuples
Solution
There is actually pre-defined lexicographical order for tuples -- but you need to import it:
import scala.math.Ordering.Implicits._
Moreover, you can define your own ordering. Suppose I want to arrange tuples, based on the difference between first and second members of the tuple:
scala> import scala.collection.mutable.PriorityQueue
// import scala.collection.mutable.PriorityQueue
scala> def diff(t2: (Int,Int)) = math.abs(t2._1 - t2._2)
// diff: (t2: (Int, Int))Int
scala> val x = new PriorityQueue[(Int, Int)]()(Ordering.by(diff))
// x: scala.collection.mutable.PriorityQueue[(Int, Int)] = PriorityQueue()
scala> x.enqueue(1 -> 1)
scala> x.enqueue(1 -> 2)
scala> x.enqueue(1 -> 3)
scala> x.enqueue(1 -> 4)
scala> x.enqueue(1 -> 0)
scala> x
// res5: scala.collection.mutable.PriorityQueue[(Int, Int)] = PriorityQueue((1,4), (1,3), (1,2), (1,1), (1,0))
Problem
I am trying to implement A* search in Scala (version 2.10), but I've ran into a brick wall - I can't figure out how to use Scala's Priority Queue. I have a set of squares, represented by `(Int, Int)`s, and I need to insert them with priorities represented by `Int`s. In Python you just have a list of key, value pairs and use the heapq functions to sort it. So how do you do this?