How to use a BinaryHeap when I can't implement Ord?

Question

I have a the following Rust trait:

trait Task {
    fn time(&self) -> std::time::Duration;
    fn run(self);
}

I need to keep instances of T: Task in some kind of sorted list where I can pop the one with the lowest value for time(). My plan was to use a BinaryHeap:

fn foo<T: Task>(task: T) {
    let heap = std::collections::BinaryHeap::new();
    heap.push(task);
}

However, I run into trouble here. To put something in a BinaryHeap, it has to implement Ord:

error[E0277]: the trait bound `T: std::cmp::Ord` is not satisfied
 --> src/lib.rs:7:16
  |
7 |     let heap = std::collections::BinaryHeap::new();
  |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::cmp::Ord` is not implemented for `T`
  |
  = help: consider adding a `where T: std::cmp::Ord` bound
  = note: required by `std::collections::BinaryHeap::<T>::new`

I can't implement Ord for Task since Ord is not from my crate. And I wouldn't want to either, since implementors of Task might want to have some other implementation for Ord.

So waht do I do? Is there some other kind of sorted list I can use? Or can I trick BinaryHeap into using other sorting rules?

Answer 1

If you want to have multiple types of Tasks in the same BinaryHeap (at the same time), you're going to need to use a boxed trait object, or some other kind of (smart) pointer. So you should implement Ord on the type Box<dyn Task>. See below if you really are just using one type of task at a time.

use std::cmp::Ordering;
use std::collections::BinaryHeap;

trait Task {
    fn time(&self) -> std::time::Duration;
    fn run(self);
}


impl PartialEq for Box<dyn Task> {
    fn eq(&self, other: &Self) -> bool {
        self.time() == other.time()
    }
}

impl Eq for Box<dyn Task> {}

impl PartialOrd for Box<dyn Task> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other)) // Delegate to the implementation in `Ord`.
    }
}

impl Ord for Box<dyn Task> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.time().cmp(&other.time())
    }
}

Then when you insert a Task into the BinaryHeap, you'll need to box it with Box::new or something equivalent. Since this Box<dyn Task> may outlive any references in T, you'll have to ensure that T contains at most 'static references by adding 'static to the bounds on T.

fn foo<T: Task + 'static>(task: T) {
    let mut heap = BinaryHeap::new();

    let boxed_task: Box<dyn Task> = Box::new(task);
    heap.push(boxed_task);
}

Just a side note: you could also implement Ord (and the rest) on dyn Task. Then you would get an implementation of Ord for Box<dyn Task> for free since Box<T> implements Ord if T does. This could be useful if you're using multiple pointer types other than Box<T> with Tasks, like Rc<dyn Task> or &dyn Task.

---

If you really are just using one type at a time, then you could use a wrapper type that implements Ord. This looks like what you're doing right now since you only create the BinaryHeap once you have a specific task in hand. I don't think this is what you want, but here it is anyway.

use std::cmp::Ordering;
use std::collections::BinaryHeap;

trait Task {
    fn time(&self) -> std::time::Duration;
    fn run(self);
}

struct TaskWrapper<T: Task>(T);

impl<T: Task> PartialEq for TaskWrapper<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.time() == other.0.time()
    }
}

impl<T: Task> Eq for TaskWrapper<T> {}

impl<T: Task> Ord for TaskWrapper<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.time().cmp(&other.0.time())
    }
}

impl<T: Task> PartialOrd for TaskWrapper<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

With this approach, if task: T and T implements Task, you can insert task into the BinaryHeap by wrapping it like TaskWrapper(task).

fn foo<T: Task>(task: T) {
    let mut heap = BinaryHeap::new();
    heap.push(TaskWrapper(task));
}

---

Just one more thing. It's a logic error for the relative ordering of members of a BinaryHeap to change. Since our ordering here is based entirely off of the method time, the ordering might change every time time is called. So even in this situation, we have to depend on the correctness external implementation of time. You wanted to avoid using the trait bound T: Ord for exactly this reason, so bear this in mind.