16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_ 17 #define INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_ 20 #include "nn/nlib/Swap.h" 23 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 24 #undef NLIB_VIS_PUBLIC 25 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT 37 #ifdef __cpp_rvalue_references 40 sbv_ = std::move(rhs.sbv_);
49 template<
class TREEITER>
52 bool InitDirect(
const uint32_t* bv, uint32_t bv_size)
NLIB_NOEXCEPT;
56 int r = ToNodeId(pos);
57 return std::make_pair((r >= 0), static_cast<NodeId>(r));
60 int r = ToPos(nodeid);
61 return std::make_pair((r >= 0), static_cast<Pos>(r));
70 int r = FirstChild(pos);
71 return std::make_pair((r >= 0), static_cast<Pos>(r));
74 int r = NextSibling(pos);
75 return std::make_pair((r >= 0), static_cast<Pos>(r));
78 int r = PrevSibling(pos);
79 return std::make_pair((r >= 0), static_cast<Pos>(r));
83 return std::make_pair((r >= 0), static_cast<Pos>(r));
87 std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
88 int r = FirstChild(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));
118 template<
class TREEITER>
123 sbv_.Init(2 * num_nodes + 1);
129 idx += iter.GetNumChildren();
131 }
while (iter.BfsMoveNext());
133 NLIB_ASSERT(idx == 2 * num_nodes + 1);
144 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Louds)
146 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS) 147 #undef NLIB_VIS_PUBLIC 148 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT 151 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_ rank/select操作をベースとした基本的なクラスが定義されています。
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
ビット列の位置から対応するノードIDを取得します。
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
constexpr Louds() noexcept
デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Louds & operator=(Louds &&rhs) noexcept
ムーブ代入演算子です。
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
指定されたノードの親ノードのノードIDを取得します。
Louds & assign(Louds &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
指定されたノードの最初の子のノードIDを取得します。
uint32_t NodeId
32bit非負整数でノードIDを表します。
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
uint32_t Pos
32bit非負整数でビット列上のインデックスを表します。
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
ノードIDから対応するビット列での位置を取得します。
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
指定されたノードの次の兄弟ノードのノードIDを取得します。
Louds(Louds &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
~Louds() noexcept
デストラクタです。
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
指定されたビット列上の位置の次の兄弟ノードのビット列上の位置を取得します。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
void Reset() noexcept
このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
各種操作を で行うことができるコンパクトなツリー構造です。
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
指定されたビット列上の位置の最初の子のビット列上の位置を取得します。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
ストリーム(InputStream)からバイナリを読み込むクラスです。
Louds(Louds &&rhs) noexcept
ムーブコンストラクタです。
std::pair< bool, NodeId > GetNodeIdOfPrevSibling(NodeId nodeid) const noexcept
指定されたノードの前の兄弟ノードのノードIDを取得します。
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
指定されたビット列上の位置の親ノードのビット列上の位置を取得します。
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
指定されたビット列上の位置の前の兄弟ノードのビット列上の位置を取得します。
bool IsLeaf(Pos pos) const noexcept
ノードが葉ノードかどうかを判定します。