17

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 Ints. 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?

samthebest
  • 30,803
  • 25
  • 102
  • 142
Antimony
  • 37,781
  • 10
  • 100
  • 107

2 Answers2

27

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))
Community
  • 1
  • 1
om-nom-nom
  • 62,329
  • 13
  • 183
  • 228
-1

Indeed, there is no implicit ordering on pairs of integers (a, b). What would it be? Perhaps they are both positive and you can use (a - 1.0/b)? Or they are not, and you can use, what, (a + atan(b/pi))? If you have an ordering in mind, you can consider wrapping your pairs in a type that has your ordering.

minopret
  • 4,726
  • 21
  • 34
  • Well the natural ordering is lexicographical, which is what C++ and Python do. Silly me for assuming Scala is at least as functional as C++. – Antimony Feb 17 '13 at 23:46
  • @Antimony: Just to clarify: The C++ language and its standard libraries themselves contain this ordering? – Randall Schulz Feb 18 '13 at 03:10