3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_SBV_H_ 4 #define INCLUDE_NN_NLIB_SUCCINCT_SBV_H_ 10 #include "nn/nlib/Swap.h" 16 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 17 #undef NLIB_VIS_PUBLIC 18 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT 25 static const unsigned int BLK_SIZE = 32;
33 NLIB_MOVE_MEMBER_HELPER_1(
Set, prv_);
35 SetPrivate* tmp = rhs.prv_;
45 uint32_t
Rank0(uint32_t idx)
const NLIB_NOEXCEPT {
46 uint32_t rank1 = this->Rank1(idx);
47 return idx + 1 - rank1;
60 mutable SetPrivate* prv_;
69 NLIB_MOVE_MEMBER_HELPER_2(
Sbv, prv_, set_);
73 SbvPrivate* tmp = rhs.prv_;
78 bool TurnOn(uint32_t idx) NLIB_NOEXCEPT {
return set_.TurnOn(idx); }
79 bool TurnOff(uint32_t idx) NLIB_NOEXCEPT {
return set_.TurnOff(idx); }
81 bool Has(uint32_t idx)
const NLIB_NOEXCEPT {
return set_.Has(idx); }
82 uint32_t
Rank1(uint32_t idx)
const NLIB_NOEXCEPT {
return set_.Rank1(idx); }
83 uint32_t
Rank0(uint32_t idx)
const NLIB_NOEXCEPT {
return set_.Rank0(idx); }
85 int32_t
Select0(uint32_t nth)
const NLIB_NOEXCEPT {
return set_.Select0(nth); }
88 const uint32_t*
GetBitVector() const NLIB_NOEXCEPT {
return set_.GetBitVector(); }
106 lowest_idx_(0xFFFFFFFF),
113 #ifdef NLIB_CXX11_RVALUE_REFERENCES 120 bool Has(uint64_t idx, uint32_t* rank)
const NLIB_NOEXCEPT {
122 uint32_t rank1 = this->Rank1(idx);
123 if (rank) *rank = rank1;
124 if (rank1 == 0)
return false;
125 int64_t select1 = this->Select1Ex(rank1 - 1);
126 NLIB_ASSERT(select1 >= 0);
128 return idx ==
static_cast<uint64_t
>(select1);
130 bool Has(uint64_t idx)
const NLIB_NOEXCEPT {
131 return this->Has(idx, NULL);
134 uint32_t
Rank0(uint64_t idx)
const NLIB_NOEXCEPT {
135 uint32_t rank1 = this->Rank1(idx);
136 return static_cast<uint32_t
>(idx + 1 - rank1);
142 return bitvector_size_;
150 uint32_t GetBits(uint64_t pos,
size_t num)
const NLIB_NOEXCEPT {
151 NLIB_ASSERT(num <= 32);
152 uint64_t idx64 = pos / detail::BLK_SIZE;
153 NLIB_ASSERT(idx64 <= SIZE_MAX);
154 size_t idx =
static_cast<size_t>(idx64);
155 size_t ofs =
static_cast<size_t>(pos % detail::BLK_SIZE);
156 if (ofs + num > 32) {
157 uint64_t b = b_[idx + 1];
160 return static_cast<uint32_t
>((b >> ofs) & ((1 << num) - 1));
162 return (b_[idx] >> ofs) & ((1 << num) - 1);
167 uint64_t bitvector_size_;
168 uint64_t lowest_idx_;
169 uint64_t highest_idx_;
170 uint32_t num_on_bits_;
179 static const size_t UNIT_SIZE = 64;
183 : header_(NULL), data_(NULL), header_size_(0), header_capacity_(0),
184 data_size_(0), data_capacity_(0), workidx_(0) {}
188 #ifdef NLIB_CXX11_RVALUE_REFERENCES 195 work_[workidx_++] = x;
196 if (workidx_ == UNIT_SIZE)
return this->Build();
200 size_t Size() const NLIB_NOEXCEPT {
201 return workidx_ + header_capacity_ * UNIT_SIZE / 2;
219 uint32_t header_size_;
220 uint32_t header_capacity_;
222 uint32_t data_capacity_;
224 uint32_t work_[UNIT_SIZE];
237 NLIB_MOVE_MEMBER_HELPER_2(
Map, set_, value_);
240 value_.swap(rhs.value_);
243 if (value_.Size() != 0)
return false;
244 return set_.Init(bv_size);
247 if (!set_.TurnOn(idx))
return false;
248 value_.PushBack(data);
254 return std::make_pair(
true, value_[set_.Rank1(idx) - 1]);
256 return std::make_pair(
false, 0);
260 return std::make_pair(
true, value_[set_.Rank1(idx) - 1]);
262 return std::make_pair(
false, 0);
265 size_t value_size = value_.MemSize();
266 size_t set_size = set_.MemSize();
267 return value_size + set_size;
276 if (!value_.Export(w))
return false;
277 if (!set_.Export(w))
return false;
281 if (!value_.Import(r) || !set_.Import(r)) {
297 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Set)
298 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Sbv)
299 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::SparseSet)
300 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::CompressedArray)
301 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Map)
303 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 304 #undef NLIB_VIS_PUBLIC 305 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT 308 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_ uint32_t Rank1(uint32_t idx) const noexcept
Performs a Rank operation.
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.
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
#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.
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.
int32_t Select0(uint32_t nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
FindType Find(IdxType idx) noexcept
Specifies a key and gets the value in the associative array.
bool Has(uint64_t idx, uint32_t *rank) const noexcept
Tests to determine whether a particular value is contained in the set.
void swap(Map &rhs) noexcept
Swaps the contents of an object.
bool Init(IdxType bv_size) noexcept
Initializes an object.
bool Has(uint32_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
void swap(Set &rhs) noexcept
Swaps the contents of an object.
uint32_t Rank0(uint64_t idx) const noexcept
Performs a Rank operation.
Set() noexcept
Instantiates the object.
void swap(Sbv &rhs) noexcept
Swaps the contents of an object.
const SetType & GetKeys() const noexcept
Gets the key set.
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
CompressedArray() noexcept
Instantiates the object.
const ArrayType & GetValues() const noexcept
Gets the set of values.
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
An empty structure indicating that an argument to a function needs to be moved.
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
SparseSet() noexcept
Instantiates the object.
uint64_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
A compressed array of integers that allows appending additional data.
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.
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
bool Has(uint64_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
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.
The class for writing binary to streams (to OutputStream).
A compact integer to integer read-only associative array.
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
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 Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
size_t Size() const noexcept
Gets the array length.
uint32_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
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.