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.
/*--------------------------------------------------------------------------------*
Project: CrossRoad
Copyright (C)Nintendo All rights reserved.
These coded instructions, statements, and computer programs contain proprietary
information of Nintendo and/or its licensed developers and are protected by
national and international copyright laws. They may not be disclosed to third
parties or copied or duplicated in any form, in whole or in part, without the
prior written consent of Nintendo.
The content herein is highly confidential and should be handled accordingly.
*--------------------------------------------------------------------------------*/
// Implements a list(set) of integers by SmartBitmap
class ItemList {
public:
static const size_t kNumItem = 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(kNumItem); }
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<kNumItem> bitmap_;
};
bool SampleMain(int, char**) {
ItemList item_list;
// Set 0, 5, 10, 15, 20, ....., 995
for (int i = 0; i < 200; ++i) item_list.Set(i * 5);
// The size of SmartBitmap<kNumItem> would be about (kNumItem * 1.4 / 8) bytes.
// It is smaller than array or list.
nlib_printf("sizeof NumList: %" PRIuS "\n", sizeof(item_list));
// Gets the count of the numbers 'item_list' has. The time complexity is O(1).
nlib_printf(" %" PRIuS "\n", item_list.GetNumItems());
// Retrieves the 50th smallest value. The time complexity is Log(kNumItem).
nlib_printf("50th value is %d\n", item_list.FindNth(50 - 1));
// The next value of 500 is 505.
nlib_printf("next(500) is %d\n", item_list.GetNextItem(500));
// Inserts 501 into item_list. The time complexity is O(1).
item_list.Set(501);
nlib_printf("501 inserted\n");
// The next value of 500 is 505 now.
nlib_printf("next(500) is %d\n", item_list.GetNextItem(500));
return true;
}
NLIB_MAINFUNC