nlib
Sbv.h
[詳解]
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/UniquePtr.h"
15 #include "nn/nlib/TypeTraits.h"
16 #include "nn/nlib/ReallocVec.h"
17 
18 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
19 #undef NLIB_VIS_PUBLIC
20 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
21 #endif
22 
23 NLIB_NAMESPACE_BEGIN
24 
25 namespace succinct {
26 
27 class Set;
28 
29 namespace detail {
30 
31 // BIT must be uint32_t or uint64_t
32 
33 static const unsigned int BLK_SIZE = 32;
34 
35 template<class BIT>
36 NLIB_ALWAYS_INLINE uint32_t GetBlockCount(uint32_t num_bits) NLIB_NOEXCEPT {
37  static const int kBitCount = sizeof(BIT) * 8; // NOLINT
38  return (num_bits + kBitCount - 1) / kBitCount;
39 }
40 
41 template<class BIT>
42 NLIB_ALWAYS_INLINE uint64_t GetBlockCount(uint64_t num_bits) NLIB_NOEXCEPT {
43  static const int kBitCount = sizeof(BIT) * 8; // NOLINT
44  return (num_bits + kBitCount - 1) / kBitCount;
45 }
46 
47 template<class BIT>
48 NLIB_ALWAYS_INLINE void SetBit(BIT* bv, uint32_t idx) NLIB_NOEXCEPT {
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;
53 }
54 
55 template<class BIT>
56 NLIB_ALWAYS_INLINE void SetBit(BIT* bv, uint64_t idx) NLIB_NOEXCEPT {
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;
61 }
62 
63 template<class BIT>
64 NLIB_ALWAYS_INLINE void ResetBit(BIT* bv, uint32_t idx) NLIB_NOEXCEPT {
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);
69 }
70 
71 template<class BIT>
72 NLIB_ALWAYS_INLINE void ResetBit(BIT* bv, uint64_t idx) NLIB_NOEXCEPT {
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);
77 }
78 
79 template<class BIT>
80 NLIB_ALWAYS_INLINE bool GetBit(const BIT* bv, uint32_t idx) NLIB_NOEXCEPT {
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));
85 }
86 
87 template<class BIT>
88 NLIB_ALWAYS_INLINE bool GetBit(const BIT* bv, uint64_t idx) NLIB_NOEXCEPT {
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));
93 }
94 
95 template <class T>
96 class Resetter NLIB_FINAL {
97  public:
98  NLIB_ALWAYS_INLINE explicit Resetter(T* obj) NLIB_NOEXCEPT
99  : m_Obj(obj), m_Ok(false) {}
100  NLIB_ALWAYS_INLINE ~Resetter() NLIB_NOEXCEPT {
101  if (!m_Ok) m_Obj->Reset();
102  }
104  m_Ok = true;
105  return true;
106  }
107 
108  private:
109  T* m_Obj;
110  bool m_Ok;
111 };
112 
113 template <class T>
114 class PlainArray32 NLIB_FINAL {
115  public:
116  PlainArray32() NLIB_NOEXCEPT : m_Count(0), m_Value() {
117  NLIB_STATIC_ASSERT(IsPod<T>::value);
118  }
119  ~PlainArray32() NLIB_NOEXCEPT { this->Reset(); }
120  NLIB_MOVE_MEMBER_HELPER_2(PlainArray32, m_Count, m_Value);
121  void swap(PlainArray32& rhs) NLIB_NOEXCEPT {
122  using std::swap;
123  swap(m_Count, rhs.m_Count);
124  swap(m_Value, rhs.m_Value);
125  }
126 
127  bool Init(uint32_t count) NLIB_NOEXCEPT;
128  T& operator[](size_t idx) {
129  NLIB_ASSERT(idx < m_Count);
130  return m_Value[idx];
131  }
132  const T& operator[](size_t idx) const {
133  NLIB_ASSERT(idx < m_Count);
134  return m_Value[idx];
135  }
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;
140  }
141  void Reset() NLIB_NOEXCEPT;
142  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
143  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
144 
145  private:
146  uint32_t m_Count;
147  UniquePtr<T[]> m_Value;
148  NLIB_DISALLOW_COPY_AND_ASSIGN(PlainArray32);
149 };
150 
151 template <class T>
152 bool PlainArray32<T>::Init(uint32_t count) NLIB_NOEXCEPT {
153  if (m_Value) return false;
154  if (count == 0) {
155  m_Count = 0;
156  return true;
157  }
158  m_Value.reset(new (std::nothrow) T[count]);
159  if (!m_Value) return false;
160  m_Count = count;
161  memset(m_Value.get(), 0, sizeof(T) * count);
162  return true;
163 }
164 
165 template <class T>
166 NLIB_ALWAYS_INLINE void PlainArray32<T>::Reset() NLIB_NOEXCEPT {
167  m_Count = 0;
168  m_Value.reset();
169 }
170 
171 template <class T>
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;
175  return true;
176 }
177 
178 template <class T>
179 bool PlainArray32<T>::Import(BinaryReader* r) NLIB_NOEXCEPT {
180  Resetter<PlainArray32<T> > rst(this);
181  if (!r->Read(&m_Count)) return false;
182  if (m_Count == 0) {
183  m_Value.reset();
184  return true;
185  }
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;
189  rst.Ok();
190  return true;
191 }
192 
193 class BitVector32 NLIB_FINAL {
194  public:
195  BitVector32() NLIB_NOEXCEPT : m_Size(0), m_BitVector() {}
196  NLIB_VIS_PUBLIC ~BitVector32() NLIB_NOEXCEPT;
197  NLIB_MOVE_MEMBER_HELPER_2(BitVector32, m_Size, m_BitVector);
198  void swap(BitVector32& rhs) NLIB_NOEXCEPT {
199  using std::swap;
200  swap(m_Size, rhs.m_Size);
201  swap(m_BitVector, rhs.m_BitVector);
202  }
203  NLIB_VIS_PUBLIC bool Init(uint32_t size) NLIB_NOEXCEPT;
204  bool TurnOn(uint32_t nth) NLIB_NOEXCEPT {
205  if (nth >= m_Size) return false;
206  SetBit(m_BitVector.get(), nth);
207  return true;
208  }
209  bool TurnOff(uint32_t nth) NLIB_NOEXCEPT {
210  if (nth >= m_Size) return false;
211  ResetBit(m_BitVector.get(), nth);
212  return true;
213  }
214  bool operator[](uint32_t nth) const NLIB_NOEXCEPT {
215  return nth < m_Size ? GetBit(m_BitVector.get(), nth) : false;
216  }
217  uint32_t Size() const NLIB_NOEXCEPT { return m_Size; }
218  const uint32_t* Data() const NLIB_NOEXCEPT {
219  return m_BitVector.get();
220  }
221  NLIB_VIS_PUBLIC void Reset() NLIB_NOEXCEPT;
222  NLIB_VIS_PUBLIC size_t MemSize() const NLIB_NOEXCEPT;
223  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
224  NLIB_VIS_PUBLIC bool Import(BinaryReader* r) NLIB_NOEXCEPT;
225 
226  private:
227  uint32_t m_Size; // m_Size is bit length
228  UniquePtr<uint32_t[]> m_BitVector;
229  NLIB_DISALLOW_COPY_AND_ASSIGN(BitVector32);
230 };
231 
232 // classic rank
233 // See http://codezine.jp/article/detail/260
234 class SbvRank NLIB_FINAL {
235  // LV-A has cumulative popCounts for each 256bits block.
236  // LV-B has popCounts in a 256bits block.
237  // We can calcuate 'rank' in O(1).
238  public:
239  SbvRank() NLIB_NOEXCEPT : m_LvA(), m_LvB() {}
240  NLIB_VIS_PUBLIC ~SbvRank() NLIB_NOEXCEPT;
241  NLIB_MOVE_MEMBER_HELPER_2(SbvRank, m_LvA, m_LvB);
242  void swap(SbvRank& rhs) NLIB_NOEXCEPT {
243  using std::swap;
244  swap(m_LvA, rhs.m_LvA);
245  swap(m_LvB, rhs.m_LvB);
246  }
247  NLIB_VIS_PUBLIC bool Build(const uint32_t* bv, uint32_t size) NLIB_NOEXCEPT;
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());
251  }
252  uint32_t Rank0(const uint32_t* bv, uint32_t pos) const NLIB_NOEXCEPT {
253  return pos + 1 - this->Rank1(bv, pos);
254  }
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));
260  return ans;
261  }
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));
267  return ans;
268  }
269  NLIB_VIS_PUBLIC void Reset() NLIB_NOEXCEPT;
270  NLIB_VIS_PUBLIC size_t MemSize(uint32_t size) const NLIB_NOEXCEPT;
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;
273 
274  private:
275  UniquePtr<uint32_t[]> m_LvA;
276  UniquePtr<uint8_t[]> m_LvB;
278 };
279 
280 // classic select:
281 // See http://codezine.jp/article/detail/260
282 class SbvSelect NLIB_FINAL {
283  public:
284  // We can calcuate 'select' in O(1).
285  SbvSelect() NLIB_NOEXCEPT {}
286  NLIB_VIS_PUBLIC ~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 {
289  using std::swap;
290  m_ClumpArray.swap(rhs.m_ClumpArray);
291  m_R.swap(rhs.m_R);
292  m_Q.swap(rhs.m_Q);
293  m_RankR.swap(rhs.m_RankR);
294  m_RankQ.swap(rhs.m_RankQ);
295  }
296  bool Build(const uint32_t* bv, uint32_t size) NLIB_NOEXCEPT;
297  NLIB_VIS_PUBLIC void Reset() NLIB_NOEXCEPT;
298  NLIB_VIS_PUBLIC int32_t Select(const Set& set, uint32_t nth) const NLIB_NOEXCEPT;
299  NLIB_VIS_PUBLIC size_t MemSize() const NLIB_NOEXCEPT;
300  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
301  NLIB_VIS_PUBLIC bool Import(BinaryReader* r) NLIB_NOEXCEPT;
302 
303  private:
304  PlainArray32<uint32_t> m_ClumpArray;
305  BitVector32 m_R;
306  BitVector32 m_Q;
307  SbvRank m_RankR;
308  SbvRank m_RankQ;
310 };
311 
312 } // namespace detail
313 
314 class Set NLIB_FINAL {
315  public:
316  typedef uint32_t IdxType;
317  Set() NLIB_NOEXCEPT : m_BVec(), m_Rank() {}
318  NLIB_VIS_PUBLIC ~Set() NLIB_NOEXCEPT;
319  NLIB_MOVE_MEMBER_HELPER_2(Set, m_BVec, m_Rank);
320  void swap(Set& rhs) NLIB_NOEXCEPT {
321  using std::swap;
322  m_BVec.swap(rhs.m_BVec);
323  m_Rank.swap(rhs.m_Rank);
324  }
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); }
328  NLIB_VIS_PUBLIC bool Build() NLIB_NOEXCEPT;
329  bool Has(uint32_t idx) const NLIB_NOEXCEPT { return m_BVec[idx]; }
330  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT {
331  // The values beyond the bit-vector are all 0.
332  uint32_t pos = idx < m_BVec.Size() ? idx : m_BVec.Size() - 1;
333  return m_Rank.Rank1(m_BVec.Data(), pos);
334  }
335  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT {
336  uint32_t rank1 = this->Rank1(idx);
337  return idx + 1 - rank1;
338  }
339  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT {
340  return m_Rank.Select1(m_BVec.Data(), m_BVec.Size(), nth);
341  }
342  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT {
343  return m_Rank.Select0(m_BVec.Data(), m_BVec.Size(), nth);
344  }
345  NLIB_VIS_PUBLIC size_t MemSize() const NLIB_NOEXCEPT;
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(); }
349  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
351 
352  private:
353  detail::BitVector32 m_BVec;
354  detail::SbvRank m_Rank;
356 };
357 
358 class Sbv NLIB_FINAL {
359  public:
360  typedef uint32_t IdxType;
361  Sbv() NLIB_NOEXCEPT {}
362  NLIB_VIS_PUBLIC ~Sbv() NLIB_NOEXCEPT;
363  NLIB_MOVE_MEMBER_HELPER_2(Sbv, m_Set, m_Select1);
364  void swap(Sbv& rhs) NLIB_NOEXCEPT {
365  using std::swap;
366  m_Set.swap(rhs.m_Set);
367  m_Select1.swap(rhs.m_Select1);
368  }
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); }
372  NLIB_VIS_PUBLIC bool Build() NLIB_NOEXCEPT;
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);
378  }
379  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT {
380  return m_Set.Select0(nth);
381  }
382  size_t MemSize() const NLIB_NOEXCEPT;
383  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT {
384  return m_Set.GetBitVectorSize();
385  }
386  const uint32_t* GetBitVector() const NLIB_NOEXCEPT {
387  return m_Set.GetBitVector();
388  }
389  void Reset() NLIB_NOEXCEPT {
390  m_Set.Reset();
391  m_Select1.Reset();
392  }
393  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
395 
396  private:
397  Set m_Set;
398  detail::SbvSelect m_Select1;
400 };
401 
402 class SparseSet NLIB_FINAL {
403  public:
404  // index is 64-bit and # of on-bits is 32-bit.
405  // In other words, rank is 64-bit index, and select is 32-bit index
406  typedef uint64_t IdxType;
407  SparseSet() NLIB_NOEXCEPT : m_BitVectorSize(0),
408  m_LowestIdx(0xFFFFFFFF),
409  m_HighestIdx(0),
410  m_NumOnBits(0),
411  m_Width(0),
412  m_BLen(0),
413  m_B() {}
414  NLIB_VIS_PUBLIC ~SparseSet() NLIB_NOEXCEPT;
415 #ifdef NLIB_CXX11_RVALUE_REFERENCES
416  SparseSet(SparseSet&& rhs) NLIB_NOEXCEPT :
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)) {}
421  SparseSet& operator=(SparseSet&& rhs) NLIB_NOEXCEPT {
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;
427  m_BLen = rhs.m_BLen;
428  m_B = std::move(rhs.m_B);
429  m_Sbv = std::move(rhs.m_Sbv);
430  return *this;
431  }
432 #endif
433  NLIB_VIS_PUBLIC bool Init(uint64_t bv_size) NLIB_NOEXCEPT;
434  NLIB_VIS_PUBLIC bool TurnOn(uint64_t idx) NLIB_NOEXCEPT;
435  NLIB_VIS_PUBLIC bool Build() NLIB_NOEXCEPT;
436  bool Has(uint64_t idx, uint32_t* rank) const NLIB_NOEXCEPT {
437  // called after Build()
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);
443  // if (select1 < 0) return false; // not possible
444  return idx == static_cast<uint64_t>(select1);
445  }
446  bool Has(uint64_t idx) const NLIB_NOEXCEPT {
447  return this->Has(idx, NULL);
448  }
449  NLIB_VIS_PUBLIC uint32_t Rank1(uint64_t idx) const NLIB_NOEXCEPT;
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);
453  }
454  NLIB_VIS_PUBLIC int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
455  NLIB_VIS_PUBLIC int64_t Select1Ex(uint32_t nth) const NLIB_NOEXCEPT;
456  NLIB_VIS_PUBLIC size_t MemSize() const NLIB_NOEXCEPT;
457  uint64_t GetBitVectorSize() const NLIB_NOEXCEPT {
458  return m_BitVectorSize;
459  }
460  NLIB_VIS_PUBLIC void Reset() NLIB_NOEXCEPT;
461  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
462  NLIB_VIS_PUBLIC bool Import(BinaryReader* r) NLIB_NOEXCEPT;
463  NLIB_VIS_PUBLIC void swap(SparseSet& rhs) NLIB_NOEXCEPT; // NOLINT
464 
465  private:
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];
474  b <<= 32;
475  b += m_B[idx];
476  return static_cast<uint32_t>((b >> ofs) & ((1 << num) - 1));
477  } else {
478  return (m_B[idx] >> ofs) & ((1 << num) - 1);
479  }
480  }
481 
482  private:
483  uint64_t m_BitVectorSize;
484  uint64_t m_LowestIdx;
485  uint64_t m_HighestIdx;
486  uint32_t m_NumOnBits;
487  uint32_t m_Width;
488  uint32_t m_BLen;
489  UniquePtr<uint32_t[]> m_B;
490  Sbv m_Sbv; // Set m_Sbv;
492 };
493 
494 /*
495 // GammaArray may be removed.
496 class GammaArray NLIB_FINAL {
497 public:
498  GammaArray() : m_Len(0), m_U(NULL), m_B(NULL) {}
499  ~GammaArray() { this->Reset(); }
500  bool Init(const uint32_t* values, uint32_t n);
501  uint32_t operator[](uint32_t idx) const;
502  size_t MemSize() const;
503  void Reset();
504  bool Export(BinaryWriter* w) const;
505  bool Import(BinaryReader* r);
506  void swap(GammaArray& rhs) { // NOLINT
507  using std::swap;
508  swap(m_Len, rhs.m_Len);
509  swap(m_U, rhs.m_U);
510  swap(m_B, rhs.m_B);
511  }
512 
513 private:
514  typedef SparseSet SetType;
515  uint32_t m_Len;
516  SetType* m_U;
517  detail::BitVector32* m_B;
518  NLIB_DISALLOW_COPY_AND_ASSIGN(GammaArray);
519 };
520 */
521 
522 class CompressedArray NLIB_FINAL {
523  static const size_t UNIT_SIZE = 64;
524 
525  public:
526  // cppcheck-suppress uninitMemberVar
527  CompressedArray() NLIB_NOEXCEPT : m_Header(), m_Data(), m_Idx(0) {}
528  NLIB_VIS_PUBLIC ~CompressedArray() NLIB_NOEXCEPT;
529  NLIB_MOVE_MEMBER_HELPER_3(CompressedArray, m_Header, m_Data, m_Idx);
530  void swap(CompressedArray& rhs) NLIB_NOEXCEPT {
531  using std::swap;
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]);
537  }
538  }
539  bool PushBack(uint32_t x) NLIB_NOEXCEPT {
540  m_Work[m_Idx++] = x;
541  if (m_Idx == UNIT_SIZE) return this->Build();
542  return true;
543  }
544  NLIB_VIS_PUBLIC uint32_t operator[](size_t idx) const NLIB_NOEXCEPT;
545  size_t Size() const NLIB_NOEXCEPT {
546  return m_Idx + m_Header.size() * UNIT_SIZE / 2;
547  }
548  NLIB_VIS_PUBLIC void Reset() NLIB_NOEXCEPT;
549  NLIB_VIS_PUBLIC size_t MemSize() const NLIB_NOEXCEPT;
550  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
551  NLIB_VIS_PUBLIC bool Import(BinaryReader* r) NLIB_NOEXCEPT;
552 
553  private:
554  NLIB_VIS_PUBLIC bool Build() NLIB_NOEXCEPT;
555  // Header:
556  // baseidx: index of m_Data(lower 27bits)
557  // k: bit width of diff data(upper 5bits)
558  // base: base value(uint32_t)
559 
560  // Data:
561  // UNIT_SIZE * kbit: diff data
562  ReallocVec<uint32_t> m_Header;
563  ReallocVec<uint32_t> m_Data;
564  uint8_t m_Idx;
565  uint32_t m_Work[UNIT_SIZE];
567 };
568 
569 class Map NLIB_FINAL {
570  typedef CompressedArray ArrayType;
571  typedef SparseSet SetType;
572 
573  public:
575  typedef std::pair<bool, uint32_t> FindType;
576  Map() NLIB_NOEXCEPT : m_Set(), m_Value() {}
577  ~Map() NLIB_NOEXCEPT {}
578  NLIB_MOVE_MEMBER_HELPER_2(Map, m_Set, m_Value);
579  void swap(Map& rhs) NLIB_NOEXCEPT {
580  m_Set.swap(rhs.m_Set);
581  m_Value.swap(rhs.m_Value);
582  }
583  bool Init(IdxType bv_size) NLIB_NOEXCEPT {
584  if (m_Value.Size() != 0) return false;
585  return m_Set.Init(bv_size);
586  }
587  bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
588  if (!m_Set.TurnOn(idx)) return false;
589  m_Value.PushBack(data);
590  return true;
591  }
592  bool Build() NLIB_NOEXCEPT { return m_Set.Build(); }
593  FindType Find(IdxType idx) NLIB_NOEXCEPT {
594  if (m_Set.Has(idx))
595  return std::make_pair(true, m_Value[m_Set.Rank1(idx) - 1]);
596  else
597  return std::make_pair(false, 0);
598  }
599  const FindType Find(IdxType idx) const NLIB_NOEXCEPT {
600  if (m_Set.Has(idx))
601  return std::make_pair(true, m_Value[m_Set.Rank1(idx) - 1]);
602  else
603  return std::make_pair(false, 0);
604  }
605  size_t MemSize() const NLIB_NOEXCEPT {
606  size_t value_size = m_Value.MemSize();
607  size_t set_size = m_Set.MemSize();
608  return value_size + set_size;
609  }
610  const SetType& GetKeys() const NLIB_NOEXCEPT { return m_Set; }
611  const ArrayType& GetValues() const NLIB_NOEXCEPT { return m_Value; }
612  void Reset() NLIB_NOEXCEPT {
613  m_Value.Reset();
614  m_Set.Reset();
615  }
616  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT {
617  if (!m_Value.Export(w)) return false;
618  if (!m_Set.Export(w)) return false;
619  return true;
620  }
621  bool Import(BinaryReader* r) NLIB_NOEXCEPT {
622  if (!m_Value.Import(r) || !m_Set.Import(r)) {
623  this->Reset();
624  return false;
625  }
626  return true;
627  }
628 
629  private:
630  SetType m_Set;
631  ArrayType m_Value;
633 };
634 
635 } // namespace succinct
636 NLIB_NAMESPACE_END
637 
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)
644 // NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::GammaArray)
645 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::CompressedArray)
646 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Map)
647 
648 NLIB_DEFINE_STD_SWAP_T_BEGIN4(nn, nlib, succinct, detail) // NOLINT
649 NLIB_DEFINE_STD_SWAP_T1(T, ::nlib_ns::succinct::detail::PlainArray32) // NOLINT
650 NLIB_DEFINE_STD_SWAP_T_END4(nn, nlib, succinct, detail) // NOLINT
651 
652 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
653 #undef NLIB_VIS_PUBLIC
654 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
655 #endif
656 
657 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Platform.h:2151
bool TurnOff(uint32_t idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: Sbv.h:327
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
Definition: Sbv.h:347
bool TurnOff(uint32_t idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: Sbv.h:371
Sbv() noexcept
コンストラクタです。
Definition: Sbv.h:361
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
uint32_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:360
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:335
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:126
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: Sbv.h:370
SparseSet(SparseSet &&rhs) noexcept
ムーブコンストラクタです。C++11の利用時に有効です。
Definition: Sbv.h:416
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:358
ストリームからバイナリファイルを読み込むクラスを定義しています。
FindType Find(IdxType idx) noexcept
キーを指定して連想配列から値を取得します。
Definition: Sbv.h:593
void swap(Map &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Sbv.h:579
bool Init(IdxType bv_size) noexcept
オブジェクトを初期化します。
Definition: Sbv.h:583
STL namespace.
void swap(Set &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Sbv.h:320
Set() noexcept
コンストラクタです。
Definition: Sbv.h:317
std::unique_ptrに相当するクラスが定義されています。
int32_t Select0(uint32_t nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: Sbv.h:342
bool Init(uint32_t bv_size) noexcept
オブジェクトを初期化します。
Definition: Sbv.h:369
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
Definition: Sbv.h:386
void swap(Sbv &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Sbv.h:364
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
Definition: Sbv.h:616
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: Sbv.h:326
int32_t Select1(uint32_t nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
Definition: Sbv.h:376
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Sbv.h:389
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
Definition: Sbv.h:605
CompressedArray() noexcept
コンストラクタです。
Definition: Sbv.h:527
int32_t Select0(uint32_t nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: Sbv.h:379
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Sbv.h:348
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:314
uint32_t Rank1(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:374
SparseSet() noexcept
コンストラクタです。
Definition: Sbv.h:407
uint32_t Rank0(uint64_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:450
追記可能な圧縮された整数配列です。
Definition: Sbv.h:522
共通して使われる機能やプラットフォームへの依存度が高い機能が実装されます。 nlib Platform APIs も御覧...
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:375
bool TurnOn(IdxType idx, uint32_t data) noexcept
キーと値を追加します。
Definition: Sbv.h:587
疎な64bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:402
SetType::IdxType IdxType
整数インデックスです。
Definition: Sbv.h:574
ストリームにバイナリファイルを書き込むクラスを定義しています。
size_t Size() const noexcept
配列の長さを取得します。
Definition: Sbv.h:545
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Sbv.h:612
SparseSet & operator=(SparseSet &&rhs) noexcept
ムーブ代入演算子です。C++11の利用時に有効です。
Definition: Sbv.h:421
開発環境別の設定が書かれるファイルです。
Rank/Select操作つきのビット列を扱うクラスが定義されています。
uint64_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:406
bool Build() noexcept
連想配列を構築します。
Definition: Sbv.h:592
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
Definition: Sbv.h:621
Map() noexcept
コンストラクタです。
Definition: Sbv.h:576
const ArrayType & GetValues() const noexcept
値の集合を取得します。
Definition: Sbv.h:611
#define NLIB_ALWAYS_INLINE
コンパイラに関数をインライン展開するように強く示します。
Definition: Platform_unix.h:59
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:13
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:51
整数から整数へのコンパクトなリードオンリーの連想配列です。
Definition: Sbv.h:569
const SetType & GetKeys() const noexcept
キーの集合を取得します。
Definition: Sbv.h:610
bool Has(uint64_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:446
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:117
bool Init(uint32_t bv_size) noexcept
オブジェクトを初期化します。
Definition: Sbv.h:325
const FindType Find(IdxType idx) const noexcept
キーを指定して連想配列から値を取得します。
Definition: Sbv.h:599
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:13
uint32_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:316
uint32_t Rank1(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:330
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:18
bool PushBack(uint32_t x) noexcept
データを追加します。64個単位の長さになるとデータを圧縮します。
Definition: Sbv.h:539
std::pair< bool, uint32_t > FindType
ブール値と整数のペアです。値が見つからなかった場合はブール値がfalseです。
Definition: Sbv.h:575
~Map() noexcept
デストラクタです。
Definition: Sbv.h:577
int32_t Select1(uint32_t nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
Definition: Sbv.h:339