Как использовать очереди приоритетов в Scala?

Я пытаюсь реализовать A * поиск в Scala (версия 2.10), но я столкнулся с кирпичной стеной - я не могу понять, как использовать Scala Priority Queue. Это похоже на простую задачу, но поиск в Google ничего не показал (кроме одного примера кода, который перестает работать в версии 2.8)

У меня есть набор квадратов, представленных (Int, Int) s, и мне нужно вставить их с приоритетами, представленными Int s. В Python это довольно просто, поскольку у вас есть только список пар ключей, значений и используйте функции heapq для его сортировки. Но похоже, что кортежи Scala даже не сопоставимы.

Итак, как вы это делаете? Меня удивляет полное отсутствие онлайн-информации, учитывая, насколько это просто.

Ответы

Ответ 1

Фактически предопределенный лексикографический порядок для кортежей - но вам нужно импортировать он:

import scala.math.Ordering.Implicits._

Кроме того, вы можете определить свой собственный заказ. Предположим, я хочу упорядочить кортежи, основываясь на различии между первым и вторым членами кортежа:

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))

Ответ 2

Действительно, не существует неявного упорядочения на парах целых чисел (a, b). Что бы это могло быть? Возможно, они оба позитивны, и вы можете использовать (a - 1.0/b)? Или это не так, и вы можете использовать, что, (a + atan (b/pi))? Если у вас есть заказ, вы можете рассмотреть возможность объединения ваших пар в тип, который имеет ваш заказ.