Type parameter T bounded by Ordering[T]

Question

When implementing a sortable data structure, I was thinking of doing something like this:

trait MaxHeap[T <: Ordering[T]] {
    def insert(e: T): Unit
    ...
}

But that wouldn't work for types like MaxHeap[Int]. In standard collection library, the element type T of a collection is not bounded. Instead, an implicit is provided for methods need it to convert T to Ordering[T], e.g.

trait Seq[+A] extends ... {
    // it's Ordering[B], not Ordering[A], but the idea is the same.
    def max[B >: A](implicit cmp: Ordering[B]): A
}

My question is, if there are many methods in my class/trait involving comparison, is there a way to specify class/trait's element type to be comparable so that I don't need to declare implicits for those methods?

Answer 1

You could declare an implicit parameter that defines the ordering, and then you can use it in all your methods:

class MaxHeap[T](implicit cmp: Ordering[_ >: T]) ...

---

If it's a trait, it can't take a parameter, but you can declare it as an implicit value:

trait Heap[T] {
  implicit protected val cmp: Ordering[_ >: T];
  // ... use cmp in your methods ...
}

and then each class that uses it can take an implicit parameter that overrides it:

class MaxHeap[T](implicit override protected val cmp: Ordering[_ >: T])
  extends Heap[T]
{
  // ...
}

---

Update: For some technical reasons Ordering isn't contravariant. This is why I used Ordering[_ >: T], because it allows greater flexibility. You can use an ordering that is defined for a superclass of T. You can of course use just cmp: Ordering[T], but then you can't do things like

new MaxHeap[java.lang.Integer]()(new Ordering[java.lang.Number] {
    // ...
  });

Also, the whole idea of Ordering is that you don't have to impose any constraints on T. This is more flexible and among other things allows to have different comparisons for the same class.