Question: Isn't this possible without a full code-port?

[ripytide]

Hi there, cool work!

I found this crate from your stack overflow comment here while looking for more flexible ways of imposing custom orderings inside BTreeMaps. I need such flexibility for the range_bounds_map crate I maintain. Specifically ripytide/nodit#21

My Question:

Is this not already possible without a full code-port by simply wrapping the BTreeMap in a new struct and then translating the types you get given into a newtype struct that dynamically applies the specified TotalOrder?

Something like:

struct CustomOrdApplicator<T, O> { inner: T, total_order: O }

impl Ord for CustomOrdApplicator {
   fn cmp(self, other) {
       self.total_order.cmp(self, other)
   }
}

Apologies if I have misunderstood something.

[eggyal]

The problem with newtyping the contained values so that they each hold runtime state required for ordering is that such state must be duplicated across every element in the collection. This has both time and space costs that can be avoided if that state is stored only once per collection.

[ripytide]

If I understand correctly, could you not then get around large total_orders by storing a Rc<impl TotalOrded> instead and storing the TotalOrder just the once in the BTreeMap Wrapper? Since there is only one impl TotalOrder per BTreeMap?

[eggyal]

Sure, but that still stores an additional pointer per element and suffers the cost of indirection to reach the ordering (in addition to the cost of the Rc's, or Arc's if multithreaded, alloc + refcounting).

[eggyal]

Also, your CustomOrdApplicator implementation above assumes that self and other have the same total_order. Perhaps if the library is carefully written, that assumption can be ensured, but to be strictly correct cmp should compare the total_order of the two arguments... and, if they differ, I guess its only option would be to panic? That would add additional cost too.

The outer wrapper type would furthermore have to do translation to/from the stored newtyped keys, which also adds further cost.

[ripytide]

That makes sense. For sure it would be a sub-optimal solution.