CODEWITHSUNDEEP
scala
schmmd
schmmd

Reputation: 19468

Require in an abstract class that subtypes are ordered

I am making a basic graph representation in Scala.

abstract class Vertex
class Edge (
  val source: Vertex
  val dest: Vertex
)
class Graph[V <: Vertex] {
  ...
}

At some point, I need to be able to sort a list of vertices in Graph[Vertex]. I would like to do so by calling vertices.sorted. If I make Vertex extend Ordered[Vertex] then I don't actually have the right compareTo since the ordering information is going to be data in the implemented subclass of Vertex and compareTo takes any Vertex. But if I make my Vertex implementation MyVertex extend Ordered[MyVertex], then that information is not available in Graph[MyVertex].

What is the best solution to this problem? Should I be using an implicit Ordering? Is there a way to enforce that subclasses of Vertex have an implicit Ordering on themselves?

I would rather not do the following:

class MyClass extends Vertex {
  override def compare(that: Vertex) = that match {
    case that: MyClass => // do the comparison
    case _ => false
  }
}

Update: maybe Graph's constructor needs to take an Ordering[V]?

Update: I could always restrict V <: Ordered[V] but this does not scale. Is it possible to have multiple type restrictions?

Upvotes: 0

Views: 212

Answers (3)

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297205

Why not just this?

class Graph[V <: Vertex with Ordered[V]]

Or you could go the way of Ordering too:

class Graph[V <: Vertex : Ordering]

Upvotes: 1

Bret
Bret

Reputation: 413

Why not design your Graph class to contain a List of Vertex objects? Then you can use List's handy built-in sortWith method.

For example:

class Graph(val Vertices:List[Vertex]) {
  def sorted():Graph = {
    new Graph(Vertices.sortWith((v1, v2) => { /* your comparison logic here */ }))
  }
}

Hope that points you in the right direction.

Upvotes: 0

Alexey Romanov
Alexey Romanov

Reputation: 170745

Update: maybe Graph's constructor needs to take an Ordering[V]?

That would be my preferred approach, because this way you may pass a different Ordering if needed.

Update: I could always restrict V <: Ordered[V] but this does not scale. Is it possible to have multiple type restrictions?

Yes, since Scala has intersection types: V <: Ordered[V] with Something[V] with SomethingElse[V].

Upvotes: 1

Related Questions