billyrieger/bimap-rs

True generic bimaps

Opened this issue · 0 comments

Using generic associated types it's possible to create a fully generic bimap where the left and right map types can be specified independently. Inner maps would be constrained by a Map trait and a bimap would become generic over the map types instead of the value types. In addition to reducing the code duplication between BiHashMap<L, R> and BiBTreeMap<L, R> that exists currently, this would also allow library users to develop custom maps to be used in a bimap if the Map trait is public. GATs are necessary due to the lifetime requirements of the Iter associated type.

// before
struct BiHashMap<L, R> { ... }
struct BiBTreeMap<L, R> { ... }
// after
struct BiMap<LMap, RMap> { ... }

impl<L, R, LMap, RMap> BiMap<LMap, RMap>
where
    LMap: Map<Key = L, Value = R>,
    RMap: Map<Key = R, Value = L>,
{
    ...
}

trait Map {
    type Key;
    type Value;
    type Iter<'a, K, V>: Iterator<Item = (&'a K, &'a V)>;
    ...
}

Implementing this will be a large breaking change. For now, work in progress is happening on the nightly branch.