RoaringBitmap / RoaringBitmap/CRoaring

Feature request: intersection, union, and difference with the tail of another bitmap

Open
#591 4 comments 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.