3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
10 #include "nn/nlib/Swap.h"
18 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
19 #undef NLIB_VIS_PUBLIC
20 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
33 static const unsigned int BLK_SIZE = 32;
37 static const int kBitCount =
sizeof(BIT) * 8;
38 return (num_bits + kBitCount - 1) / kBitCount;
43 static const int kBitCount =
sizeof(BIT) * 8;
44 return (num_bits + kBitCount - 1) / kBitCount;
49 static const int kBitCount =
sizeof(*bv) * 8;
50 uint32_t blk = idx / kBitCount;
51 uint32_t ofs = idx % kBitCount;
52 bv[blk] |=
static_cast<BIT
>(1) << ofs;
57 static const int kBitCount =
sizeof(*bv) * 8;
58 uint64_t blk = idx / kBitCount;
59 uint32_t ofs =
static_cast<uint32_t
>(idx % kBitCount);
60 bv[blk] |=
static_cast<BIT
>(1) << ofs;
65 static const int kBitCount =
sizeof(*bv) * 8;
66 uint32_t blk = idx / kBitCount;
67 uint32_t ofs = idx % kBitCount;
68 bv[blk] &= ~(
static_cast<BIT
>(1) << ofs);
73 static const int kBitCount =
sizeof(*bv) * 8;
74 uint64_t blk = idx / kBitCount;
75 uint32_t ofs =
static_cast<uint32_t
>(idx % kBitCount);
76 bv[blk] &= ~(
static_cast<BIT
>(1) << ofs);
81 static const int kBitCount =
sizeof(*bv) * 8;
82 uint32_t blk = idx / kBitCount;
83 uint32_t ofs = idx % kBitCount;
84 return 0 != (bv[blk] & (
static_cast<BIT
>(1) << ofs));
89 static const int kBitCount =
sizeof(*bv) * 8;
90 uint64_t blk = idx / kBitCount;
91 uint32_t ofs =
static_cast<uint32_t
>(idx % kBitCount);
92 return 0 != (bv[blk] & (
static_cast<BIT
>(1) << ofs));
99 : m_Obj(obj), m_Ok(
false) {}
101 if (!m_Ok) m_Obj->Reset();
120 NLIB_MOVE_MEMBER_HELPER_2(PlainArray32, m_Count, m_Value);
123 swap(m_Count, rhs.m_Count);
124 swap(m_Value, rhs.m_Value);
128 T& operator[](
size_t idx) {
129 NLIB_ASSERT(idx < m_Count);
132 const T& operator[](
size_t idx)
const {
133 NLIB_ASSERT(idx < m_Count);
136 size_t Size() const NLIB_NOEXCEPT {
return m_Count; }
137 size_t MemSize() const NLIB_NOEXCEPT {
138 size_t array_size =
sizeof(T) * m_Count;
139 return sizeof(m_Count) +
sizeof(m_Value) + array_size;
141 void Reset() NLIB_NOEXCEPT;
142 bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
143 bool Import(BinaryReader* r) NLIB_NOEXCEPT;
147 UniquePtr<T[]> m_Value;
152 bool PlainArray32<T>::Init(uint32_t count) NLIB_NOEXCEPT {
153 if (m_Value)
return false;
158 m_Value.reset(
new (std::nothrow) T[count]);
159 if (!m_Value)
return false;
161 memset(m_Value.get(), 0,
sizeof(T) * count);
172 bool PlainArray32<T>::Export(BinaryWriter* w)
const NLIB_NOEXCEPT {
173 if (!w->Write(m_Count))
return false;
174 if (!w->WriteArray(m_Value.get(), m_Count))
return false;
179 bool PlainArray32<T>::Import(BinaryReader* r) NLIB_NOEXCEPT {
180 Resetter<PlainArray32<T> > rst(
this);
181 if (!r->Read(&m_Count))
return false;
186 m_Value.reset(
new (std::nothrow) T[m_Count]);
187 if (!m_Value)
return false;
188 if (m_Count != r->ReadArray(m_Value.get(), m_Count))
return false;
195 BitVector32() NLIB_NOEXCEPT : m_Size(0), m_BitVector() {}
197 NLIB_MOVE_MEMBER_HELPER_2(BitVector32, m_Size, m_BitVector);
198 void swap(BitVector32& rhs) NLIB_NOEXCEPT {
200 swap(m_Size, rhs.m_Size);
201 swap(m_BitVector, rhs.m_BitVector);
204 bool TurnOn(uint32_t nth) NLIB_NOEXCEPT {
205 if (nth >= m_Size)
return false;
206 SetBit(m_BitVector.get(), nth);
209 bool TurnOff(uint32_t nth) NLIB_NOEXCEPT {
210 if (nth >= m_Size)
return false;
211 ResetBit(m_BitVector.get(), nth);
214 bool operator[](uint32_t nth)
const NLIB_NOEXCEPT {
215 return nth < m_Size ? GetBit(m_BitVector.get(), nth) :
false;
217 uint32_t Size() const NLIB_NOEXCEPT {
return m_Size; }
218 const uint32_t* Data() const NLIB_NOEXCEPT {
219 return m_BitVector.get();
228 UniquePtr<uint32_t[]> m_BitVector;
239 SbvRank() NLIB_NOEXCEPT : m_LvA(), m_LvB() {}
241 NLIB_MOVE_MEMBER_HELPER_2(SbvRank, m_LvA, m_LvB);
242 void swap(SbvRank& rhs) NLIB_NOEXCEPT {
244 swap(m_LvA, rhs.m_LvA);
245 swap(m_LvB, rhs.m_LvB);
248 uint32_t Rank1(
const uint32_t* bv, uint32_t pos)
const NLIB_NOEXCEPT {
249 using ::nlib_ns::detail::CalcRank1;
250 return CalcRank1(pos, bv, m_LvA.get(), m_LvB.get());
252 uint32_t Rank0(
const uint32_t* bv, uint32_t pos)
const NLIB_NOEXCEPT {
253 return pos + 1 - this->Rank1(bv, pos);
255 int32_t Select1(
const uint32_t* bv, uint32_t size, uint32_t nth)
const NLIB_NOEXCEPT {
256 using ::nlib_ns::detail::CalcSelect1;
257 if (nth >= this->Rank1(bv, size - 1))
return -1;
258 int32_t ans = CalcSelect1(nth, size, bv, m_LvA.get(), m_LvB.get());
259 NLIB_ASSERT(ans < static_cast<int>(size));
262 int32_t Select0(
const uint32_t* bv, uint32_t size, uint32_t nth)
const NLIB_NOEXCEPT {
263 using ::nlib_ns::detail::CalcSelect0;
264 if (nth >= this->Rank0(bv, size - 1))
return -1;
265 int32_t ans = CalcSelect0(nth, size, bv, m_LvA.get(), m_LvB.get());
266 NLIB_ASSERT(ans < static_cast<int>(size));
271 NLIB_VIS_PUBLIC bool Export(BinaryWriter* w, uint32_t size) const NLIB_NOEXCEPT;
272 NLIB_VIS_PUBLIC bool Import(BinaryReader* r, uint32_t size) NLIB_NOEXCEPT;
275 UniquePtr<uint32_t[]> m_LvA;
276 UniquePtr<uint8_t[]> m_LvB;
282 class SbvSelect NLIB_FINAL {
285 SbvSelect() NLIB_NOEXCEPT {}
287 NLIB_MOVE_MEMBER_HELPER_5(SbvSelect, m_ClumpArray, m_R, m_Q, m_RankR, m_RankQ);
288 void swap(SbvSelect& rhs) NLIB_NOEXCEPT {
290 m_ClumpArray.swap(rhs.m_ClumpArray);
293 m_RankR.swap(rhs.m_RankR);
294 m_RankQ.swap(rhs.m_RankQ);
298 NLIB_VIS_PUBLIC int32_t Select(const Set& set, uint32_t nth) const NLIB_NOEXCEPT;
304 PlainArray32<uint32_t> m_ClumpArray;
317 Set() NLIB_NOEXCEPT : m_BVec(), m_Rank() {}
319 NLIB_MOVE_MEMBER_HELPER_2(
Set, m_BVec, m_Rank);
320 void swap(Set& rhs) NLIB_NOEXCEPT {
322 m_BVec.
swap(rhs.m_BVec);
323 m_Rank.swap(rhs.m_Rank);
325 bool Init(uint32_t bv_size) NLIB_NOEXCEPT {
return m_BVec.Init(bv_size); }
326 bool TurnOn(uint32_t idx) NLIB_NOEXCEPT {
return m_BVec.TurnOn(idx); }
327 bool TurnOff(uint32_t idx) NLIB_NOEXCEPT {
return m_BVec.TurnOff(idx); }
329 bool Has(uint32_t idx) const NLIB_NOEXCEPT {
return m_BVec[idx]; }
330 uint32_t
Rank1(uint32_t idx)
const NLIB_NOEXCEPT {
332 uint32_t pos = idx < m_BVec.Size() ? idx : m_BVec.Size() - 1;
333 return m_Rank.Rank1(m_BVec.Data(), pos);
335 uint32_t
Rank0(uint32_t idx)
const NLIB_NOEXCEPT {
336 uint32_t rank1 = this->Rank1(idx);
337 return idx + 1 - rank1;
339 int32_t
Select1(uint32_t nth)
const NLIB_NOEXCEPT {
340 return m_Rank.Select1(m_BVec.Data(), m_BVec.Size(), nth);
342 int32_t
Select0(uint32_t nth)
const NLIB_NOEXCEPT {
343 return m_Rank.Select0(m_BVec.Data(), m_BVec.Size(), nth);
346 uint32_t GetBitVectorSize() const NLIB_NOEXCEPT {
return m_BVec.Size(); }
347 const uint32_t*
GetBitVector() const NLIB_NOEXCEPT {
return m_BVec.Data(); }
348 void Reset() NLIB_NOEXCEPT { m_BVec.Reset(); }
353 detail::BitVector32 m_BVec;
354 detail::SbvRank m_Rank;
363 NLIB_MOVE_MEMBER_HELPER_2(
Sbv, m_Set, m_Select1);
364 void swap(Sbv& rhs) NLIB_NOEXCEPT {
366 m_Set.
swap(rhs.m_Set);
367 m_Select1.swap(rhs.m_Select1);
369 bool Init(uint32_t bv_size) NLIB_NOEXCEPT {
return m_Set.Init(bv_size); }
370 bool TurnOn(uint32_t idx) NLIB_NOEXCEPT {
return m_Set.TurnOn(idx); }
371 bool TurnOff(uint32_t idx) NLIB_NOEXCEPT {
return m_Set.TurnOff(idx); }
373 bool Has(uint32_t idx) const NLIB_NOEXCEPT {
return m_Set.Has(idx); }
374 uint32_t
Rank1(uint32_t idx)
const NLIB_NOEXCEPT {
return m_Set.Rank1(idx); }
375 uint32_t
Rank0(uint32_t idx)
const NLIB_NOEXCEPT {
return m_Set.Rank0(idx); }
376 int32_t
Select1(uint32_t nth)
const NLIB_NOEXCEPT {
377 return m_Select1.Select(m_Set, nth);
379 int32_t
Select0(uint32_t nth)
const NLIB_NOEXCEPT {
380 return m_Set.Select0(nth);
382 size_t MemSize() const NLIB_NOEXCEPT;
383 uint32_t GetBitVectorSize() const NLIB_NOEXCEPT {
384 return m_Set.GetBitVectorSize();
387 return m_Set.GetBitVector();
398 detail::SbvSelect m_Select1;
408 m_LowestIdx(0xFFFFFFFF),
415 #ifdef NLIB_CXX11_RVALUE_REFERENCES
417 m_BitVectorSize(rhs.m_BitVectorSize), m_LowestIdx(rhs.m_LowestIdx),
418 m_HighestIdx(rhs.m_HighestIdx), m_NumOnBits(rhs.m_NumOnBits),
419 m_Width(rhs.m_Width), m_BLen(rhs.m_BLen),
420 m_B(
std::move(rhs.m_B)), m_Sbv(
std::move(rhs.m_Sbv)) {}
422 m_BitVectorSize = rhs.m_BitVectorSize;
423 m_LowestIdx = rhs.m_LowestIdx;
424 m_HighestIdx = rhs.m_HighestIdx;
425 m_NumOnBits = rhs.m_NumOnBits;
426 m_Width = rhs.m_Width;
428 m_B = std::move(rhs.m_B);
429 m_Sbv = std::move(rhs.m_Sbv);
436 bool Has(uint64_t idx, uint32_t* rank) const NLIB_NOEXCEPT {
438 uint32_t rank1 = this->Rank1(idx);
439 if (rank) *rank = rank1;
440 if (rank1 == 0)
return false;
441 int64_t select1 = this->Select1Ex(rank1 - 1);
442 NLIB_ASSERT(select1 >= 0);
444 return idx ==
static_cast<uint64_t
>(select1);
446 bool Has(uint64_t idx)
const NLIB_NOEXCEPT {
447 return this->Has(idx, NULL);
450 uint32_t
Rank0(uint64_t idx)
const NLIB_NOEXCEPT {
451 uint32_t rank1 = this->Rank1(idx);
452 return static_cast<uint32_t
>(idx + 1 - rank1);
457 uint64_t GetBitVectorSize() const NLIB_NOEXCEPT {
458 return m_BitVectorSize;
466 uint32_t GetBits(uint64_t pos,
size_t num) const NLIB_NOEXCEPT {
467 NLIB_ASSERT(num <= 32);
468 uint64_t idx64 = pos / detail::BLK_SIZE;
469 NLIB_ASSERT(idx64 <= SIZE_MAX);
470 size_t idx =
static_cast<size_t>(idx64);
471 size_t ofs =
static_cast<size_t>(pos % detail::BLK_SIZE);
472 if (ofs + num > 32) {
473 uint64_t b = m_B[idx + 1];
476 return static_cast<uint32_t
>((b >> ofs) & ((1 << num) - 1));
478 return (m_B[idx] >> ofs) & ((1 << num) - 1);
483 uint64_t m_BitVectorSize;
484 uint64_t m_LowestIdx;
485 uint64_t m_HighestIdx;
486 uint32_t m_NumOnBits;
489 UniquePtr<uint32_t[]> m_B;
523 static const size_t UNIT_SIZE = 64;
530 void swap(CompressedArray& rhs) NLIB_NOEXCEPT {
532 swap(m_Header, rhs.m_Header);
533 swap(m_Data, rhs.m_Data);
534 swap(m_Idx, rhs.m_Idx);
535 for (
size_t i = 0; i < UNIT_SIZE; ++i) {
536 swap(m_Work[i], rhs.m_Work[i]);
541 if (m_Idx == UNIT_SIZE)
return this->Build();
545 size_t Size() const NLIB_NOEXCEPT {
546 return m_Idx + m_Header.size() * UNIT_SIZE / 2;
565 uint32_t m_Work[UNIT_SIZE];
576 Map() NLIB_NOEXCEPT : m_Set(), m_Value() {}
578 NLIB_MOVE_MEMBER_HELPER_2(
Map, m_Set, m_Value);
580 m_Set.swap(rhs.m_Set);
581 m_Value.swap(rhs.m_Value);
583 bool Init(IdxType bv_size) NLIB_NOEXCEPT {
584 if (m_Value.Size() != 0)
return false;
585 return m_Set.Init(bv_size);
587 bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
588 if (!m_Set.TurnOn(idx))
return false;
589 m_Value.PushBack(data);
592 bool Build() NLIB_NOEXCEPT {
return m_Set.Build(); }
593 FindType
Find(IdxType idx) NLIB_NOEXCEPT {
595 return std::make_pair(
true, m_Value[m_Set.Rank1(idx) - 1]);
597 return std::make_pair(
false, 0);
599 const FindType
Find(IdxType idx)
const NLIB_NOEXCEPT {
601 return std::make_pair(
true, m_Value[m_Set.Rank1(idx) - 1]);
603 return std::make_pair(
false, 0);
606 size_t value_size = m_Value.MemSize();
607 size_t set_size = m_Set.MemSize();
608 return value_size + set_size;
610 const SetType&
GetKeys() const NLIB_NOEXCEPT {
return m_Set; }
611 const ArrayType&
GetValues() const NLIB_NOEXCEPT {
return m_Value; }
617 if (!m_Value.Export(w))
return false;
618 if (!m_Set.Export(w))
return false;
622 if (!m_Value.Import(r) || !m_Set.Import(r)) {
638 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::detail::BitVector32)
639 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::detail::SbvRank)
640 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::detail::SbvSelect)
641 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::Set)
642 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::Sbv)
643 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::SparseSet)
645 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::CompressedArray)
646 NLIB_DEFINE_STD_SWAP(::
nlib_ns::succinct::Map)
648 NLIB_DEFINE_STD_SWAP_T_BEGIN4(
nn, nlib, succinct, detail)
649 NLIB_DEFINE_STD_SWAP_T1(T, ::
nlib_ns::succinct::detail::PlainArray32)
650 NLIB_DEFINE_STD_SWAP_T_END4(nn, nlib, succinct, detail)
652 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
653 #undef NLIB_VIS_PUBLIC
654 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
657 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
bool TurnOff(uint32_t idx) noexcept
Removes a 32-bit unsigned integer from the set.
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
bool TurnOff(uint32_t idx) noexcept
Removes a 32-bit unsigned integer from the set.
Sbv() noexcept
Instantiates the object.
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
uint32_t IdxType
typedef for the integer index type.
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
SparseSet(SparseSet &&rhs) noexcept
Instantiates the object (move constructor). This function is useful when using C++11.
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Defines the class for reading binary files from streams.
FindType Find(IdxType idx) noexcept
Specifies a key and gets the value in the associative array.
void swap(Map &rhs) noexcept
Swaps the contents of an object.
bool Init(IdxType bv_size) noexcept
Initializes an object.
void swap(Set &rhs) noexcept
Swaps the contents of an object.
Set() noexcept
Instantiates the object.
Defines that class that is corresponding to std::unique_ptr.
int32_t Select0(uint32_t nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
bool Init(uint32_t bv_size) noexcept
Initializes an object.
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
void swap(Sbv &rhs) noexcept
Swaps the contents of an object.
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
int32_t Select1(uint32_t nth) const noexcept
Returns the position of the nth 1 bit. nth starts from 0.
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
CompressedArray() noexcept
Instantiates the object.
int32_t Select0(uint32_t nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
uint32_t Rank1(uint32_t idx) const noexcept
Performs a Rank operation.
SparseSet() noexcept
Instantiates the object.
uint32_t Rank0(uint64_t idx) const noexcept
Performs a Rank operation.
A compressed array of integers that allows appending additional data.
Implements common features and features that are highly platform-dependent. Also refer to nlib Platfo...
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
bool TurnOn(IdxType idx, uint32_t data) noexcept
Adds a key and value.
Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers.
SetType::IdxType IdxType
Integer index.
Defines the class for writing binary files to streams.
size_t Size() const noexcept
Gets the array length.
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
SparseSet & operator=(SparseSet &&rhs) noexcept
Move assignment operator. This function is useful when using C++11.
A file that contains the configuration information for each development environment.
Defines the class for handing bit streams operated on by Rank and Select.
uint64_t IdxType
typedef for the integer index type.
bool Build() noexcept
Builds an associative array.
bool Import(BinaryReader *r) noexcept
Reads the written object.
Map() noexcept
Instantiates the object.
const ArrayType & GetValues() const noexcept
Gets the set of values.
The class for writing binary to streams (to OutputStream).
A compact integer to integer read-only associative array.
const SetType & GetKeys() const noexcept
Gets the key set.
bool Has(uint64_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
bool Init(uint32_t bv_size) noexcept
Initializes an object.
const FindType Find(IdxType idx) const noexcept
Specifies a key and gets the value in the associative array.
The class for reading binary from streams (from InputStream).
uint32_t IdxType
typedef for the integer index type.
uint32_t Rank1(uint32_t idx) const noexcept
Performs a Rank operation.
The class for realloc-based implementations of vectors with POD-type elements.
bool PushBack(uint32_t x) noexcept
Adds data. Compresses data after it becomes 64 elements long.
std::pair< bool, uint32_t > FindType
Pair of boolean value and integer. If the value is not found, the boolean value is false...
~Map() noexcept
Destructor.
int32_t Select1(uint32_t nth) const noexcept
Returns the position of the nth 1 bit. nth starts from 0.