16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_SBV_H_ 17 #define INCLUDE_NN_NLIB_SUCCINCT_SBV_H_ 23 #include "nn/nlib/Swap.h" 29 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 30 #undef NLIB_VIS_PUBLIC 31 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT 38 static const unsigned int BLK_SIZE = 32;
46 NLIB_DEFMOVE_PIMPL(
Set);
54 uint32_t
Rank0(uint32_t idx)
const NLIB_NOEXCEPT {
55 uint32_t rank1 = this->Rank1(idx);
56 return idx + 1 - rank1;
69 mutable SetPrivate* prv_;
78 #ifdef __cpp_rvalue_references 83 set_ = std::move(rhs.set_);
93 rhs.set_.assign(rhs.set_,
move_tag());
100 bool TurnOn(uint32_t idx) NLIB_NOEXCEPT {
return set_.TurnOn(idx); }
101 bool TurnOff(uint32_t idx) NLIB_NOEXCEPT {
return set_.TurnOff(idx); }
103 bool Has(uint32_t idx)
const NLIB_NOEXCEPT {
return set_.Has(idx); }
104 uint32_t
Rank1(uint32_t idx)
const NLIB_NOEXCEPT {
return set_.Rank1(idx); }
105 uint32_t
Rank0(uint32_t idx)
const NLIB_NOEXCEPT {
return set_.Rank0(idx); }
107 int32_t
Select0(uint32_t nth)
const NLIB_NOEXCEPT {
return set_.Select0(nth); }
110 const uint32_t*
GetBitVector() const NLIB_NOEXCEPT {
return set_.GetBitVector(); }
128 : bitvector_size_(0), lowest_idx_(0xFFFFFFFF), highest_idx_(0), num_on_bits_(0),
129 width_(0), blen_(0), b_(
nullptr) {}
131 #ifdef __cpp_rvalue_references 141 bool Has(uint64_t idx, uint32_t* rank)
const NLIB_NOEXCEPT {
143 uint32_t rank1 = this->Rank1(idx);
144 if (rank) *rank = rank1;
145 if (rank1 == 0)
return false;
146 int64_t select1 = this->Select1Ex(rank1 - 1);
147 NLIB_ASSERT(select1 >= 0);
149 return idx ==
static_cast<uint64_t
>(select1);
151 bool Has(uint64_t idx)
const NLIB_NOEXCEPT {
152 return this->Has(idx,
nullptr);
155 uint32_t
Rank0(uint64_t idx)
const NLIB_NOEXCEPT {
156 uint32_t rank1 = this->Rank1(idx);
157 return static_cast<uint32_t
>(idx + 1 - rank1);
163 return bitvector_size_;
170 uint32_t GetBits(uint64_t pos,
size_t num)
const NLIB_NOEXCEPT {
171 NLIB_ASSERT(num <= 32);
172 uint64_t idx64 = pos / detail::BLK_SIZE;
173 NLIB_ASSERT(idx64 <= SIZE_MAX);
174 size_t idx =
static_cast<size_t>(idx64);
175 size_t ofs =
static_cast<size_t>(pos % detail::BLK_SIZE);
176 if (ofs + num > 32) {
177 uint64_t b = b_[idx + 1];
180 return static_cast<uint32_t
>((b >> ofs) & ((1 << num) - 1));
182 return (b_[idx] >> ofs) & ((1 << num) - 1);
187 uint64_t bitvector_size_;
188 uint64_t lowest_idx_;
189 uint64_t highest_idx_;
190 uint32_t num_on_bits_;
199 static const size_t UNIT_SIZE = 64;
203 : header_(
nullptr), data_(
nullptr), header_size_(0), header_capacity_(0),
204 data_size_(0), data_capacity_(0), workidx_(0), work_() {}
208 #ifdef __cpp_rvalue_references 214 work_[workidx_++] = x;
215 if (workidx_ == UNIT_SIZE)
return this->Build();
219 size_t Size() const NLIB_NOEXCEPT {
220 return workidx_ + header_capacity_ * UNIT_SIZE / 2;
238 uint32_t header_size_;
239 uint32_t header_capacity_;
241 uint32_t data_capacity_;
243 uint32_t work_[UNIT_SIZE];
256 #ifdef __cpp_rvalue_references 257 #ifdef NLIB_CXX11_DEFAULTED_AND_DELETED_FUNCTIONS 259 Map& operator=(
Map&& rhs) =
default;
263 set_ = std::move(rhs.set_);
264 value_ = std::move(rhs.value_);
273 value_.assign(rhs.value_,
move_tag());
277 bool Init(IdxType bv_size) NLIB_NOEXCEPT {
278 if (value_.Size() != 0)
return false;
279 return set_.Init(bv_size);
281 bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
282 if (!set_.TurnOn(idx))
return false;
283 value_.PushBack(data);
286 bool Build() NLIB_NOEXCEPT {
return set_.Build(); }
287 FindType
Find(IdxType idx) NLIB_NOEXCEPT {
289 return std::make_pair(
true, value_[set_.Rank1(idx) - 1]);
291 return std::make_pair(
false, 0);
293 const FindType
Find(IdxType idx)
const NLIB_NOEXCEPT {
295 return std::make_pair(
true, value_[set_.Rank1(idx) - 1]);
297 return std::make_pair(
false, 0);
300 size_t value_size = value_.MemSize();
301 size_t set_size = set_.MemSize();
302 return value_size + set_size;
304 const SetType&
GetKeys() const NLIB_NOEXCEPT {
return set_; }
305 const ArrayType&
GetValues() const NLIB_NOEXCEPT {
return value_; }
311 if (!value_.Export(w))
return false;
312 if (!set_.Export(w))
return false;
316 if (!value_.Import(r) || !set_.Import(r)) {
332 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Set)
333 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Sbv)
334 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::SparseSet)
335 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::CompressedArray)
336 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Map)
342 swap(prv_, rhs.prv_);
346 swap(set_, rhs.set_);
347 swap(prv_, rhs.prv_);
351 swap(set_, rhs.set_);
352 swap(value_, rhs.value_);
356 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 357 #undef NLIB_VIS_PUBLIC 358 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT 361 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_ uint32_t Rank1(uint32_t idx) const noexcept
Rank操作を行います。
bool TurnOff(uint32_t idx) noexcept
集合から32bit符号なし整数を取り除きます。
constexpr Sbv() noexcept
コンストラクタです。
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
uint32_t IdxType
インデックスとなる整数型のtypedefです。
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
ストリームからバイナリファイルを読み込むクラスを定義しています。
int32_t Select0(uint32_t nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
FindType Find(IdxType idx) noexcept
キーを指定して連想配列から値を取得します。
bool Has(uint64_t idx, uint32_t *rank) const noexcept
値が集合に含まれているかどうかをテストします。
bool Init(IdxType bv_size) noexcept
オブジェクトを初期化します。
~CompressedArray() noexcept
デストラクタです。
bool Has(uint32_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
uint32_t Rank0(uint64_t idx) const noexcept
Rank操作を行います。
constexpr Set() noexcept
コンストラクタです。
Map & assign(Map &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Sbv & assign(Sbv &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Sbv & operator=(Sbv &&rhs) noexcept
ムーブ代入演算子です。C++11の利用時に有効です。
~SparseSet() noexcept
デストラクタです。
const SetType & GetKeys() const noexcept
キーの集合を取得します。
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
constexpr CompressedArray() noexcept
コンストラクタです。
Map(Map &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
const ArrayType & GetValues() const noexcept
値の集合を取得します。
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Sbv(Sbv &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
constexpr SparseSet() noexcept
コンストラクタです。
uint64_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
bool TurnOn(IdxType idx, uint32_t data) noexcept
キーと値を追加します。
疎な64bit符号なし整数の集合を保持する簡潔データ構造です。
SetType::IdxType IdxType
整数インデックスです。
ストリームにバイナリファイルを書き込むクラスを定義しています。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
bool Has(uint64_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
Rank/Select操作つきのビット列を扱うクラスが定義されています。
uint64_t IdxType
インデックスとなる整数型のtypedefです。
Sbv(Sbv &&rhs) noexcept
ムーブコンストラクタです。C++11の利用時に有効です。
bool Build() noexcept
連想配列を構築します。
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
constexpr Map() noexcept
コンストラクタです。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
整数から整数へのコンパクトなリードオンリーの連想配列です。
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
const FindType Find(IdxType idx) const noexcept
キーを指定して連想配列から値を取得します。
ストリーム(InputStream)からバイナリを読み込むクラスです。
uint32_t IdxType
インデックスとなる整数型のtypedefです。
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
size_t Size() const noexcept
配列の長さを取得します。
uint32_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
bool PushBack(uint32_t x) noexcept
データを追加します。64個単位の長さになるとデータを圧縮します。
std::pair< bool, uint32_t > FindType
ブール値と整数のペアです。値が見つからなかった場合はブール値がfalseです。