I did some refactoring and honestly code is not that bad, could be deduplicated in some places but other than that its okay. Needed to fix some structure visibility setting in one place and reimagine how one interface should work, but i am satisfied with the results for now. It is possible i will change internal API design in the future, but public API should slowly approach stability (especially since i am copying BTreeMap in most cases anyways lol).
In other news, i learned how to do those automatic docs for Rust using doc comments :) they look so fancyyyy just like std docs.
Lastly, there is a very funny trick using zero-sized types in Rust. A Map is a data structure which maps every key to one value uniquely, and then a Set is a data structure which keeps track of unique values efficiently. Since both keep track of uniqueness of keys, they may often be implemented using similar algorithms underneath.
With zero-sized types (ZSTs) in Rust, it is even possible to very easily implement a Set using a Map. Given a Map defined as Map<K: Ord, V> with keys of type K and values of type V, it is possible to fully define a Set by basically making a Set into a Map for which V is a ZST.
In fact, this is how it is done in std library. For instance, BTreeSet contains a BTreeMap with value type V set to an empty struct (zero-sized type):
All it does is relay methods to the underlying map + apply some glue inbetween. For instance, insert() and remove() on a Map return Option<> and Set's insert() and remove() should return a boolean. This can be easily converted using is_none() and is_some():
From what i've read, compiler is smart enough to optimize away all the ZST code (since many operations on ZSTs are no-ops), so there's no added complexity while at the same time code reuse is great and very intuitive :) very cool!
















