Feature: expose consecutive runs

[ranfdev]

roaring.consecutive(bit: 0, range: 13..) could return the number of consecutive zeroes from bit 13.

[Kerollmops]

Hey @ranfdev 👋

Roaring bitmaps are not necessarily "bitmaps" but are optimized to not be too big for some cases. What you seem to want is to know the number of missing values in a certain range. You can probably use the range_cardinality(&self, range: impl Range) -> u64 function and substract this number from the range size itself.

[ranfdev]

Thanks, but unfortunately range_cardinality doesn't cover my use case.

That's because range_cardinality returns the count of ones or zeros even if they aren't consecutive.

The function Roaring::consecutive(&self, bit, range) would stop counting after finding the first bitflip.

I know roaring bitmaps may be stored compressed with run length encoding. In fact, consecutive could take advantage of this compression to execute faster.

If the roaring bitmap contains RLE compressed ones as (start, count), and the user asks for consecutive(1, start..) the query can return instantly with value count.

I think this should be implemented inside the library, because as a user I don't have access to the internal representation of the bitmap, so I cannot optimize the query.

[Kerollmops]

That's because range_cardinality returns the count of ones or zeros even if they aren't consecutive.

Ho! I see. That's indeed not the same.

I think this should be implemented inside the library, because as a user I don't have access to the internal representation of the bitmap, so I cannot optimize the query.

For now you could try implementing this outside of the library by using the iterator. But happy to review a PR if you think performances matter.

[Dr-Emann]

I believe consecutive zeros can be gotten optimally with something like:

let bitmap = RoaringBitmap::from([0, 1, 12, 20]);
let mut iter = bitmap.range(13..);
let next_set_bit = iter.next().unwrap_or(u32::MAX);
let consecutive_zeros = next_set_bit - 13;
assert_eq!(consecutive_zeros, 7);

There's not (currently) an efficient way to get the number of consecutive ones (which could be done more efficiently than iterating over each item for range containers especially, but also bitmap containers).

[Dr-Emann]

With #338, I believe you can (a little indirectly) get this information efficiently:
roaring.consecutive(bit: 0, range: 13..) becomes:

let iter = bitmap.range(13..);
let next_range = iter.next_range();
let consecutive_zeros = next_range.map_or(u32::MAX, |r| *r.start()) - 13;

And looking for consecutive ones should look like:

let iter = bitmap.range(13..);
let next_range = iter.next_range();
let consecutive_ones = next_range.filter(|r| *r.start() == 13).map_or(0, |r| r.end() - 13 + 1);