4 ms·

I haven't tried roaring bitmaps on this problem yet. I think it's generally fairly dense so that's why I tried dense bitsets first, but it's a fair point. It mi

I haven't tried roaring bitmaps on this problem yet. I think it's generally fairly dense so that's why I tried dense bitsets first, but it's a fair point. It might still be beneficial to go with a sparse representation depending on the interval lengths for example. I also didn't have a good way to measure runs from roaring bitmap's Rust API (https://github.com/RoaringBitmap/roaring-rs/issues/274 https://github.com/RoaringBitmap/roaring-rs/issues/274) which makes it hard to track interval duration, but would be interested to compare this approach.

quadrature 2y ago
Thats fair, the rust port isn't as feature rich as the original Java library. The Java version has methods for previous/next absent value which i think would solve your issue ?. The method is implemented using count trailing zeros intrinsic in the dense container so it is very performant for dense bitmaps https://github.com/RoaringBitmap/RoaringBitmap/blob/d2c6c3bcb087bc4d7785c05b37bf1240b99efd1e/RoaringBitmap/src/main/java/org/roaringbitmap/BitmapContainer.java#L981 https://github.com/RoaringBitmap/RoaringBitmap/blob/d2c6c3bc... Maybe this can be ported to the rust lib as well.