nlib
Bp.h
Go to the documentation of this file.
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_BP_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_BP_H_
5 
6 #include "nn/nlib/Swap.h"
7 #include "nn/nlib/succinct/Sbv.h"
8 #include "nn/nlib/ReallocVec.h"
9 
10 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
11 #undef NLIB_VIS_PUBLIC
12 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
13 #endif
14 
15 NLIB_NAMESPACE_BEGIN
16 namespace succinct {
17 
18 class Bp_;
19 
20 class Bp NLIB_FINAL {
21  public:
22  Bp() NLIB_NOEXCEPT : m_Bp(NULL) {}
23  ~Bp() NLIB_NOEXCEPT { this->Reset(); }
24  NLIB_MOVE_MEMBER_HELPER_2(Bp, m_Bp, m_Select1);
25  void swap(Bp& rhs) NLIB_NOEXCEPT {
26  using std::swap;
27  swap(m_Bp, rhs.m_Bp);
28  swap(m_Select1, rhs.m_Select1);
29  }
30  template <class TREEITER>
31  bool Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
32  NLIB_VIS_PUBLIC bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
33  NLIB_VIS_PUBLIC int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
34  NLIB_VIS_PUBLIC int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
35  NLIB_VIS_PUBLIC int FindOpen(uint32_t pos) const NLIB_NOEXCEPT;
36  NLIB_VIS_PUBLIC int FindClose(uint32_t pos) const NLIB_NOEXCEPT;
37  NLIB_VIS_PUBLIC int Enclose(uint32_t pos) const NLIB_NOEXCEPT;
38  NLIB_VIS_PUBLIC int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
39  NLIB_VIS_PUBLIC int LastChild(uint32_t pos) const NLIB_NOEXCEPT;
40  NLIB_VIS_PUBLIC int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
41  NLIB_VIS_PUBLIC int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
42  int Parent(uint32_t pos) const NLIB_NOEXCEPT { return this->Enclose(pos); }
43  NLIB_VIS_PUBLIC size_t MemSize() const NLIB_NOEXCEPT;
44  NLIB_VIS_PUBLIC void Reset() NLIB_NOEXCEPT;
45  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
46  NLIB_VIS_PUBLIC bool Import(BinaryReader* r) NLIB_NOEXCEPT;
47 
48  private:
49  Set* Get1stLevelSet() NLIB_NOEXCEPT;
50  bool Build() NLIB_NOEXCEPT;
51 
52  private:
53  Bp_* m_Bp;
54  detail::SbvSelect m_Select1; // used to get pos from nodeid
56 };
57 
58 template <class TREEITER>
59 bool Bp::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
60  // TREEITER has following methods:
61  // const void* NodePtr(); // ptr to node
62  // const void* ParentNodePtr(); // ptr to parent node
63  // bool MoveNext(); // move to the next node by depth first search
64  if (num_nodes >= 0x80000000) return false;
65  if (m_Bp) return false;
66  Set* bv = Get1stLevelSet(); // bv = &m_Bp.m_B
67  bv->Init(num_nodes * 2);
68 
69  uint32_t idx = 0;
71  do {
72  const void* parent = iter.ParentNodePtr();
73  const void* node = iter.NodePtr();
74  if (stack.empty() || stack.back() == parent) {
75  bv->TurnOn(idx++);
76  if (!stack.push_back(node)) return false;
77  } else {
78  while (stack.back() != parent) {
79  stack.pop_back();
80  ++idx;
81  }
82  bv->TurnOn(idx++);
83  if (!stack.push_back(node)) return false;
84  }
85  } while (iter.MoveNext());
86 
87  if (!this->Build() || !m_Select1.Build(bv->GetBitVector(), bv->GetBitVectorSize())) {
88  this->Reset();
89  return false;
90  }
91  return true;
92 }
93 
94 } // namespace succinct
95 NLIB_NAMESPACE_END
96 
97 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Bp)
98 
99 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
100 #undef NLIB_VIS_PUBLIC
101 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
102 #endif
103 
104 #endif // INCLUDE_NN_NLIB_SUCCINCT_BP_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Platform.h:2151
Defines the basic classes that form the basis to Rank and Select operations.
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
Definition: Sbv.h:347
bool push_back(const T &v) noexcept
Adds an element to the vector.
Definition: ReallocVec.h:46
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:126
uint32_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
Definition: Sbv.h:346
~Bp() noexcept
Destructor.
Definition: Bp.h:23
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: Sbv.h:326
T & back()
Gets the last element.
Definition: ReallocVec.h:64
bool pop_back() noexcept
Deletes an element from the end of the vector.
Definition: ReallocVec.h:55
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:314
int Parent(uint32_t pos) const noexcept
Returns the position of the parentheses equivalent to the parent node.
Definition: Bp.h:42
Provides a compact tree structure that can provide various operations in constant time...
Definition: Bp.h:20
void swap(Bp &rhs) noexcept
Swaps the contents of an object.
Definition: Bp.h:25
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:13
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:51
Bp() noexcept
Instantiates the object.
Definition: Bp.h:22
bool Init(uint32_t bv_size) noexcept
Initializes an object.
Definition: Sbv.h:325
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:13
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:96
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:18