Scala - 如何使具有自定义排序的 SortedSet 包含多个不同的对象，这些对象具有我们排序的相同值?

Question

如标题中所述，我有一个具有自定义排序的SortedSet。该集合包含类 Edge 的对象(表示图形中的边缘(。每个 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

考虑改用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)

Answer 2

要在SortedSet中保留所有具有相同排序成本值的不同Edge，您可以修改Ordering.by的函数以返回一个包含边缘 ID 的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))