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