search

RoaringBitmap / roaring-rs

A better compressed bitset in Rust
https://docs.rs/roaring/
Apache License 2.0
757 stars 84 forks source link

Override default `fold` and `rfold` implementations for the iterators #277

Closed oskgo closed 5 months ago

oskgo commented 5 months ago

fold and rfold are APIs for internal iteration, which is sometimes more efficient than external iteration (next and next_back). It is always possible to implement internal iteration in terms of external, which is what the default impl does, but this implementation need not be optimal. Flatten (which roaring uses) has more efficient fold and rfold implementations than the default. Roaring should use the implementations from Flatten rather than the default implementations.

Ideally you would implement try_fold and try_rfold as well, but they cannot be implemented until the Try trait is stabilized (https://github.com/rust-lang/rust/issues/84277).

This might apply to other default implementations overridden by Flatten as well.

Kerollmops commented 5 months ago

Hey @oskgo 👋

Thank you for the information and proposal. It is very interesting. Would you mind doing a PR or something at some point? Or is it more like a tracking issue?

oskgo commented 5 months ago

You seem to be fine with the change I'm proposing, so I can write up a PR.

It might make sense to have a tracking issue if it can be set up to be notified when Try stabilizes, but I don't know how to set that up.