I have a backwards compatible proposal that I think would be similar to the way sort already works. There are currently 4 methods that create a BinaryHeap. These are new, with_capacity, from, and into. I propose that we change the definition of a BinaryHeap to:
struct BinaryHeap<T, C>
where
C: FnMut(&T, &T) -> Ordering,
{
data: Vec<T>,
cmp: C,
}
Here we use FnMut as it gives the greatest flexibility. If C does not capture any variables it would be a zero sized type. The current heaps are an example of this. Similar to sort, sort_by, and sort_by_key we define:
impl<T> BinaryHeap<T, fn(&T, &T) -> Ordering> {
pub fn new() -> BinaryHeap<T, Max<T>>
where
T: Ord,
{
BinaryHeap {
data: Vec::new(),
cmp: Max::new(),
}
}
pub fn new_by<C>(cmp: C) -> BinaryHeap<T, C>
where
C: FnMut(&T, &T) -> Ordering,
{
BinaryHeap {
data: Vec::new(),
cmp,
}
}
pub fn new_by_key<K, F>(mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
where
K: Ord,
F: FnMut(&T) -> K,
{
BinaryHeap {
data: Vec::new(),
cmp: move |x, y| K::cmp(&f(x), &f(y)),
}
}
}
We use fn(&T, &T) -> Ordering to have a concrete type to define these methods on. The type is not important here, the only thing we care about is that it implements FnMut(&T, &T) -> Ordering. We implement
-
with_capacity,
-
with_capacity_by,
-
with_capacity_by_key,
-
from,
-
from_by,
from_by_key
in similar ways. The From trait is only implemented for Vec so we can easily generalise it this way. I propose that we keep this trait implementation and define the other two functions as methods. The only function we can not easily generalize this way is into. For this we would have to define methods on Vec and I am not sure that would be worth it.
We could use new() -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering> instead of new() -> BinaryHeap<T, Max<T>> and do the same for from, and with_capacity.
However this would mean that the compiler would think that these three functions don’t return the same type.
This would be a breaking change as these functions currently do return the same type. So I propose we make a new struct:
#![feature(fn_traits, unboxed_closures)]
struct Max<T: Ord>(PhantomData<fn(&T, &T) -> Ordering>);
impl<T: Ord> Max<T> {
pub fn new() -> Max<T> {
Max(PhantomData)
}
}
impl<'a, 'b, T: Ord> FnOnce<(&'a T, &'b T)> for Max<T> {
type Output = Ordering;
extern "rust-call" fn call_once(self, args: (&'a T, &'b T)) -> Ordering {
T::cmp(args.0, args.1)
}
}
impl<'a, 'b, T: Ord> FnMut<(&'a T, &'b T)> for Max<T> {
extern "rust-call" fn call_mut(&mut self, args: (&'a T, &'b T)) -> Ordering {
T::cmp(args.0, args.1)
}
}
impl<'a, 'b, T: Ord> Fn<(&'a T, &'b T)> for Max<T> {
extern "rust-call" fn call(&self, args: (&'a T, &'b T)) -> Ordering {
T::cmp(args.0, args.1)
}
}
What is currelty BinaryHeap<T> would become BinaryHeap<T, Max<T>>. We can define Min<T> in a similar way. You can create a max heap by calling new() or new_by(Max::new()), a min heap can be ceated by calling new_by(Min::new()). This would be simalar to sorting as one can now sort a slice increasingly by calling sort() or sort_by(Max::new()) and decreasingly by calling sort_by(Min::new()).
