CODEWITHSUNDEEP
scalafunctional-programmingsetsortedset
UtheMan
UtheMan

Reputation: 41

Scala - how to make the SortedSet with custom ordering hold multiple different objects that have the same value by which we sort?

as mentioned in the title I have a SortedSet with custom ordering. The set holds objects of class Edge (representing an edge in a graph). Each Edge has a cost associated with it as well as it's start and end point.

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

My ordering for SortedSet of edges looks like this (it's for the A* algorithm) : 

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

}

However after I apply said ordering to the set and I try to sort edges that have different start/end points but the same cost - only the last encountered edge retains in the set.

For example : 

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

Only prints (3,2,2)

Aren't these distinct objects? They only share the same value for one field so shouldn't the Set be able to handle this?

Upvotes: 2

Views: 1458

Answers (2)

Leo C
Leo C

Reputation: 22449

To retain all the distinct Edges with the same ordering cost value in the SortedSet, you can modify your Ordering.by's function to return a Tuple that includes the edge Ids as well:

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

A quick proof of concept below:

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

Upvotes: 1

Andrey Tyukin
Andrey Tyukin

Reputation: 44937

Consider using a mutable.PriorityQueue instead, it can keep multiple elements that have the same order. Here is a simpler example where we order pairs by the second component:

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

Even though both pairs are mapped to 2, and therefore have the same priority, the queue does not lose any elements:

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

Upvotes: 1

Related Questions