nlib
Sbv.h
[詳解]
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
18 
19 #include <string.h>
20 #include <utility>
21 
22 #include "nn/nlib/Config.h"
23 #include "nn/nlib/Swap.h"
24 #include "nn/nlib/SmartBitmap.h"
25 #include "nn/nlib/BinaryReader.h"
26 #include "nn/nlib/BinaryWriter.h"
27 #include "nn/nlib/TypeTraits.h"
28 
29 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
30 #undef NLIB_VIS_PUBLIC
31 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
32 #endif
33 
34 NLIB_NAMESPACE_BEGIN
35 namespace succinct {
36 
37 namespace detail {
38 static const unsigned int BLK_SIZE = 32;
39 } // namespace detail
40 
42  public:
43  typedef uint32_t IdxType;
44  Set() NLIB_NOEXCEPT : prv_(NULL) {}
45  ~Set() NLIB_NOEXCEPT;
46  NLIB_MOVE_MEMBER_HELPER_1(Set, prv_);
47  void swap(Set& rhs) NLIB_NOEXCEPT {
48  SetPrivate* tmp = rhs.prv_;
49  rhs.prv_ = prv_;
50  prv_ = tmp;
51  }
52  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
53  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT;
54  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT;
55  bool Build() NLIB_NOEXCEPT;
56  bool Has(uint32_t idx) const NLIB_NOEXCEPT;
57  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT;
58  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT {
59  uint32_t rank1 = this->Rank1(idx);
60  return idx + 1 - rank1;
61  }
62  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
63  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT;
64  size_t MemSize() const NLIB_NOEXCEPT;
65  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT;
66  const uint32_t* GetBitVector() const NLIB_NOEXCEPT;
67  void Reset() NLIB_NOEXCEPT;
68  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT NLIB_NONNULL;
69  bool Import(BinaryReader* r) NLIB_NOEXCEPT NLIB_NONNULL;
70 
71  private:
72  struct SetPrivate;
73  mutable SetPrivate* prv_;
75 };
76 
78  public:
79  typedef uint32_t IdxType;
80  Sbv() NLIB_NOEXCEPT : prv_(NULL) {}
81  ~Sbv() NLIB_NOEXCEPT;
82  NLIB_MOVE_MEMBER_HELPER_2(Sbv, prv_, set_);
83  void swap(Sbv& rhs) NLIB_NOEXCEPT {
84  using std::swap;
85  set_.swap(rhs.set_);
86  SbvPrivate* tmp = rhs.prv_;
87  rhs.prv_ = prv_;
88  prv_ = tmp;
89  }
90  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
91  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOn(idx); }
92  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOff(idx); }
93  bool Build() NLIB_NOEXCEPT;
94  bool Has(uint32_t idx) const NLIB_NOEXCEPT { return set_.Has(idx); }
95  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT { return set_.Rank1(idx); }
96  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT { return set_.Rank0(idx); }
97  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
98  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT { return set_.Select0(nth); }
99  size_t MemSize() const NLIB_NOEXCEPT;
100  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT { return set_.GetBitVectorSize(); }
101  const uint32_t* GetBitVector() const NLIB_NOEXCEPT { return set_.GetBitVector(); }
102  void Reset() NLIB_NOEXCEPT;
103  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
104  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
105 
106  private:
107  struct SbvPrivate;
108  SbvPrivate* prv_;
109  Set set_;
111 };
112 
114  public:
115  // index is 64-bit and # of on-bits is 32-bit.
116  // In other words, rank is 64-bit index, and select is 32-bit index
117  typedef uint64_t IdxType;
118  SparseSet() NLIB_NOEXCEPT : bitvector_size_(0),
119  lowest_idx_(0xFFFFFFFF),
120  highest_idx_(0),
121  num_on_bits_(0),
122  width_(0),
123  blen_(0),
124  b_(NULL) {}
126 #ifdef NLIB_CXX11_RVALUE_REFERENCES
128  SparseSet& operator=(SparseSet&& rhs) NLIB_NOEXCEPT;
129 #endif
130  bool Init(uint64_t bv_size) NLIB_NOEXCEPT;
131  bool TurnOn(uint64_t idx) NLIB_NOEXCEPT;
132  bool Build() NLIB_NOEXCEPT;
133  bool Has(uint64_t idx, uint32_t* rank) const NLIB_NOEXCEPT {
134  // called after Build()
135  uint32_t rank1 = this->Rank1(idx);
136  if (rank) *rank = rank1;
137  if (rank1 == 0) return false;
138  int64_t select1 = this->Select1Ex(rank1 - 1);
139  NLIB_ASSERT(select1 >= 0);
140  // if (select1 < 0) return false; // not possible
141  return idx == static_cast<uint64_t>(select1);
142  }
143  bool Has(uint64_t idx) const NLIB_NOEXCEPT {
144  return this->Has(idx, NULL);
145  }
146  uint32_t Rank1(uint64_t idx) const NLIB_NOEXCEPT;
147  uint32_t Rank0(uint64_t idx) const NLIB_NOEXCEPT {
148  uint32_t rank1 = this->Rank1(idx);
149  return static_cast<uint32_t>(idx + 1 - rank1);
150  }
151  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
152  int64_t Select1Ex(uint32_t nth) const NLIB_NOEXCEPT;
153  size_t MemSize() const NLIB_NOEXCEPT;
154  uint64_t GetBitVectorSize() const NLIB_NOEXCEPT {
155  return bitvector_size_;
156  }
157  void Reset() NLIB_NOEXCEPT;
158  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
159  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
160  void swap(SparseSet& rhs) NLIB_NOEXCEPT; // NOLINT
161 
162  private:
163  uint32_t GetBits(uint64_t pos, size_t num) const NLIB_NOEXCEPT {
164  NLIB_ASSERT(num <= 32);
165  uint64_t idx64 = pos / detail::BLK_SIZE;
166  NLIB_ASSERT(idx64 <= SIZE_MAX);
167  size_t idx = static_cast<size_t>(idx64);
168  size_t ofs = static_cast<size_t>(pos % detail::BLK_SIZE);
169  if (ofs + num > 32) {
170  uint64_t b = b_[idx + 1];
171  b <<= 32;
172  b += b_[idx];
173  return static_cast<uint32_t>((b >> ofs) & ((1 << num) - 1));
174  } else {
175  return (b_[idx] >> ofs) & ((1 << num) - 1);
176  }
177  }
178 
179  private:
180  uint64_t bitvector_size_;
181  uint64_t lowest_idx_;
182  uint64_t highest_idx_;
183  uint32_t num_on_bits_;
184  uint32_t width_;
185  uint32_t blen_;
186  uint32_t* b_;
187  Sbv sbv_; // Set sbv_;
189 };
190 
192  static const size_t UNIT_SIZE = 64;
193 
194  public:
196  : header_(NULL), data_(NULL), header_size_(0), header_capacity_(0),
197  data_size_(0), data_capacity_(0), workidx_(0) {}
200  CompressedArray& assign(CompressedArray &rhs, move_tag) NLIB_NOEXCEPT; // NOLINT
201 #ifdef NLIB_CXX11_RVALUE_REFERENCES
204 #endif
205  // NLIB_MOVE_MEMBER_HELPER_3(CompressedArray, header_, data_, workidx_);
206  void swap(CompressedArray& rhs) NLIB_NOEXCEPT;
207  bool PushBack(uint32_t x) NLIB_NOEXCEPT {
208  work_[workidx_++] = x;
209  if (workidx_ == UNIT_SIZE) return this->Build();
210  return true;
211  }
212  uint32_t operator[](size_t idx) const NLIB_NOEXCEPT;
213  size_t Size() const NLIB_NOEXCEPT {
214  return workidx_ + header_capacity_ * UNIT_SIZE / 2;
215  }
216  void Reset() NLIB_NOEXCEPT;
217  size_t MemSize() const NLIB_NOEXCEPT;
218  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
219  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
220 
221  private:
222  bool Build() NLIB_NOEXCEPT;
223  // Header:
224  // baseidx: index of data_(lower 27bits)
225  // k: bit width of diff data(upper 5bits)
226  // base: base value(uint32_t)
227 
228  // Data:
229  // UNIT_SIZE * kbit: diff data
230  uint32_t* header_;
231  uint32_t* data_;
232  uint32_t header_size_;
233  uint32_t header_capacity_;
234  uint32_t data_size_;
235  uint32_t data_capacity_;
236  uint8_t workidx_;
237  uint32_t work_[UNIT_SIZE];
239 };
240 
242  typedef CompressedArray ArrayType;
243  typedef SparseSet SetType;
244 
245  public:
247  typedef std::pair<bool, uint32_t> FindType;
248  Map() NLIB_NOEXCEPT : set_(), value_() {}
250  NLIB_MOVE_MEMBER_HELPER_2(Map, set_, value_);
251  void swap(Map& rhs) NLIB_NOEXCEPT {
252  set_.swap(rhs.set_);
253  value_.swap(rhs.value_);
254  }
255  bool Init(IdxType bv_size) NLIB_NOEXCEPT {
256  if (value_.Size() != 0) return false;
257  return set_.Init(bv_size);
258  }
259  bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
260  if (!set_.TurnOn(idx)) return false;
261  value_.PushBack(data);
262  return true;
263  }
264  bool Build() NLIB_NOEXCEPT { return set_.Build(); }
265  FindType Find(IdxType idx) NLIB_NOEXCEPT {
266  if (set_.Has(idx))
267  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
268  else
269  return std::make_pair(false, 0);
270  }
271  const FindType Find(IdxType idx) const NLIB_NOEXCEPT {
272  if (set_.Has(idx))
273  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
274  else
275  return std::make_pair(false, 0);
276  }
277  size_t MemSize() const NLIB_NOEXCEPT {
278  size_t value_size = value_.MemSize();
279  size_t set_size = set_.MemSize();
280  return value_size + set_size;
281  }
282  const SetType& GetKeys() const NLIB_NOEXCEPT { return set_; }
283  const ArrayType& GetValues() const NLIB_NOEXCEPT { return value_; }
285  value_.Reset();
286  set_.Reset();
287  }
289  if (!value_.Export(w)) return false;
290  if (!set_.Export(w)) return false;
291  return true;
292  }
294  if (!value_.Import(r) || !set_.Import(r)) {
295  this->Reset();
296  return false;
297  }
298  return true;
299  }
300 
301  private:
302  SetType set_;
303  ArrayType value_;
305 };
306 
307 } // namespace succinct
308 NLIB_NAMESPACE_END
309 
310 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Set)
311 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Sbv)
312 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::SparseSet)
313 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::CompressedArray)
314 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Map)
315 
316 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
317 #undef NLIB_VIS_PUBLIC
318 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
319 #endif
320 
321 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
uint32_t Rank1(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:95
bool TurnOff(uint32_t idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: Sbv.h:92
Sbv() noexcept
コンストラクタです。
Definition: Sbv.h:80
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
uint32_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:79
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
Definition: Sbv.h:277
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:163
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: Sbv.h:91
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:77
ストリームからバイナリファイルを読み込むクラスを定義しています。
int32_t Select0(uint32_t nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: Sbv.h:98
FindType Find(IdxType idx) noexcept
キーを指定して連想配列から値を取得します。
Definition: Sbv.h:265
bool Has(uint64_t idx, uint32_t *rank) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:133
void swap(Map &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Sbv.h:251
bool Init(IdxType bv_size) noexcept
オブジェクトを初期化します。
Definition: Sbv.h:255
bool Has(uint32_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:94
void swap(Set &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Sbv.h:47
uint32_t Rank0(uint64_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:147
Set() noexcept
コンストラクタです。
Definition: Sbv.h:44
void swap(Sbv &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Sbv.h:83
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:89
const SetType & GetKeys() const noexcept
キーの集合を取得します。
Definition: Sbv.h:282
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
Definition: Sbv.h:288
CompressedArray() noexcept
コンストラクタです。
Definition: Sbv.h:195
const ArrayType & GetValues() const noexcept
値の集合を取得します。
Definition: Sbv.h:283
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:58
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:41
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:249
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
Definition: Sbv.h:101
SparseSet() noexcept
コンストラクタです。
Definition: Sbv.h:118
uint64_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
Definition: Sbv.h:154
追記可能な圧縮された整数配列です。
Definition: Sbv.h:191
bool TurnOn(IdxType idx, uint32_t data) noexcept
キーと値を追加します。
Definition: Sbv.h:259
疎な64bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:113
SetType::IdxType IdxType
整数インデックスです。
Definition: Sbv.h:246
ストリームにバイナリファイルを書き込むクラスを定義しています。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:99
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Sbv.h:284
bool Has(uint64_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:143
開発環境別の設定が書かれるファイルです。
Rank/Select操作つきのビット列を扱うクラスが定義されています。
uint64_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:117
bool Build() noexcept
連想配列を構築します。
Definition: Sbv.h:264
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
Definition: Sbv.h:293
Map() noexcept
コンストラクタです。
Definition: Sbv.h:248
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
整数から整数へのコンパクトなリードオンリーの連想配列です。
Definition: Sbv.h:241
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:229
const FindType Find(IdxType idx) const noexcept
キーを指定して連想配列から値を取得します。
Definition: Sbv.h:271
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
uint32_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:43
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:96
size_t Size() const noexcept
配列の長さを取得します。
Definition: Sbv.h:213
#define NLIB_NONNULL
全ての引数にNULLを指定することができないことを示します。
uint32_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
Definition: Sbv.h:100
bool PushBack(uint32_t x) noexcept
データを追加します。64個単位の長さになるとデータを圧縮します。
Definition: Sbv.h:207
std::pair< bool, uint32_t > FindType
ブール値と整数のペアです。値が見つからなかった場合はブール値がfalseです。
Definition: Sbv.h:247
~Map() noexcept
デストラクタです。
Definition: Sbv.h:249