Iterate over bit ranges

[rogpeppe]

Sometimes we want to find the ranges of 1 bits, and there's no obviously efficient way to do that currently. (Maybe I'm missing something!).

If #22 was implemented, then we could do it without allocation, but currently the only way I can think of doing it with reasonable efficiency (avoiding O(nbits) complexity I think) is by using Flip and two iterators.

Providing a way to iterator over the unset bits or providing a way to iterate over the bit-ranges would make this more efficient and/or convenient.

Something like this, perhaps:

// Ranges returns an iterator over all the [start, end)
// ranges of 1-bits in b.
func (b *Bitmap) Ranges() iter.Seq2[uint64, uint64]

Given that, it's trivial to write a function to iterate over the inverted bits.

PoC of the range functions using Flip: https://go.dev/play/p/Ss3T8NCDdJ0

[lemire]

I have a PR for unset iterators: https://github.com/RoaringBitmap/roaring/pull/492

[lemire]

Sometimes we want to find the ranges of 1 bits, and there's no obviously efficient way to do that currently. (...) If https://github.com/RoaringBitmap/roaring/issues/22 was implemented, then we could do it...

I am fixing 22 right now.