16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_BP_H_ 17 #define INCLUDE_NN_NLIB_SUCCINCT_BP_H_ 22 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 23 #undef NLIB_VIS_PUBLIC 24 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT 36 NLIB_DEFMOVE_PIMPL(
Bp);
37 template<
class TREEITER>
39 bool InitDirect(
const uint32_t* bv, uint32_t bv_size)
NLIB_NOEXCEPT;
52 int r = ToNodeId(pos);
53 return std::make_pair((r >= 0), static_cast<NodeId>(r));
56 int r = ToPos(nodeid);
57 return std::make_pair((r >= 0), static_cast<Pos>(r));
61 int r = FirstChild(pos);
62 return std::make_pair((r >= 0), static_cast<Pos>(r));
65 int r = LastChild(pos);
66 return std::make_pair((r >= 0), static_cast<Pos>(r));
69 int r = NextSibling(pos);
70 return std::make_pair((r >= 0), static_cast<Pos>(r));
73 int r = PrevSibling(pos);
74 return std::make_pair((r >= 0), static_cast<Pos>(r));
78 return std::make_pair((r >= 0), static_cast<Pos>(r));
82 std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
83 int r = FirstChild(pos.second);
84 return GetNodeIdByPos(static_cast<Pos>(r));
87 std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
88 int r = LastChild(pos.second);
89 return GetNodeIdByPos(static_cast<Pos>(r));
92 std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
93 int r = NextSibling(pos.second);
94 return GetNodeIdByPos(static_cast<Pos>(r));
97 std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
98 int r = PrevSibling(pos.second);
99 return GetNodeIdByPos(static_cast<Pos>(r));
102 std::pair<bool, uint32_t> pos = GetPosByNodeId(nodeid);
103 int r = Parent(pos.second);
104 return GetNodeIdByPos(static_cast<Pos>(r));
114 bool Build(const uint32_t* bv, uint32_t bvsize)
NLIB_NOEXCEPT;
122 template<class TREEITER>
124 TREEITER& iter = root;
129 if (num_nodes >= 0x80000000)
return false;
130 if (prv_)
return false;
131 Set* bv = Get1stLevelSet();
136 bv->
Init(num_nodes * 2);
141 const void* parent = iter.ParentNodePtr();
142 const void* node = iter.NodePtr();
143 if (stack.
empty() || stack.
back() == parent) {
150 while (stack.
back() != parent) {
165 }
while (iter.MoveNext());
177 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Bp)
179 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 180 #undef NLIB_VIS_PUBLIC 181 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT 184 #endif // INCLUDE_NN_NLIB_SUCCINCT_BP_H_ rank/select操作をベースとした基本的なクラスが定義されています。
std::pair< bool, NodeId > GetNodeIdOfLastChild(NodeId nodeid) const noexcept
指定されたノードの最後の子のノードIDを取得します。
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
指定された括弧列上の位置の親ノードの括弧列上の位置を取得します。
bool push_back(const T &v) noexcept
ベクタに要素を追加します。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
uint32_t Pos
32bit非負整数で括弧列上のインデックスを表します。
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
指定されたノードの次の兄弟ノードのノードIDを取得します。
uint32_t GetBitVectorSize() const noexcept
ビットベクトルのサイズを返します。
std::pair< bool, NodeId > GetNodeIdOfPrevSibling(NodeId nodeid) const noexcept
指定されたノードの前の兄弟ノードのノードIDを取得します。
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
指定された括弧列上の位置の次の兄弟ノードの括弧列上の位置を取得します。
std::pair< bool, Pos > GetPosOfLastChild(Pos pos) const noexcept
指定された括弧列上の位置の最後の子の括弧列上の位置を取得します。
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
指定されたノードの親ノードのノードIDを取得します。
const uint32_t * GetBitVector() const noexcept
ビットベクトルへのポインタを返します。
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
指定された括弧列上の位置の前の兄弟ノードの括弧列上の位置を取得します。
int Parent(Pos pos) const noexcept
親ノードとなる括弧の位置を返します。
bool TurnOn(uint32_t idx) noexcept
集合に32bit符号なし整数を追加します。
T & back()
最後の要素への参照を取得します。
bool pop_back() noexcept
ベクタの末尾から要素を削除します。
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
括弧の位置から対応するノードIDを取得します。
uint32_t NodeId
32bit非負整数でノードIDを表します。
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
指定されたノードの最初の子のノードIDを取得します。
各種操作を で行うことができるコンパクトなツリー構造です。
bool empty() const noexcept
格納されている要素数が0ならばtrue、それ以外ならfalseを返します。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
ノードIDから対応する括弧の位置を取得します。
constexpr Bp() noexcept
デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
bool Init(uint32_t bv_size) noexcept
オブジェクトを初期化します。
ストリーム(InputStream)からバイナリを読み込むクラスです。
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
指定された括弧列上の位置の最初の子の括弧列上の位置を取得します。
PODを要素に持つベクタをreallocベースで実装しています。