Scala - как заставить SortedSet с пользовательским упорядочением содержать несколько разных объектов, имеющих одинаковое значение, по которому мы сортируем?

Question

, как указано в заголовке, у меня есть SortedSet с пользовательским порядком.Набор содержит объекты класса Edge (представляющие ребро на графе).С каждым ребром связана стоимость, а также начальная и конечная точки.

case class Edge(firstId : Int, secondId : Int, cost : Int) {}

Мой порядок сортировки ребер SortedSet выглядит следующим образом (это для алгоритма A *):

  object Ord {
val edgeCostOrdering: Ordering[Edge] = Ordering.by { edge : Edge =>
 if (edge.secondId == goalId) graphRepresentation.calculateStraightLineCost(edge.firstId, goalId) else edge.cost + graphRepresentation.calculateStraightLineCost(edge.secondId, goalId)
}

}

Однако после того, как я применил указанное упорядочение к набору и попытался отсортировать ребра, которые имеют разные начальные / конечные точки, но одинаковую стоимость - в наборе остается только последнее обнаруженное ребро.

Например:

val testSet : SortedSet[Edge] = SortedSet[Edge]()(edgeOrder)
val testSet2 = testSet + Edge(1,4,2)
val testSet3 = testSet2 + Edge(3,2,2)
println(testSet3)

Только отпечатки (3,2,2)

Разве это не отдельные объекты?Они имеют одинаковое значение только для одного поля, поэтому неужели Set не сможет это обработать?

Answer 1

Чтобы сохранить все различные Edge с одинаковым значением стоимости заказа в SortedSet, вы можете изменить функцию Ordering.by так, чтобы она возвращала Tuple, который также включает идентификаторы ребер:

val edgeCostOrdering: Ordering[Edge] = Ordering.by { edge: Edge =>
  val cost = if (edge.secondId == goalId) ... else ...
  (cost, edge.firstId, edge.secondId)
}

Краткое доказательство концепции ниже:

import scala.collection.immutable.SortedSet

case class Foo(a: Int, b: Int)

val fooOrdering: Ordering[Foo] = Ordering.by(_.b)
val ss = SortedSet(Foo(2, 2), Foo(2, 1), Foo(1, 2))(fooOrdering)
// ss: scala.collection.immutable.SortedSet[Foo] = TreeSet(Foo(2,1), Foo(1,2))

val fooOrdering: Ordering[Foo] = Ordering.by(foo => (foo.b, foo.a))
val ss = SortedSet(Foo(2, 2), Foo(2, 1), Foo(1, 2))(fooOrdering)
// ss: scala.collection.immutable.SortedSet[Foo] = TreeSet(Foo(1,2), Foo(2,1), Foo(2,2))

Answer 2

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

import collection.mutable.PriorityQueue
implicit val twoOrd = math.Ordering.by{ (t: (Int, Int)) => t._2 }
val p = new PriorityQueue[(Int, Int)]()(twoOrd)
p += ((1, 2))
p += ((42, 2))

Несмотря на то, что обе пары сопоставлены с 2 и, следовательно, имеют одинаковый приоритет, очередь не теряет никаких элементов:

p foreach println
(1,2)
(42,2)