RoaringBitmap / RoaringBitmap/CRoaring
Feature request: intersection, union, and difference with the tail of another bitmap
Nobody has claimed this yet.
- Dominant language
- C
- Stars
- 1.9k
- Forks
- 334
- Avg merge
- 2d 5h
- Merged PRs (30d)
- 17
Description
I have two bitmaps a and b, I find one point inside b (say using an iterator), and then I want to intersect / union / compute the set difference of a with the tail of b after that point.
That is, I'd like the equivalent of
b.removeRange(0, x);
a &= b;
without the overhead of mutating b (the memmove from array containers shows up meaningfully in my CPU profile).
Roaring iterators already have all the information needed to implement this efficiently, and I sometimes need to walk through a to find the right spot (it's not as easy as rank(x)) so I'd prefer this:
auto it = b.begin();
it.move(x);
a.intersectTail(it);
// intersectRange(it, b.end()) would be nice too, but that means you have to be able to
// deal with partial containers at both ends instead of just at the beginning so it's a bit
// harder to implement
Do you think this is worth implementing?
Thanks,
-Tudor.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reviewing the existing bitmap iterator and set-operation APIs mentioned in the issue, including begin(), move(), end(), removeRange(), intersection, union, and difference. Determine the intended behavior for applying an operation with the tail beginning at an iterator position, then add coverage showing that the operation matches removing the prefix from b without mutating b.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- data, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100