16 #ifndef INCLUDE_NN_NLIB_SMARTBITMAP_H_ 17 #define INCLUDE_NN_NLIB_SMARTBITMAP_H_ 26 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int word_count,
const uint32_t* bv,
28 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int word_count,
const uint64_t* bv,
31 NLIB_VIS_PUBLIC unsigned int CalcRank1(
unsigned int pos,
const uint32_t* bv,
const uint32_t* lv_a,
33 NLIB_VIS_PUBLIC unsigned int CalcRank1(
unsigned int pos,
const uint64_t* bv,
const uint32_t* lv_a,
39 NLIB_VIS_PUBLIC int CalcSelect1(
unsigned int nth,
unsigned int size,
const uint32_t* bv,
41 NLIB_VIS_PUBLIC int CalcSelect1(
unsigned int nth,
unsigned int size,
const uint64_t* bv,
44 NLIB_VIS_PUBLIC int CalcSelect0(
unsigned int nth,
unsigned int size,
const uint32_t* bv,
46 NLIB_VIS_PUBLIC int CalcSelect0(
unsigned int nth,
unsigned int size,
const uint64_t* bv,
51 template <
size_t N,
class Derived,
class BIT>
55 BLK_SIZE = 8 *
sizeof(BIT),
56 WORD_COUNT = (N + BLK_SIZE - 1) / BLK_SIZE,
57 LV_A_COUNT = (N + 256 - 1) / 256,
58 LV_B_COUNT = ((N + BLK_SIZE - 1) / BLK_SIZE + 3) & ~0x3
66 NLIB_ASSERT(This()->bitmap_);
67 if (is_dirty_) this->Build();
68 if (idx >= N)
return false;
69 unsigned int blk = idx / BLK_SIZE;
70 unsigned int ofs = idx % BLK_SIZE;
71 return 0 != (This()->bitmap_[blk] & (
static_cast<BIT
>(1) << ofs));
75 if (is_dirty_) this->Build();
76 unsigned int pos = idx < N ? idx : N - 1;
77 return detail::CalcRank1(pos, This()->bitmap_, lv_a_, lv_b_);
80 unsigned int rank1 = this->Rank1(idx);
81 return idx + 1 - rank1;
84 NLIB_ASSERT(This()->bitmap_);
85 if (nth >= this->Rank1(N - 1))
return -1;
86 return detail::CalcSelect1(nth, N, This()->bitmap_, lv_a_, lv_b_);
89 NLIB_ASSERT(This()->bitmap_);
90 if (nth >= this->Rank0(N - 1))
return -1;
91 return detail::CalcSelect0(nth, N, This()->bitmap_, lv_a_, lv_b_);
94 NLIB_ASSERT(This()->bitmap_);
95 if (idx >= N)
return false;
96 unsigned int blk = idx / BLK_SIZE;
97 unsigned int ofs = idx % BLK_SIZE;
98 if (!(This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs))) {
99 This()->bitmap_[blk] |=
static_cast<BIT
>(1) << ofs;
106 NLIB_ASSERT(This()->bitmap_);
107 if (idx >= N)
return false;
108 unsigned int blk = idx / BLK_SIZE;
109 unsigned int ofs = idx % BLK_SIZE;
110 if (This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs)) {
111 This()->bitmap_[blk] &= ~(
static_cast<BIT
>(1) << ofs);
117 return value ? this->Set(idx) : this->Unset(idx);
120 NLIB_ASSERT(This()->bitmap_);
123 nlib_memset(reinterpret_cast<void*>(&This()->bitmap_[0]),
125 static_cast<size_t>(WORD_COUNT *
sizeof(This()->bitmap_[0])));
134 static_cast<size_t>(LV_A_COUNT *
sizeof(lv_a_[0])));
137 static_cast<size_t>(LV_B_COUNT *
sizeof(lv_b_[0])));
141 Derived* This()
NLIB_NOEXCEPT {
return static_cast<Derived*
>(
this); }
142 const Derived* This()
const NLIB_NOEXCEPT {
return static_cast<const Derived*
>(
this); }
144 detail::BuildRankDictionary(WORD_COUNT, This()->bitmap_, lv_a_, lv_b_);
147 mutable bool is_dirty_;
148 mutable uint32_t lv_a_[LV_A_COUNT];
149 mutable uint8_t lv_b_[LV_B_COUNT];
153 template <
size_t N,
class BIT = u
int64_t>
155 template <
size_t N,
class BIT = u
int32_t>
164 BIT bitmap_[CrtpBase::WORD_COUNT];
169 template <
size_t N,
class BIT = u
int64_t>
171 template <
size_t N,
class BIT = u
int32_t>
178 enum { ARRAY_SIZE = CrtpBase::WORD_COUNT };
192 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_ int Select1(unsigned int nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
Rank/Select操作つきのビットデータを保持するデータ構造です。
bool TurnOn(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
const BIT * GetBitVector() const noexcept
ビットデータへのポインタを返します。
bool Unset(unsigned int idx) noexcept
集合から32bit符号なし整数を取り除きます。
bool Set(unsigned int idx, bool value) noexcept
ビットデータのビットを設定します。
void Init(BIT *bitmap) noexcept
ビットデータへのポインタを設定します。
bool operator[](const unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
int Select0(unsigned int nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
unsigned int Rank0(unsigned int idx) const noexcept
Rank操作を行います。
unsigned int GetBitVectorSize() const noexcept
ビットデータのサイズを返します。
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Rank/Select操作つきのビットデータを保持するデータ構造です。
bool Set(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Rank/Select操作つきのビットデータを保持するデータ構造です。
bool Has(unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
unsigned int Rank1(unsigned int idx) const noexcept
Rank操作を行います。