Define `impl Ord` at runtime

I am finding myself in a situation where I'd like to select one from among several impl Ord definitions at runtime, which I understand is not possible, and am wondering what the idiomatic approach would be to solving the actual problem: I'm implementing a best-first heuristic search algorithm for forward state-space search, and I want to be able to provide an arbitrary number of node prioritization schemes from which the user can select at runtime.

Approach Idea 1: instead of impl Ord on my search Node struct, parameterize the priority queue data structure with a comparator function fn(&Node, &Node) -> std::cmp::Ordering, and define such a function for each prioritization scheme.

Approach Idea 2: define separate wrappers NodeA, NodeB, etc., each with corresponding impl Ord, for each prioritization scheme.

Pros/cons of each approach? Suggestions for other approaches? Mistakes in thinking/gaps in understanding?

1 is good, and you can do that with binary_heap_plus - Rust but note that performance won't be as good as having monomorphized binary heaps for each comparator. If comparisons will be infrequent, then this'll be fine.

2 is just as hard as making monomorphized binary heaps, and the latter is probably less complicated as far as the generics go. I'd suggest something like:

fn with_compare<T, C: Compare<T>>(data: Vec<T>, cmp: C) {
    let mut heap = BinaryHeap::from_vec_cmp(data, cmp);
    todo!();
}

fn main() {
    // read user input to determine comparator
    let cmp_str = "rev";
    let data = vec![1, 2, 3];
    
    match cmp_str {
        "normal" => with_compare(data, |a, b| a.cmp(b)),
        "rev" => with_compare(data, |a, b| b.cmp(a)),
        "none" => with_compare(data, |_, _| Ordering::Equal),
    }
}
1 Like