Jak używać kolejek priorytetowych w Scali?

Question

Próbuję zaimplementować wyszukiwanie A * w Scali (wersja 2.10), ale natknąłem się na ścianę z cegieł - nie mogę wymyślić, jak użyć kolejki priorytetowej Scala. Wydaje się, że to proste zadanie, ale wyszukiwanie w Google niczego nie zmieniło (z wyjątkiem pojedynczej próbki kodu, która przestała działać w wersji 2.8)

Mam zestaw kwadratów, reprezentowanych przez (Int, Int) s, a także należy wstawić je z priorytetami reprezentowanymi przez Int. W Pythonie jest to dość proste, ponieważ masz tylko listę par klucz, wartość i użyj funkcji heapq, aby ją posortować. Wygląda jednak na to, że krotki Scali nie są nawet porównywalne.

Jak to zrobić? Jestem zaskoczony całkowitym brakiem informacji online, biorąc pod uwagę, jak prosty powinien być.

Answer 1

Jest rzeczywiście pre-defined lexicographical order for tuples - but you need to import it:

import scala.math.Ordering.Implicits._ 

Ponadto można zdefiniować własną kolejność. Załóżmy, że chcemy zorganizować krotki, na podstawie różnicy pomiędzy pierwszym i drugim członków krotki:

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

Answer 2

Rzeczywiście, nie ma domniemanych porządków na parach liczb całkowitych (a, b). Co by to było? Być może są one zarówno pozytywne, jak i możesz użyć (a - 1.0/b)? Lub nie są, i możesz użyć, co, (a + atan (b/pi))? Jeśli masz na myśli zamawianie, możesz rozważyć zawijanie swoich par w typie, który ma twoje zamówienie.