grelner
commented
2 months ago Hi sorry for the slow progress, I've been on vacation too. I've pushed some changes and I think it's ready for review now. This implements:
- advance_to for Iter and IntoIter, which skips containers using the value key. This uses an existing iterator for data
- Bitmap::iter_from, which is faster that advance_to, because it does a binary search to find the container to start from This change significantly changes the iterator implementations, which now implement their own flatten functionality.
Kerollmops
This is the start of the implementation of #286 . It adds a new trait
SkipTowhich for now is only implemented for iter::Iter.The
SkipTotrait contains a methodskip_to(&mut self, n:u32)which should return anIteratorthat yields values >=n. The implementation foriter::Iterachieves this by doing a binary search for the correct container, and then another binary search if the container is anArrayStore, or forwarding like a normalBitmapIteruntil a suitable value is found forBitmapStore.Right now
SkipTois implemented foriter::Iter, but I don't think this is semantically sound, and it should probably rather be implemented forRoaringBitmap. In the discussion for #286 @Kerollmops wanted a similar api toSkipWhile, but this does not really fit, asSkipWhilecan perform it's operation only using an existing iterator, but this is not true forSkipTo, 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 toiter::Iteronly for this purpose. Theiteratorreturned is fully independent, and not related to the iterator on which theskip_tocall 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.