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_ Defines the basic classes that form the basis to Rank and Select operations.
std::pair< bool, NodeId > GetNodeIdOfLastChild(NodeId nodeid) const noexcept
Gets the node ID of the last child of the specified node.
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
Gets the balanced parentheses position of the parent node in the specified balanced parentheses posit...
bool push_back(const T &v) noexcept
Adds an element to the vector.
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
uint32_t Pos
Represents an index in the balanced parentheses with a 32-bit non-negative integer.
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
Gets the node ID of the next sibling node of the specified node.
uint32_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
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 > GetPosOfNextSibling(Pos pos) const noexcept
Gets the balanced parentheses position of the next sibling node in the specified balanced parentheses...
std::pair< bool, Pos > GetPosOfLastChild(Pos pos) const noexcept
Gets the balanced parentheses position of the last child in the specified balanced parentheses positi...
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
Gets the node ID of the parent node of the specified node.
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
Gets the balanced parentheses position of the previous sibling node in the specified balanced parenth...
~Bp() noexcept
Destructor.
int Parent(Pos pos) const noexcept
Returns the position of the parentheses equivalent to the parent node.
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
T & back()
Gets a reference to the last element.
bool pop_back() noexcept
Deletes an element from the end of the vector.
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
Gets the corresponding node ID from the parenthesis position.
uint32_t NodeId
Represents a node ID with a 32-bit non-negative integer.
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
Gets the node ID of the first child of the specified node.
Provides a compact tree structure that can provide various operations in constant time...
bool empty() const noexcept
Returns true if the number of stored elements is 0, or returns false otherwise.
#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.
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.
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
Gets the corresponding parenthesis position from the node ID.
constexpr Bp() noexcept
Instantiates the object with default parameters (default constructor). Requires initialization with I...
bool Init(uint32_t bv_size) noexcept
Initializes an object.
The class for reading binary from streams (from InputStream).
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
Gets the balanced parentheses position of the first child in the specified balanced parentheses posit...
The class for realloc-based implementations of vectors with POD-type elements.