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_ Defines the basic classes that form the basis to Rank and Select operations.
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
Gets the corresponding node ID from the bit array position.
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
constexpr Louds() noexcept
Instantiates the object with default parameters (default constructor). Requires initialization with I...
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Louds & operator=(Louds &&rhs) noexcept
Move assignment operator.
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
Gets the node ID of the parent node of the specified node.
Louds & assign(Louds &rhs, move_tag) noexcept
Corresponds to a move assignment operator.
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
Gets the node ID of the first child of the specified node.
uint32_t NodeId
Represents a node ID with a 32-bit non-negative integer.
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
bool Import(BinaryReader *r) noexcept
Reads the written object.
An empty structure indicating that an argument to a function needs to be moved.
uint32_t Pos
Represents an index in the bit array with a 32-bit non-negative integer.
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
Gets the corresponding bit array position from the node ID.
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
Gets the node ID of the next sibling node of the specified node.
Louds(Louds &rhs, move_tag) noexcept
Corresponds to a move constructor.
~Louds() noexcept
Destructor.
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
Gets the bit array position of the next sibling node in the specified bit array position.
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
void Reset() noexcept
Resets this object to the state immediately after the default constructor was executed.
Provides a compact tree structure that can provide various operations in constant time...
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
Gets the bit array position of the first child in the specified bit array position.
The class for writing binary to streams (to OutputStream).
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
The class for reading binary from streams (from InputStream).
Louds(Louds &&rhs) noexcept
Instantiates the object (move constructor).
std::pair< bool, NodeId > GetNodeIdOfPrevSibling(NodeId nodeid) const noexcept
Gets the node ID of the previous sibling node of the specified node.
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
Gets the bit array position of the parent node in the specified bit array position.
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
Gets the bit array position of the previous sibling node in the specified bit array position...
bool IsLeaf(Pos pos) const noexcept
Determines whether the specified node is a leaf (or external) node.