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  typedef uint32_t NodeId;
33  typedef uint32_t Pos;
34  NLIB_CEXPR Bp() NLIB_NOEXCEPT : prv_(nullptr) {}
35  ~Bp() NLIB_NOEXCEPT { Reset(); }
36  NLIB_DEFMOVE_PIMPL(Bp);
37  template<class TREEITER>
38  bool Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT;
39  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
40  int ToNodeId(Pos pos) const NLIB_NOEXCEPT;
41  int ToPos(NodeId nodeid) const NLIB_NOEXCEPT;
42  int FindOpen(Pos pos) const NLIB_NOEXCEPT;
43  int FindClose(Pos pos) const NLIB_NOEXCEPT;
44  int Enclose(Pos pos) const NLIB_NOEXCEPT;
45  int FirstChild(Pos pos) const NLIB_NOEXCEPT;
46  int LastChild(Pos pos) const NLIB_NOEXCEPT;
47  int NextSibling(Pos pos) const NLIB_NOEXCEPT;
48  int PrevSibling(Pos pos) const NLIB_NOEXCEPT;
49  int Parent(Pos pos) const NLIB_NOEXCEPT { return this->Enclose(pos); }
50 
51  std::pair<bool, NodeId> GetNodeIdByPos(Pos pos) const NLIB_NOEXCEPT {
52  int r = ToNodeId(pos);
53  return std::make_pair((r >= 0), static_cast<NodeId>(r));
54  }
55  std::pair<bool, Pos> GetPosByNodeId(NodeId nodeid) const NLIB_NOEXCEPT {
56  int r = ToPos(nodeid);
57  return std::make_pair((r >= 0), static_cast<Pos>(r));
58  }
59 
60  std::pair<bool, Pos> GetPosOfFirstChild(Pos pos) const NLIB_NOEXCEPT {
61  int r = FirstChild(pos);
62  return std::make_pair((r >= 0), static_cast<Pos>(r));
63  }
64  std::pair<bool, Pos> GetPosOfLastChild(Pos pos) const NLIB_NOEXCEPT {
65  int r = LastChild(pos);
66  return std::make_pair((r >= 0), static_cast<Pos>(r));
67  }
68  std::pair<bool, Pos> GetPosOfNextSibling(Pos pos) const NLIB_NOEXCEPT {
69  int r = NextSibling(pos);
70  return std::make_pair((r >= 0), static_cast<Pos>(r));
71  }
72  std::pair<bool, Pos> GetPosOfPrevSibling(Pos pos) const NLIB_NOEXCEPT {
73  int r = PrevSibling(pos);
74  return std::make_pair((r >= 0), static_cast<Pos>(r));
75  }
76  std::pair<bool, Pos> GetPosOfParent(Pos pos) const NLIB_NOEXCEPT {
77  int r = Parent(pos);
78  return std::make_pair((r >= 0), static_cast<Pos>(r));
79  }
80 
81  std::pair<bool, NodeId> GetNodeIdOfFirstChild(NodeId nodeid) const NLIB_NOEXCEPT {
82  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
83  int r = FirstChild(pos.second);
84  return GetNodeIdByPos(static_cast<Pos>(r));
85  }
86  std::pair<bool, NodeId> GetNodeIdOfLastChild(NodeId nodeid) const NLIB_NOEXCEPT {
87  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
88  int r = LastChild(pos.second);
89  return GetNodeIdByPos(static_cast<Pos>(r));
90  }
91  std::pair<bool, NodeId> GetNodeIdOfNextSibling(NodeId nodeid) const NLIB_NOEXCEPT {
92  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
93  int r = NextSibling(pos.second);
94  return GetNodeIdByPos(static_cast<Pos>(r));
95  }
96  std::pair<bool, NodeId> GetNodeIdOfPrevSibling(NodeId nodeid) const NLIB_NOEXCEPT {
97  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
98  int r = PrevSibling(pos.second);
99  return GetNodeIdByPos(static_cast<Pos>(r));
100  }
101  std::pair<bool, NodeId> GetNodeIdOfParent(NodeId nodeid) const NLIB_NOEXCEPT {
102  std::pair<bool, uint32_t> pos = GetPosByNodeId(nodeid);
103  int r = Parent(pos.second);
104  return GetNodeIdByPos(static_cast<Pos>(r));
105  }
106 
107  size_t MemSize() const NLIB_NOEXCEPT;
108  void Reset() NLIB_NOEXCEPT;
109  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
110  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
111 
112  private:
113  Set* Get1stLevelSet() NLIB_NOEXCEPT;
114  bool Build(const uint32_t* bv, uint32_t bvsize) NLIB_NOEXCEPT;
115 
116  private:
117  struct BpPrivate;
118  BpPrivate* prv_;
120 };
121 
122 template<class TREEITER>
123 bool Bp::Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT {
124  TREEITER& iter = root;
125  // TREEITER has following methods:
126  // const void* NodePtr(); // ptr to node
127  // const void* ParentNodePtr(); // ptr to parent node
128  // bool MoveNext(); // move to the next node by depth first search
129  if (num_nodes >= 0x80000000) return false;
130  if (prv_) return false;
131  Set* bv = Get1stLevelSet(); // bv = &bp_.b_
132  if (!bv) {
133  this->Reset();
134  return false;
135  }
136  bv->Init(num_nodes * 2);
137 
138  uint32_t idx = 0;
140  do {
141  const void* parent = iter.ParentNodePtr();
142  const void* node = iter.NodePtr();
143  if (stack.empty() || stack.back() == parent) {
144  bv->TurnOn(idx++);
145  if (!stack.push_back(node)) {
146  this->Reset();
147  return false;
148  }
149  } else {
150  while (stack.back() != parent) {
151  stack.pop_back();
152  ++idx;
153  if (stack.empty()) {
154  // Has multiple root nodes
155  this->Reset();
156  return false;
157  }
158  }
159  bv->TurnOn(idx++);
160  if (!stack.push_back(node)) {
161  this->Reset();
162  return false;
163  }
164  }
165  } while (iter.MoveNext());
166 
167  if (!this->Build(bv->GetBitVector(), bv->GetBitVectorSize())) {
168  this->Reset();
169  return false;
170  }
171  return true;
172 }
173 
174 } // namespace succinct
175 NLIB_NAMESPACE_END
176 
177 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Bp)
178 
179 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
180 #undef NLIB_VIS_PUBLIC
181 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
182 #endif
183 
184 #endif // INCLUDE_NN_NLIB_SUCCINCT_BP_H_
rank/select操作をベースとした基本的なクラスが定義されています。
std::pair< bool, NodeId > GetNodeIdOfLastChild(NodeId nodeid) const noexcept
指定されたノードの最後の子のノードIDを取得します。
Definition: Bp.h:86
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
指定された括弧列上の位置の親ノードの括弧列上の位置を取得します。
Definition: Bp.h:76
bool push_back(const T &v) noexcept
ベクタに要素を追加します。
Definition: ReallocVec.h:100
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:183
uint32_t Pos
32bit非負整数で括弧列上のインデックスを表します。
Definition: Bp.h:33
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
指定されたノードの次の兄弟ノードのノードIDを取得します。
Definition: Bp.h:91
uint32_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
std::pair< bool, NodeId > GetNodeIdOfPrevSibling(NodeId nodeid) const noexcept
指定されたノードの前の兄弟ノードのノードIDを取得します。
Definition: Bp.h:96
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
指定された括弧列上の位置の次の兄弟ノードの括弧列上の位置を取得します。
Definition: Bp.h:68
std::pair< bool, Pos > GetPosOfLastChild(Pos pos) const noexcept
指定された括弧列上の位置の最後の子の括弧列上の位置を取得します。
Definition: Bp.h:64
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
指定されたノードの親ノードのノードIDを取得します。
Definition: Bp.h:101
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
指定された括弧列上の位置の前の兄弟ノードの括弧列上の位置を取得します。
Definition: Bp.h:72
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:87
~Bp() noexcept
デストラクタです。
Definition: Bp.h:35
int Parent(Pos pos) const noexcept
親ノードとなる括弧の位置を返します。
Definition: Bp.h:49
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
T & back()
最後の要素への参照を取得します。
Definition: ReallocVec.h:124
bool pop_back() noexcept
ベクタの末尾から要素を削除します。
Definition: ReallocVec.h:109
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:41
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
括弧の位置から対応するノードIDを取得します。
Definition: Bp.h:51
uint32_t NodeId
32bit非負整数でノードIDを表します。
Definition: Bp.h:32
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
指定されたノードの最初の子のノードIDを取得します。
Definition: Bp.h:81
各種操作を で行うことができるコンパクトなツリー構造です。
Definition: Bp.h:30
bool empty() const noexcept
格納されている要素数が0ならばtrue、それ以外ならfalseを返します。
Definition: ReallocVec.h:147
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:111
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:250
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
ノードIDから対応する括弧の位置を取得します。
Definition: Bp.h:55
constexpr Bp() noexcept
デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
Definition: Bp.h:34
bool Init(uint32_t bv_size) noexcept
オブジェクトを初期化します。
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
指定された括弧列上の位置の最初の子の括弧列上の位置を取得します。
Definition: Bp.h:60
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:32