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  NLIB_CEXPR Set() NLIB_NOEXCEPT : prv_(nullptr) {}
45  ~Set() NLIB_NOEXCEPT { Reset(); }
46  NLIB_DEFMOVE_PIMPL(Set);
47  NLIB_DEPRECATED void swap(Set& rhs) NLIB_NOEXCEPT;
48  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
49  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT;
50  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT;
51  bool Build() NLIB_NOEXCEPT;
52  bool Has(uint32_t idx) const NLIB_NOEXCEPT;
53  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT;
54  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT {
55  uint32_t rank1 = this->Rank1(idx);
56  return idx + 1 - rank1;
57  }
58  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
59  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT;
60  size_t MemSize() const NLIB_NOEXCEPT;
61  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT;
62  const uint32_t* GetBitVector() const NLIB_NOEXCEPT;
63  void Reset() NLIB_NOEXCEPT;
64  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT NLIB_NONNULL;
65  bool Import(BinaryReader* r) NLIB_NOEXCEPT NLIB_NONNULL;
66 
67  private:
68  struct SetPrivate;
69  mutable SetPrivate* prv_;
71 };
72 
74  public:
75  typedef uint32_t IdxType;
76  NLIB_CEXPR Sbv() NLIB_NOEXCEPT : prv_(nullptr) {}
77  ~Sbv() NLIB_NOEXCEPT { Reset(); }
78 #ifdef __cpp_rvalue_references
79  Sbv(Sbv&& rhs) NLIB_NOEXCEPT : prv_(rhs.prv_), set_(std::move(rhs.set_)) {
80  rhs.prv_ = nullptr;
81  }
83  set_ = std::move(rhs.set_);
84  prv_ = rhs.prv_;
85  rhs.prv_ = nullptr;
86  return *this;
87  }
88 #endif
89  Sbv(Sbv& rhs, move_tag) NLIB_NOEXCEPT : prv_(rhs.prv_), set_(rhs.set_, move_tag()) { // NOLINT
90  rhs.prv_ = nullptr;
91  }
92  Sbv& assign(Sbv& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
93  rhs.set_.assign(rhs.set_, move_tag());
94  prv_ = rhs.prv_;
95  rhs.prv_ = nullptr;
96  return *this;
97  }
98  NLIB_DEPRECATED void swap(Sbv& rhs) NLIB_NOEXCEPT;
99  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
100  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOn(idx); }
101  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOff(idx); }
102  bool Build() NLIB_NOEXCEPT;
103  bool Has(uint32_t idx) const NLIB_NOEXCEPT { return set_.Has(idx); }
104  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT { return set_.Rank1(idx); }
105  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT { return set_.Rank0(idx); }
106  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
107  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT { return set_.Select0(nth); }
108  size_t MemSize() const NLIB_NOEXCEPT;
109  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT { return set_.GetBitVectorSize(); }
110  const uint32_t* GetBitVector() const NLIB_NOEXCEPT { return set_.GetBitVector(); }
111  void Reset() NLIB_NOEXCEPT;
112  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
113  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
114 
115  private:
116  struct SbvPrivate;
117  SbvPrivate* prv_;
118  Set set_;
120 };
121 
123  public:
124  // index is 64-bit and # of on-bits is 32-bit.
125  // In other words, rank is 64-bit index, and select is 32-bit index
126  typedef uint64_t IdxType;
128  : bitvector_size_(0), lowest_idx_(0xFFFFFFFF), highest_idx_(0), num_on_bits_(0),
129  width_(0), blen_(0), b_(nullptr) {}
130  ~SparseSet() NLIB_NOEXCEPT { Reset(); }
131 #ifdef __cpp_rvalue_references
133  SparseSet& operator=(SparseSet&& rhs) NLIB_NOEXCEPT;
134 #endif
135  SparseSet(SparseSet& rhs, move_tag) NLIB_NOEXCEPT; // NOLINT
136  SparseSet& assign(SparseSet& rhs, move_tag) NLIB_NOEXCEPT; // NOLINT
137  NLIB_DEPRECATED void swap(SparseSet& rhs) NLIB_NOEXCEPT; // NOLINT
138  bool Init(uint64_t bv_size) NLIB_NOEXCEPT;
139  bool TurnOn(uint64_t idx) NLIB_NOEXCEPT;
140  bool Build() NLIB_NOEXCEPT;
141  bool Has(uint64_t idx, uint32_t* rank) const NLIB_NOEXCEPT {
142  // called after Build()
143  uint32_t rank1 = this->Rank1(idx);
144  if (rank) *rank = rank1;
145  if (rank1 == 0) return false;
146  int64_t select1 = this->Select1Ex(rank1 - 1);
147  NLIB_ASSERT(select1 >= 0);
148  // if (select1 < 0) return false; // not possible
149  return idx == static_cast<uint64_t>(select1);
150  }
151  bool Has(uint64_t idx) const NLIB_NOEXCEPT {
152  return this->Has(idx, nullptr);
153  }
154  uint32_t Rank1(uint64_t idx) const NLIB_NOEXCEPT;
155  uint32_t Rank0(uint64_t idx) const NLIB_NOEXCEPT {
156  uint32_t rank1 = this->Rank1(idx);
157  return static_cast<uint32_t>(idx + 1 - rank1);
158  }
159  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
160  int64_t Select1Ex(uint32_t nth) const NLIB_NOEXCEPT;
161  size_t MemSize() const NLIB_NOEXCEPT;
162  uint64_t GetBitVectorSize() const NLIB_NOEXCEPT {
163  return bitvector_size_;
164  }
165  void Reset() NLIB_NOEXCEPT;
166  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
167  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
168 
169  private:
170  uint32_t GetBits(uint64_t pos, size_t num) const NLIB_NOEXCEPT {
171  NLIB_ASSERT(num <= 32);
172  uint64_t idx64 = pos / detail::BLK_SIZE;
173  NLIB_ASSERT(idx64 <= SIZE_MAX);
174  size_t idx = static_cast<size_t>(idx64);
175  size_t ofs = static_cast<size_t>(pos % detail::BLK_SIZE);
176  if (ofs + num > 32) {
177  uint64_t b = b_[idx + 1];
178  b <<= 32;
179  b += b_[idx];
180  return static_cast<uint32_t>((b >> ofs) & ((1 << num) - 1));
181  } else {
182  return (b_[idx] >> ofs) & ((1 << num) - 1);
183  }
184  }
185 
186  private:
187  uint64_t bitvector_size_;
188  uint64_t lowest_idx_;
189  uint64_t highest_idx_;
190  uint32_t num_on_bits_;
191  uint32_t width_;
192  uint32_t blen_;
193  uint32_t* b_;
194  Sbv sbv_; // Set sbv_;
196 };
197 
199  static const size_t UNIT_SIZE = 64;
200 
201  public:
203  : header_(nullptr), data_(nullptr), header_size_(0), header_capacity_(0),
204  data_size_(0), data_capacity_(0), workidx_(0), work_() {}
207  CompressedArray& assign(CompressedArray &rhs, move_tag) NLIB_NOEXCEPT; // NOLINT
208 #ifdef __cpp_rvalue_references
211 #endif
213  bool PushBack(uint32_t x) NLIB_NOEXCEPT {
214  work_[workidx_++] = x;
215  if (workidx_ == UNIT_SIZE) return this->Build();
216  return true;
217  }
218  uint32_t operator[](size_t idx) const NLIB_NOEXCEPT;
219  size_t Size() const NLIB_NOEXCEPT {
220  return workidx_ + header_capacity_ * UNIT_SIZE / 2;
221  }
222  void Reset() NLIB_NOEXCEPT;
223  size_t MemSize() const NLIB_NOEXCEPT;
224  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
225  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
226 
227  private:
228  bool Build() NLIB_NOEXCEPT;
229  // Header:
230  // baseidx: index of data_(lower 27bits)
231  // k: bit width of diff data(upper 5bits)
232  // base: base value(uint32_t)
233 
234  // Data:
235  // UNIT_SIZE * kbit: diff data
236  uint32_t* header_;
237  uint32_t* data_;
238  uint32_t header_size_;
239  uint32_t header_capacity_;
240  uint32_t data_size_;
241  uint32_t data_capacity_;
242  uint8_t workidx_;
243  uint32_t work_[UNIT_SIZE];
245 };
246 
248  typedef CompressedArray ArrayType;
249  typedef SparseSet SetType;
250 
251  public:
253  typedef std::pair<bool, uint32_t> FindType;
254  NLIB_CEXPR Map() NLIB_NOEXCEPT : set_(), value_() {}
256 #ifdef __cpp_rvalue_references
257 #ifdef NLIB_CXX11_DEFAULTED_AND_DELETED_FUNCTIONS
258  Map(Map&& rhs) = default;
259  Map& operator=(Map&& rhs) = default;
260 #else
261  Map(Map&& rhs) NLIB_NOEXCEPT : set_(std::move(rhs.set_)), value_(std::move(rhs.value_)) {}
262  Map& operator=(Map&& rhs) NLIB_NOEXCEPT {
263  set_ = std::move(rhs.set_);
264  value_ = std::move(rhs.value_);
265  return *this;
266  }
267 #endif
268 #endif
269  Map(Map& rhs, move_tag) NLIB_NOEXCEPT // NOLINT
270  : set_(rhs.set_, move_tag()), value_(rhs.value_, move_tag()) {}
271  Map& assign(Map& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
272  set_.assign(rhs.set_, move_tag());
273  value_.assign(rhs.value_, move_tag());
274  return *this;
275  }
276  NLIB_DEPRECATED void swap(Map& rhs) NLIB_NOEXCEPT;
277  bool Init(IdxType bv_size) NLIB_NOEXCEPT {
278  if (value_.Size() != 0) return false;
279  return set_.Init(bv_size);
280  }
281  bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
282  if (!set_.TurnOn(idx)) return false;
283  value_.PushBack(data);
284  return true;
285  }
286  bool Build() NLIB_NOEXCEPT { return set_.Build(); }
287  FindType Find(IdxType idx) NLIB_NOEXCEPT {
288  if (set_.Has(idx))
289  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
290  else
291  return std::make_pair(false, 0);
292  }
293  const FindType Find(IdxType idx) const NLIB_NOEXCEPT {
294  if (set_.Has(idx))
295  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
296  else
297  return std::make_pair(false, 0);
298  }
299  size_t MemSize() const NLIB_NOEXCEPT {
300  size_t value_size = value_.MemSize();
301  size_t set_size = set_.MemSize();
302  return value_size + set_size;
303  }
304  const SetType& GetKeys() const NLIB_NOEXCEPT { return set_; }
305  const ArrayType& GetValues() const NLIB_NOEXCEPT { return value_; }
306  void Reset() NLIB_NOEXCEPT {
307  value_.Reset();
308  set_.Reset();
309  }
310  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT {
311  if (!value_.Export(w)) return false;
312  if (!set_.Export(w)) return false;
313  return true;
314  }
315  bool Import(BinaryReader* r) NLIB_NOEXCEPT {
316  if (!value_.Import(r) || !set_.Import(r)) {
317  this->Reset();
318  return false;
319  }
320  return true;
321  }
322 
323  private:
324  SetType set_;
325  ArrayType value_;
327 };
328 
329 } // namespace succinct
330 NLIB_NAMESPACE_END
331 
332 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Set)
333 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Sbv)
334 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::SparseSet)
335 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::CompressedArray)
336 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Map)
337 
338 NLIB_NAMESPACE_BEGIN
339 namespace succinct {
340 inline void Set::swap(Set& rhs) NLIB_NOEXCEPT {
341  using std::swap;
342  swap(prv_, rhs.prv_);
343 }
344 inline void Sbv::swap(Sbv& rhs) NLIB_NOEXCEPT {
345  using std::swap;
346  swap(set_, rhs.set_);
347  swap(prv_, rhs.prv_);
348 }
349 inline void Map::swap(Map& rhs) NLIB_NOEXCEPT {
350  using std::swap;
351  swap(set_, rhs.set_);
352  swap(value_, rhs.value_);
353 }
354 } // namespace succinct
355 NLIB_NAMESPACE_END
356 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
357 #undef NLIB_VIS_PUBLIC
358 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
359 #endif
360 
361 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
uint32_t Rank1(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:104
~Sbv() noexcept
デストラクタです。
Definition: Sbv.h:77
bool TurnOff(uint32_t idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: Sbv.h:101
constexpr Sbv() noexcept
コンストラクタです。
Definition: Sbv.h:76
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
uint32_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:75
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
Definition: Sbv.h:299
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:179
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: Sbv.h:100
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:73
ストリームからバイナリファイルを読み込むクラスを定義しています。
int32_t Select0(uint32_t nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: Sbv.h:107
FindType Find(IdxType idx) noexcept
キーを指定して連想配列から値を取得します。
Definition: Sbv.h:287
bool Has(uint64_t idx, uint32_t *rank) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:141
bool Init(IdxType bv_size) noexcept
オブジェクトを初期化します。
Definition: Sbv.h:277
~CompressedArray() noexcept
デストラクタです。
Definition: Sbv.h:205
bool Has(uint32_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:103
uint32_t Rank0(uint64_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:155
constexpr Set() noexcept
コンストラクタです。
Definition: Sbv.h:44
Map & assign(Map &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Definition: Sbv.h:271
Sbv & assign(Sbv &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Definition: Sbv.h:92
#define NLIB_DEPRECATED
関数等がdeprecatedになったことを示します。
Definition: Config.h:109
Sbv & operator=(Sbv &&rhs) noexcept
ムーブ代入演算子です。C++11の利用時に有効です。
Definition: Sbv.h:82
~SparseSet() noexcept
デストラクタです。
Definition: Sbv.h:130
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:89
const SetType & GetKeys() const noexcept
キーの集合を取得します。
Definition: Sbv.h:304
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
Definition: Sbv.h:310
constexpr CompressedArray() noexcept
コンストラクタです。
Definition: Sbv.h:202
Map(Map &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
Definition: Sbv.h:269
const ArrayType & GetValues() const noexcept
値の集合を取得します。
Definition: Sbv.h:305
uint32_t Rank0(uint32_t idx) const noexcept
Rank操作を行います。
Definition: Sbv.h:54
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:41
Sbv(Sbv &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
Definition: Sbv.h:89
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:265
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
Definition: Sbv.h:110
constexpr SparseSet() noexcept
コンストラクタです。
Definition: Sbv.h:127
~Set() noexcept
デストラクタです。
Definition: Sbv.h:45
uint64_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
Definition: Sbv.h:162
追記可能な圧縮された整数配列です。
Definition: Sbv.h:198
bool TurnOn(IdxType idx, uint32_t data) noexcept
キーと値を追加します。
Definition: Sbv.h:281
疎な64bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:122
SetType::IdxType IdxType
整数インデックスです。
Definition: Sbv.h:252
ストリームにバイナリファイルを書き込むクラスを定義しています。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:105
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Sbv.h:306
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:107
bool Has(uint64_t idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: Sbv.h:151
開発環境別の設定が書かれるファイルです。
Rank/Select操作つきのビット列を扱うクラスが定義されています。
uint64_t IdxType
インデックスとなる整数型のtypedefです。
Definition: Sbv.h:126
Sbv(Sbv &&rhs) noexcept
ムーブコンストラクタです。C++11の利用時に有効です。
Definition: Sbv.h:79
bool Build() noexcept
連想配列を構築します。
Definition: Sbv.h:286
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
Definition: Sbv.h:315
constexpr Map() noexcept
コンストラクタです。
Definition: Sbv.h:254
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
整数から整数へのコンパクトなリードオンリーの連想配列です。
Definition: Sbv.h:247
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:245
const FindType Find(IdxType idx) const noexcept
キーを指定して連想配列から値を取得します。
Definition: Sbv.h:293
ストリーム(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:105
size_t Size() const noexcept
配列の長さを取得します。
Definition: Sbv.h:219
#define NLIB_NONNULL
全ての引数にNULLを指定することができないことを示します。
uint32_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
Definition: Sbv.h:109
bool PushBack(uint32_t x) noexcept
データを追加します。64個単位の長さになるとデータを圧縮します。
Definition: Sbv.h:213
std::pair< bool, uint32_t > FindType
ブール値と整数のペアです。値が見つからなかった場合はブール値がfalseです。
Definition: Sbv.h:253
~Map() noexcept
デストラクタです。
Definition: Sbv.h:255