roaring-rs
roaring-rs copied to clipboard
Implement SkipTo for iter::Iter
This is the start of the implementation of #286 .
It adds a new trait SkipTo which for now is only implemented for iter::Iter.
The SkipTo trait contains a method skip_to(&mut self, n:u32) which should return an Iterator that yields values >= n.
The implementation for iter::Iter achieves this by doing a binary search for the correct container, and then another binary search if the container is an ArrayStore, or forwarding like a normal BitmapIter until a suitable value is found for BitmapStore.
Right now SkipTo is implemented for iter::Iter, but I don't think this is semantically sound, and it should probably rather be implemented for RoaringBitmap. In the discussion for #286 @Kerollmops wanted a similar api to SkipWhile, but this does not really fit, as SkipWhile can perform it's operation only using an existing iterator, but this is not true for SkipTo, as it needs direct access to the containers to do it's skip efficiently, not only the existing iterator. A reference to the container vec has been added to iter::Iter only for this purpose. The iterator returned is fully independent, and not related to the iterator on which the skip_to call was made at all.
This PR in it's current state implements what I need for my project, but I would like to finish it, albeit at a slightly slower pace.