nlib
succinct/bitvector/bitvector.cpp
This sample implements a compact integer list using SmartBitmap.
For example, a list or std::set can be used to create a set of IDs. The downsides of this approach include the relatively large memory footprint and the need for active memory management.
Bit vectors can be used to store the data more compactly if the maximum ID value is known. SmartBitmap allows the addition of a small amount of data to a bit vector to count or search data efficiently.
// Implements a list(set) of integers by SmartBitmap
class ItemList {
public:
static const size_t NUM_ITEM = 1024;
int GetNextItem(uint32_t n) const {
// Rank1(n) computes the count of '1' bits in [0, n].
// Select1(r) computes the index for the (r + 1)th '1' bit.
// you can compute the place of the net '1' bit.
return bitmap_.Select1(bitmap_.Rank1(n));
}
int GetPrevItem(uint32_t n) const {
unsigned int r = bitmap_.Rank1(n);
if (r == 0) return -1;
return bitmap_.Select1(r - 1);
}
size_t GetNumItems() const { return bitmap_.Rank1(NUM_ITEM); }
bool Find(uint32_t n) const { return bitmap_.Has(n); }
int FindNth(uint32_t nth) const { return bitmap_.Select1(nth); }
void Set(uint32_t n) { bitmap_.Set(n); }
void Unset(uint32_t n) { bitmap_.Unset(n); }
private:
SmartBitmap<NUM_ITEM> bitmap_;
};
bool SampleMain(int, char**) {
ItemList L;
// Set 0, 5, 10, 15, 20, ....., 995
for (int i = 0; i < 200; ++i) L.Set(i * 5);
// The size of SmartBitmap<NUM_ITEM> would be about (NUM_ITEM * 1.4 / 8) bytes.
// It is smaller than array or list.
nlib_printf("sizeof NumList: %" PRIuS "\n", sizeof(L));
// Gets the count of the numbers 'L' has. The time complexity is O(1).
nlib_printf(" %" PRIuS "\n", L.GetNumItems());
// Retrieves the 50th smallest value. The time complexity is Log(NUM_ITEM).
nlib_printf("50th value is %d\n", L.FindNth(50 - 1));
// The next value of 500 is 505.
nlib_printf("next(500) is %d\n", L.GetNextItem(500));
// Inserts 501 into L. The time complexity is O(1).
L.Set(501);
nlib_printf("501 inserted\n");
// The next value of 500 is 505 now.
nlib_printf("next(500) is %d\n", L.GetNextItem(500));
return true;
}
NLIB_MAINFUNC