How to define an ordered Map/Set with a runtime-defined comparator?

Question

This is similar to How do I use a custom comparator function with BTreeSet? however in my case I won't know the sorting criteria until runtime. The possible criteria are extensive and can't be hard-coded (think something like sort by distance to target or sort by specific bytes in a payload or combination thereof). The sorting criteria won't change after the map/set is created.

The only alternatives I see are:

• use a Vec, but log(n) inserts and deletes are crucial
• wrap each of the elements with the sorting criteria (directly or indirectly), but that seems wasteful

This is possible with standard C++ containers std::map/std::set but doesn't seem possible with Rust's BTreeMap/BTreeSet. Is there an alternative in the standard library or in another crate that can do this? Or will I have to implement this myself?

---

My use-case is a database-like system where elements in the set are defined by a schema, like:

Element {
    FIELD x: f32
    FIELD y: f32
    FIELD z: i64

    ORDERBY z
}

But since the schema is user-defined at runtime, the elements are stored in a set of bytes (BTreeSet<Vec<u8>>). Likewise the order of the elements is user-defined. So the comparator I would give to BTreeSet would look like |a, b| schema.cmp(a, b). Hard-coded, the above example may look something like:

fn cmp(a: &Vec<u8>, b: &Vec<u8>) -> Ordering {
    let a_field = self.get_field(a, 2).as_i64();
    let b_field = self.get_field(b, 2).as_i64();
    a_field.cmp(b_field)
}

Answer 1

There is the copse¹ crate written by @eggyal which provides BTreeSet, BTreeMap, and BinaryHeap types mimicking the standard library but which allow a ordering to be specified separately.

Here is an example BTreeSet of Points that are ordered by a distance to a fixed point:

use copse::{BTreeSet, SortableBy, TotalOrder};

struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn distance(&self, other: &Point) -> f64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx * dx + dy * dy).sqrt()
    }
}

struct PointTotalOrder(Point);

impl TotalOrder for PointTotalOrder {
    type OrderedType = Point;

    fn cmp(&self, this: &Point, that: &Point) -> std::cmp::Ordering {
        let this_dist = self.0.distance(this);
        let that_dist = self.0.distance(that);
        f64::total_cmp(&this_dist, &that_dist)
    }
}

impl SortableBy<PointTotalOrder> for Point {
    fn sort_key(&self) -> &Point {
        self
    }
}

fn main() {
    let fixed = Point { x: 2.0, y: 3.0 };

    let mut set = BTreeSet::new(PointTotalOrder(fixed));
    set.insert(Point { x: 0.0, y: 0.0 });
    set.insert(Point { x: 3.0, y: 3.0 });
    set.insert(Point { x: 2.0, y: 5.0 });

    for point in set {
        println!("({}, {})", point.x, point.y);
    }
}

(3, 3)
(2, 5)
(0, 0)

^{1. "Copse" is a word meaning "a small group of trees" which I find very fitting.}

Answer 2

Would it be possible to pass the comparator closure as an argument to each node operation that needs it? It would be owned by the tree wrapper instead of cloned in every node.