nlib
Louds.h
[詳解]
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
5 
6 #include "nn/nlib/Swap.h"
7 #include "nn/nlib/succinct/Sbv.h"
8 
9 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
10 #undef NLIB_VIS_PUBLIC
11 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
12 #endif
13 
14 NLIB_NAMESPACE_BEGIN
15 namespace succinct {
16 
18  public:
21  NLIB_MOVE_MEMBER_HELPER_1(Louds, m_Sbv);
22  void swap(Louds& rhs) NLIB_NOEXCEPT { m_Sbv.swap(rhs.m_Sbv); }
23  template <class TREEITER>
24  bool Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
25 
26  NLIB_VIS_PUBLIC bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
27  NLIB_VIS_PUBLIC int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
28  NLIB_VIS_PUBLIC int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
29  NLIB_VIS_PUBLIC int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
30  NLIB_VIS_PUBLIC int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
31  NLIB_VIS_PUBLIC int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
32  NLIB_VIS_PUBLIC int Parent(uint32_t pos) const NLIB_NOEXCEPT;
33  bool IsLeaf(uint32_t pos) const NLIB_NOEXCEPT {
34  return this->FirstChild(pos) < 0;
35  }
36  size_t MemSize() const NLIB_NOEXCEPT { return m_Sbv.MemSize(); }
37  void Reset() NLIB_NOEXCEPT { m_Sbv.Reset(); }
38  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT { return m_Sbv.Export(w); }
39  bool Import(BinaryReader* r) NLIB_NOEXCEPT { return m_Sbv.Import(r); }
40 
41  private:
42  Sbv m_Sbv;
44 };
45 
46 template <class TREEITER>
47 bool Louds::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
48  // TREEITER has following methods:
49  // int GetNumChildren();
50  // bool BfsMoveNext(); // move to the next node by breadth first search
51  m_Sbv.Init(2 * num_nodes + 1);
52 
53  // diffrent from the Louds paper: reversed bits
54  m_Sbv.TurnOn(1);
55  uint32_t idx = 2; // consider super-root 01
56  do {
57  idx += iter.GetNumChildren();
58  m_Sbv.TurnOn(idx++);
59  } while (iter.BfsMoveNext());
60 
61  NLIB_ASSERT(idx == 2 * num_nodes + 1);
62  if (!m_Sbv.Build()) {
63  m_Sbv.Reset();
64  return false;
65  }
66  return true;
67 }
68 
69 } // namespace succinct
70 NLIB_NAMESPACE_END
71 
72 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
73 #undef NLIB_VIS_PUBLIC
74 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
75 #endif
76 
77 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Platform.h:2151
rank/select操作をベースとした基本的なクラスが定義されています。
Louds() noexcept
コンストラクタです。
Definition: Louds.h:19
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:126
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:358
bool IsLeaf(uint32_t pos) const noexcept
ノードが葉ノードかどうかを判定します。
Definition: Louds.h:33
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
Definition: Louds.h:39
void swap(Louds &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Louds.h:22
~Louds() noexcept
デストラクタです。
Definition: Louds.h:20
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Louds.h:37
各種操作を で行うことができるコンパクトなツリー構造です。
Definition: Louds.h:17
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:13
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:51
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:13
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
Definition: Louds.h:38
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
Definition: Louds.h:36