Using generic data structures with generic reference types

[cp289]

I'm trying to write a small library of generic data structures and algorithms in a way I hope to be as high-level/implementation-agnostic as possible. My reasoning: the less I constrain the implementations, the more reusable the code + test-cases, and the less code I need to change if I need to micro-optimize in the future.

I've been trying to use Rust's type system to my advantage here. Some examples of the traits I'm considering:

• Map<K, V>: Maps keys of type K to values of type V (a HashMap<K, V> would trivially implement this trait)
• Set<T>: An unordered collection of values of type T (a HashSet<T> would trivially implement this trait)

The interesting part comes down to references. For example, what should the type signature be for Map::get()? (I'm ignoring the self argument for now.)

• For HashMap<K, V>: Map<K, V> it's usually fn(&K) -> &V
• For Vec<T>: Map<usize, T> it could be fn(&usize) -> &T or fn(usize) -> &T
• For a bitmap type, e.g. BitMap: Map<usize, bool>, it really should be fn(usize) -> bool (fn(&usize) -> bool might work too), but fn(usize) -> &bool is too constraining since an efficient implementation usually uses something like Vec<u32> internally and thus can't return a &bool.

My solution here is to parameterize the reference types. For example the Map trait now becomes:

• Map<K, V, KRef, VRef>: Data structure mapping Ks to Vs whose keys are referenced by KRef and whose values are referenced by VRef.
• Map::get() now has signature fn(KRef) -> VRef and can be used for all scenarios described above. And as a bonus, a single data structure can implement multiple parameterizations of Map depending on the usage context.

Of course, now there's the issue of lifetimes. In the case of Map I arrived at this solution:

• Map<'v, K, V, KRef, VRef> where 'v denotes the lifetime of VRef
• Map::get() has signature fn<'s>(KRef) -> VRef where 's: 'v.
• An implementation requiring VRef=&V would need to implement Map<'v, K, V, KRef, &'v V>.

This approach seems to work most of the time, although it does feel slightly hacky.

Here's my best attempt at implementing a generic unit test to the Set trait (this unfortunately fails with 2 lifetime errors): Rust Playground

Am I going down the right path here? Is there a better way to achieve the generality + flexibility I'm looking for that satisfies the borrow checker? Hoping I'm overlooking something simple here, e.g. perhaps my testing strategy is flawed more than anything else.

[ProgramCrafter]

At the next step you'll run into problems with .get_mut. On bitset, whatever type is returned, it must call a method to write new bit; other maps might return just mutable references.

[cp289]

Good point, thankfully get_mut() for Map<'_, K, V, KRef, VRef> wasn't too hard to solve. The trick is to create a method called map_mut() instead:

/// Returns result of `f` applied to a mutable reference of value specified by `key` if it exists.
fn map_mut<T>(&mut self, key: KRef, f: impl FnMut(&mut V) -> T) -> Option<T>;

This allows a BitMap implementation to handle mutations by sharing a mutable reference to a stack variable and updating the data structure appropriately like so:

fn map_mut<T>(&mut self, key: usize, mut f: impl FnMut(&mut bool) -> T) -> Option<T> {
    if let Some(v) = self.get(key) {
        let mut local_copy_of_v = *v;
        let ret = f(&mut local_copy_of_v);
        self.insert(key, local_copy_of_v);
        Some(ret)
    } else {
        None
    }
}