nlib
Sbv.h
Go to the documentation of this file.
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
5 
6 #include <string.h>
7 #include <utility>
8 
9 #include "nn/nlib/Config.h"
10 #include "nn/nlib/Swap.h"
11 #include "nn/nlib/SmartBitmap.h"
12 #include "nn/nlib/BinaryReader.h"
13 #include "nn/nlib/BinaryWriter.h"
14 #include "nn/nlib/TypeTraits.h"
15 
16 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
17 #undef NLIB_VIS_PUBLIC
18 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
19 #endif
20 
21 NLIB_NAMESPACE_BEGIN
22 namespace succinct {
23 
24 namespace detail {
25 static const unsigned int BLK_SIZE = 32;
26 } // namespace detail
27 
29  public:
30  typedef uint32_t IdxType;
31  Set() NLIB_NOEXCEPT : prv_(NULL) {}
32  ~Set() NLIB_NOEXCEPT;
33  NLIB_MOVE_MEMBER_HELPER_1(Set, prv_);
34  void swap(Set& rhs) NLIB_NOEXCEPT {
35  SetPrivate* tmp = rhs.prv_;
36  rhs.prv_ = prv_;
37  prv_ = tmp;
38  }
39  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
40  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT;
41  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT;
42  bool Build() NLIB_NOEXCEPT;
43  bool Has(uint32_t idx) const NLIB_NOEXCEPT;
44  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT;
45  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT {
46  uint32_t rank1 = this->Rank1(idx);
47  return idx + 1 - rank1;
48  }
49  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
50  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT;
51  size_t MemSize() const NLIB_NOEXCEPT;
52  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT;
53  const uint32_t* GetBitVector() const NLIB_NOEXCEPT;
54  void Reset() NLIB_NOEXCEPT;
55  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT NLIB_NONNULL;
56  bool Import(BinaryReader* r) NLIB_NOEXCEPT NLIB_NONNULL;
57 
58  private:
59  struct SetPrivate;
60  mutable SetPrivate* prv_;
62 };
63 
65  public:
66  typedef uint32_t IdxType;
67  Sbv() NLIB_NOEXCEPT : prv_(NULL) {}
68  ~Sbv() NLIB_NOEXCEPT;
69  NLIB_MOVE_MEMBER_HELPER_2(Sbv, prv_, set_);
70  void swap(Sbv& rhs) NLIB_NOEXCEPT {
71  using std::swap;
72  set_.swap(rhs.set_);
73  SbvPrivate* tmp = rhs.prv_;
74  rhs.prv_ = prv_;
75  prv_ = tmp;
76  }
77  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
78  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOn(idx); }
79  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOff(idx); }
80  bool Build() NLIB_NOEXCEPT;
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); }
84  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
85  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT { return set_.Select0(nth); }
86  size_t MemSize() const NLIB_NOEXCEPT;
87  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT { return set_.GetBitVectorSize(); }
88  const uint32_t* GetBitVector() const NLIB_NOEXCEPT { return set_.GetBitVector(); }
89  void Reset() NLIB_NOEXCEPT;
90  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
91  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
92 
93  private:
94  struct SbvPrivate;
95  SbvPrivate* prv_;
96  Set set_;
98 };
99 
101  public:
102  // index is 64-bit and # of on-bits is 32-bit.
103  // In other words, rank is 64-bit index, and select is 32-bit index
104  typedef uint64_t IdxType;
105  SparseSet() NLIB_NOEXCEPT : bitvector_size_(0),
106  lowest_idx_(0xFFFFFFFF),
107  highest_idx_(0),
108  num_on_bits_(0),
109  width_(0),
110  blen_(0),
111  b_(NULL) {}
113 #ifdef NLIB_CXX11_RVALUE_REFERENCES
115  SparseSet& operator=(SparseSet&& rhs) NLIB_NOEXCEPT;
116 #endif
117  bool Init(uint64_t bv_size) NLIB_NOEXCEPT;
118  bool TurnOn(uint64_t idx) NLIB_NOEXCEPT;
119  bool Build() NLIB_NOEXCEPT;
120  bool Has(uint64_t idx, uint32_t* rank) const NLIB_NOEXCEPT {
121  // called after Build()
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);
127  // if (select1 < 0) return false; // not possible
128  return idx == static_cast<uint64_t>(select1);
129  }
130  bool Has(uint64_t idx) const NLIB_NOEXCEPT {
131  return this->Has(idx, NULL);
132  }
133  uint32_t Rank1(uint64_t idx) const NLIB_NOEXCEPT;
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);
137  }
138  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
139  int64_t Select1Ex(uint32_t nth) const NLIB_NOEXCEPT;
140  size_t MemSize() const NLIB_NOEXCEPT;
141  uint64_t GetBitVectorSize() const NLIB_NOEXCEPT {
142  return bitvector_size_;
143  }
144  void Reset() NLIB_NOEXCEPT;
145  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
146  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
147  void swap(SparseSet& rhs) NLIB_NOEXCEPT; // NOLINT
148 
149  private:
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];
158  b <<= 32;
159  b += b_[idx];
160  return static_cast<uint32_t>((b >> ofs) & ((1 << num) - 1));
161  } else {
162  return (b_[idx] >> ofs) & ((1 << num) - 1);
163  }
164  }
165 
166  private:
167  uint64_t bitvector_size_;
168  uint64_t lowest_idx_;
169  uint64_t highest_idx_;
170  uint32_t num_on_bits_;
171  uint32_t width_;
172  uint32_t blen_;
173  uint32_t* b_;
174  Sbv sbv_; // Set sbv_;
176 };
177 
179  static const size_t UNIT_SIZE = 64;
180 
181  public:
183  : header_(NULL), data_(NULL), header_size_(0), header_capacity_(0),
184  data_size_(0), data_capacity_(0), workidx_(0) {}
187  CompressedArray& assign(CompressedArray &rhs, move_tag) NLIB_NOEXCEPT; // NOLINT
188 #ifdef NLIB_CXX11_RVALUE_REFERENCES
191 #endif
192  // NLIB_MOVE_MEMBER_HELPER_3(CompressedArray, header_, data_, workidx_);
193  void swap(CompressedArray& rhs) NLIB_NOEXCEPT;
194  bool PushBack(uint32_t x) NLIB_NOEXCEPT {
195  work_[workidx_++] = x;
196  if (workidx_ == UNIT_SIZE) return this->Build();
197  return true;
198  }
199  uint32_t operator[](size_t idx) const NLIB_NOEXCEPT;
200  size_t Size() const NLIB_NOEXCEPT {
201  return workidx_ + header_capacity_ * UNIT_SIZE / 2;
202  }
203  void Reset() NLIB_NOEXCEPT;
204  size_t MemSize() const NLIB_NOEXCEPT;
205  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
206  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
207 
208  private:
209  bool Build() NLIB_NOEXCEPT;
210  // Header:
211  // baseidx: index of data_(lower 27bits)
212  // k: bit width of diff data(upper 5bits)
213  // base: base value(uint32_t)
214 
215  // Data:
216  // UNIT_SIZE * kbit: diff data
217  uint32_t* header_;
218  uint32_t* data_;
219  uint32_t header_size_;
220  uint32_t header_capacity_;
221  uint32_t data_size_;
222  uint32_t data_capacity_;
223  uint8_t workidx_;
224  uint32_t work_[UNIT_SIZE];
226 };
227 
229  typedef CompressedArray ArrayType;
230  typedef SparseSet SetType;
231 
232  public:
234  typedef std::pair<bool, uint32_t> FindType;
235  Map() NLIB_NOEXCEPT : set_(), value_() {}
237  NLIB_MOVE_MEMBER_HELPER_2(Map, set_, value_);
238  void swap(Map& rhs) NLIB_NOEXCEPT {
239  set_.swap(rhs.set_);
240  value_.swap(rhs.value_);
241  }
242  bool Init(IdxType bv_size) NLIB_NOEXCEPT {
243  if (value_.Size() != 0) return false;
244  return set_.Init(bv_size);
245  }
246  bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
247  if (!set_.TurnOn(idx)) return false;
248  value_.PushBack(data);
249  return true;
250  }
251  bool Build() NLIB_NOEXCEPT { return set_.Build(); }
252  FindType Find(IdxType idx) NLIB_NOEXCEPT {
253  if (set_.Has(idx))
254  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
255  else
256  return std::make_pair(false, 0);
257  }
258  const FindType Find(IdxType idx) const NLIB_NOEXCEPT {
259  if (set_.Has(idx))
260  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
261  else
262  return std::make_pair(false, 0);
263  }
264  size_t MemSize() const NLIB_NOEXCEPT {
265  size_t value_size = value_.MemSize();
266  size_t set_size = set_.MemSize();
267  return value_size + set_size;
268  }
269  const SetType& GetKeys() const NLIB_NOEXCEPT { return set_; }
270  const ArrayType& GetValues() const NLIB_NOEXCEPT { return value_; }
272  value_.Reset();
273  set_.Reset();
274  }
276  if (!value_.Export(w)) return false;
277  if (!set_.Export(w)) return false;
278  return true;
279  }
281  if (!value_.Import(r) || !set_.Import(r)) {
282  this->Reset();
283  return false;
284  }
285  return true;
286  }
287 
288  private:
289  SetType set_;
290  ArrayType value_;
292 };
293 
294 } // namespace succinct
295 NLIB_NAMESPACE_END
296 
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)
302 
303 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
304 #undef NLIB_VIS_PUBLIC
305 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
306 #endif
307 
308 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
uint32_t Rank1(uint32_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:82
bool TurnOff(uint32_t idx) noexcept
Removes a 32-bit unsigned integer from the set.
Definition: Sbv.h:79
Sbv() noexcept
Instantiates the object.
Definition: Sbv.h:67
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
uint32_t IdxType
typedef for the integer index type.
Definition: Sbv.h:66
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
Definition: Sbv.h:264
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:145
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: Sbv.h:78
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:64
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.
Definition: Sbv.h:85
FindType Find(IdxType idx) noexcept
Specifies a key and gets the value in the associative array.
Definition: Sbv.h:252
bool Has(uint64_t idx, uint32_t *rank) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: Sbv.h:120
void swap(Map &rhs) noexcept
Swaps the contents of an object.
Definition: Sbv.h:238
bool Init(IdxType bv_size) noexcept
Initializes an object.
Definition: Sbv.h:242
bool Has(uint32_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: Sbv.h:81
void swap(Set &rhs) noexcept
Swaps the contents of an object.
Definition: Sbv.h:34
uint32_t Rank0(uint64_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:134
Set() noexcept
Instantiates the object.
Definition: Sbv.h:31
void swap(Sbv &rhs) noexcept
Swaps the contents of an object.
Definition: Sbv.h:70
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:61
const SetType & GetKeys() const noexcept
Gets the key set.
Definition: Sbv.h:269
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
Definition: Sbv.h:275
CompressedArray() noexcept
Instantiates the object.
Definition: Sbv.h:182
const ArrayType & GetValues() const noexcept
Gets the set of values.
Definition: Sbv.h:270
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:45
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:28
An empty structure indicating that an argument to a function needs to be moved.
Definition: Config.h:231
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
Definition: Sbv.h:88
SparseSet() noexcept
Instantiates the object.
Definition: Sbv.h:105
uint64_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
Definition: Sbv.h:141
A compressed array of integers that allows appending additional data.
Definition: Sbv.h:178
bool TurnOn(IdxType idx, uint32_t data) noexcept
Adds a key and value.
Definition: Sbv.h:246
Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers.
Definition: Sbv.h:100
SetType::IdxType IdxType
Integer index.
Definition: Sbv.h:233
Defines the class for writing binary files to streams.
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:86
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: Sbv.h:271
bool Has(uint64_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: Sbv.h:130
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.
Definition: Sbv.h:104
bool Build() noexcept
Builds an associative array.
Definition: Sbv.h:251
bool Import(BinaryReader *r) noexcept
Reads the written object.
Definition: Sbv.h:280
Map() noexcept
Instantiates the object.
Definition: Sbv.h:235
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:13
A compact integer to integer read-only associative array.
Definition: Sbv.h:228
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:211
const FindType Find(IdxType idx) const noexcept
Specifies a key and gets the value in the associative array.
Definition: Sbv.h:258
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:13
uint32_t IdxType
typedef for the integer index type.
Definition: Sbv.h:30
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:83
size_t Size() const noexcept
Gets the array length.
Definition: Sbv.h:200
#define NLIB_NONNULL
Indicates that you cannot specify NULL for all arguments.
Definition: Platform_unix.h:76
uint32_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
Definition: Sbv.h:87
bool PushBack(uint32_t x) noexcept
Adds data. Compresses data after it becomes 64 elements long.
Definition: Sbv.h:194
std::pair< bool, uint32_t > FindType
Pair of boolean value and integer. If the value is not found, the boolean value is false...
Definition: Sbv.h:234
~Map() noexcept
Destructor.
Definition: Sbv.h:236