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