nlib
Bp.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_BP_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_BP_H_
18 
19 #include "nn/nlib/succinct/Sbv.h"
20 #include "nn/nlib/ReallocVec.h"
21 
22 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
23 #undef NLIB_VIS_PUBLIC
24 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
25 #endif
26 
27 NLIB_NAMESPACE_BEGIN
28 namespace succinct {
29 
31  public:
32  NLIB_CEXPR Bp() NLIB_NOEXCEPT : prv_(nullptr) {}
33  ~Bp() NLIB_NOEXCEPT { Reset(); }
34  NLIB_DEFMOVE_PIMPL(Bp);
36  BpPrivate* tmp = rhs.prv_;
37  rhs.prv_ = prv_;
38  prv_ = tmp;
39  }
40  template <class TREEITER>
41  bool Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
42  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
43  int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
44  int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
45  int FindOpen(uint32_t pos) const NLIB_NOEXCEPT;
46  int FindClose(uint32_t pos) const NLIB_NOEXCEPT;
47  int Enclose(uint32_t pos) const NLIB_NOEXCEPT;
48  int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
49  int LastChild(uint32_t pos) const NLIB_NOEXCEPT;
50  int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
51  int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
52  int Parent(uint32_t pos) const NLIB_NOEXCEPT { return this->Enclose(pos); }
53  size_t MemSize() const NLIB_NOEXCEPT;
54  void Reset() NLIB_NOEXCEPT;
55  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
56  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
57 
58  private:
59  Set* Get1stLevelSet() NLIB_NOEXCEPT;
60  bool Build(const uint32_t* bv, uint32_t bvsize) NLIB_NOEXCEPT;
61 
62  private:
63  struct BpPrivate;
64  BpPrivate* prv_;
66 };
67 
68 template <class TREEITER>
69 bool Bp::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
70  // TREEITER has following methods:
71  // const void* NodePtr(); // ptr to node
72  // const void* ParentNodePtr(); // ptr to parent node
73  // bool MoveNext(); // move to the next node by depth first search
74  if (num_nodes >= 0x80000000) return false;
75  if (prv_) return false;
76  Set* bv = Get1stLevelSet(); // bv = &bp_.b_
77  if (!bv) {
78  this->Reset();
79  return false;
80  }
81  bv->Init(num_nodes * 2);
82 
83  uint32_t idx = 0;
85  do {
86  const void* parent = iter.ParentNodePtr();
87  const void* node = iter.NodePtr();
88  if (stack.empty() || stack.back() == parent) {
89  bv->TurnOn(idx++);
90  if (!stack.push_back(node)) {
91  this->Reset();
92  return false;
93  }
94  } else {
95  while (stack.back() != parent) {
96  stack.pop_back();
97  ++idx;
98  }
99  bv->TurnOn(idx++);
100  if (!stack.push_back(node)) {
101  this->Reset();
102  return false;
103  }
104  }
105  } while (iter.MoveNext());
106 
107  if (!this->Build(bv->GetBitVector(), bv->GetBitVectorSize())) {
108  this->Reset();
109  return false;
110  }
111  return true;
112 }
113 
114 } // namespace succinct
115 NLIB_NAMESPACE_END
116 
117 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Bp)
118 
119 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
120 #undef NLIB_VIS_PUBLIC
121 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
122 #endif
123 
124 #endif // INCLUDE_NN_NLIB_SUCCINCT_BP_H_
rank/select操作をベースとした基本的なクラスが定義されています。
bool push_back(const T &v) noexcept
ベクタに要素を追加します。
Definition: ReallocVec.h:101
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:179
uint32_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
#define NLIB_DEPRECATED
関数等がdeprecatedになったことを示します。
Definition: Config.h:109
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:89
~Bp() noexcept
デストラクタです。
Definition: Bp.h:33
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
T & back()
最後の要素を取得します。
Definition: ReallocVec.h:119
bool pop_back() noexcept
ベクタの末尾から要素を削除します。
Definition: ReallocVec.h:110
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:41
各種操作を で行うことができるコンパクトなツリー構造です。
Definition: Bp.h:30
bool empty() const noexcept
ベクタが空かどうかを判定する
Definition: ReallocVec.h:144
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:105
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:107
void swap(Bp &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Bp.h:35
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:245
constexpr Bp() noexcept
コンストラクタです。
Definition: Bp.h:32
bool Init(uint32_t bv_size) noexcept
オブジェクトを初期化します。
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
int Parent(uint32_t pos) const noexcept
親ノードとなる括弧の位置を返します。
Definition: Bp.h:52
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:32