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