Type parameter T bounded by Ordering[T]

implicit, scala

Solution

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.

Problem

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?

Original source