Add custom comparators

[matthew-mcallister]

Closes https://github.com/crossbeam-rs/crossbeam/issues/1180.

The diff is large due to having to add a type parameter C and update constraints in numerous places, but the logic changes are not large.

This trait adds the Comparator and Equivalator traits, which generalize the Comparable and Equivalent traits by taking a self parameter in addition to the two keys to compare, making it possible to change the comparison function used without changing the key type.

Summary

• Adds trait Comparator<L, R> and trait Equivalator<L, R>.
• Adds struct BasicComparator, which is a zero-sized type that implements Comparator using the Comparable trait, which itself falls back on Borrow and Ord.
• Adds a type parameter C to SkipList, SkipMap, and SkipSet.
  • C is defaulted to OrdComparator. This preserves the existing behavior of functions like get(), insert(), etc.
• Adds SkipList::with_comparator(), SkipSet::with_comparator(), and SkipMap::with_comparator() constructors.
  • SkipList::new(), SkipMap::new(), and SkipSet::new() always use C = OrdComparator. It would be nice if it worked for any C that implements Default, but that would break type inference. This is exactly the reason std::collections::HashMap::new() always uses S = RandomState for its defaulted parameter even if S implements Default.
• Adds a test using a wrapper around Box<dyn Fn(&[u8], &[u8]) -> Ordering> as the comparator.

Hashing

Because the goal of these traits is to support totally different comparison operations from the default for the underlying key type, Equivalator explicitly does not require two equivalent keys to have the same hash. If someone, someday wants to support Equivalator on their hash map, they will have to generalize the Hash trait as well.

Safety

My one minor question is whether unsafe impl<Q, R, K, V, C> Send for RefRange<'_, Q, R, K, V, C> should require C: Sync. I don't think so because it doesn't require K or V to be sync, but it was enough to make me second-guess myself.

[taiki-e]

cc @al8n

[matthew-mcallister]

Restored the Equivalent and Comparable traits. Now there is no change in behavior compared to master unless you explicitly define your own comparator type.

[matthew-mcallister]

It's been a while since I circled back to this, but is there a sentiment as to whether to merge?

[matthew-mcallister]

Sorry it took me an eternity to circle back round to this. I got busy and I'm bad at multitasking.

I pushed a commit that addresses the last round of feedback with respect to comments and tests/examples. Are there any maintainers that want to provide feedback and give a disposition as to whether there is a desire to merge this? Or whether we should perhaps take a different approach, such as spinning out the traits into a new crate and adding a hashing trait for DB folks who want to support this with their Bloom filters?