nlib
Bp.h
Go to the documentation of this file.
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_BP_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_BP_H_
18 
19 #include "nn/nlib/succinct/Sbv.h"
20 #include "nn/nlib/ReallocVec.h"
21 
22 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
23 #undef NLIB_VIS_PUBLIC
24 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
25 #endif
26 
27 NLIB_NAMESPACE_BEGIN
28 namespace succinct {
29 
31  public:
32  typedef uint32_t NodeId;
33  typedef uint32_t Pos;
34  NLIB_CEXPR Bp() NLIB_NOEXCEPT : prv_(nullptr) {}
35  ~Bp() NLIB_NOEXCEPT { Reset(); }
36  NLIB_DEFMOVE_PIMPL(Bp);
37  template<class TREEITER>
38  bool Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT;
39  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
40  int ToNodeId(Pos pos) const NLIB_NOEXCEPT;
41  int ToPos(NodeId nodeid) const NLIB_NOEXCEPT;
42  int FindOpen(Pos pos) const NLIB_NOEXCEPT;
43  int FindClose(Pos pos) const NLIB_NOEXCEPT;
44  int Enclose(Pos pos) const NLIB_NOEXCEPT;
45  int FirstChild(Pos pos) const NLIB_NOEXCEPT;
46  int LastChild(Pos pos) const NLIB_NOEXCEPT;
47  int NextSibling(Pos pos) const NLIB_NOEXCEPT;
48  int PrevSibling(Pos pos) const NLIB_NOEXCEPT;
49  int Parent(Pos pos) const NLIB_NOEXCEPT { return this->Enclose(pos); }
50 
51  std::pair<bool, NodeId> GetNodeIdByPos(Pos pos) const NLIB_NOEXCEPT {
52  int r = ToNodeId(pos);
53  return std::make_pair((r >= 0), static_cast<NodeId>(r));
54  }
55  std::pair<bool, Pos> GetPosByNodeId(NodeId nodeid) const NLIB_NOEXCEPT {
56  int r = ToPos(nodeid);
57  return std::make_pair((r >= 0), static_cast<Pos>(r));
58  }
59 
60  std::pair<bool, Pos> GetPosOfFirstChild(Pos pos) const NLIB_NOEXCEPT {
61  int r = FirstChild(pos);
62  return std::make_pair((r >= 0), static_cast<Pos>(r));
63  }
64  std::pair<bool, Pos> GetPosOfLastChild(Pos pos) const NLIB_NOEXCEPT {
65  int r = LastChild(pos);
66  return std::make_pair((r >= 0), static_cast<Pos>(r));
67  }
68  std::pair<bool, Pos> GetPosOfNextSibling(Pos pos) const NLIB_NOEXCEPT {
69  int r = NextSibling(pos);
70  return std::make_pair((r >= 0), static_cast<Pos>(r));
71  }
72  std::pair<bool, Pos> GetPosOfPrevSibling(Pos pos) const NLIB_NOEXCEPT {
73  int r = PrevSibling(pos);
74  return std::make_pair((r >= 0), static_cast<Pos>(r));
75  }
76  std::pair<bool, Pos> GetPosOfParent(Pos pos) const NLIB_NOEXCEPT {
77  int r = Parent(pos);
78  return std::make_pair((r >= 0), static_cast<Pos>(r));
79  }
80 
81  std::pair<bool, NodeId> GetNodeIdOfFirstChild(NodeId nodeid) const NLIB_NOEXCEPT {
82  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
83  int r = FirstChild(pos.second);
84  return GetNodeIdByPos(static_cast<Pos>(r));
85  }
86  std::pair<bool, NodeId> GetNodeIdOfLastChild(NodeId nodeid) const NLIB_NOEXCEPT {
87  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
88  int r = LastChild(pos.second);
89  return GetNodeIdByPos(static_cast<Pos>(r));
90  }
91  std::pair<bool, NodeId> GetNodeIdOfNextSibling(NodeId nodeid) const NLIB_NOEXCEPT {
92  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
93  int r = NextSibling(pos.second);
94  return GetNodeIdByPos(static_cast<Pos>(r));
95  }
96  std::pair<bool, NodeId> GetNodeIdOfPrevSibling(NodeId nodeid) const NLIB_NOEXCEPT {
97  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
98  int r = PrevSibling(pos.second);
99  return GetNodeIdByPos(static_cast<Pos>(r));
100  }
101  std::pair<bool, NodeId> GetNodeIdOfParent(NodeId nodeid) const NLIB_NOEXCEPT {
102  std::pair<bool, uint32_t> pos = GetPosByNodeId(nodeid);
103  int r = Parent(pos.second);
104  return GetNodeIdByPos(static_cast<Pos>(r));
105  }
106 
107  size_t MemSize() const NLIB_NOEXCEPT;
108  void Reset() NLIB_NOEXCEPT;
109  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
110  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
111 
112  private:
113  Set* Get1stLevelSet() NLIB_NOEXCEPT;
114  bool Build(const uint32_t* bv, uint32_t bvsize) NLIB_NOEXCEPT;
115 
116  private:
117  struct BpPrivate;
118  BpPrivate* prv_;
120 };
121 
122 template<class TREEITER>
123 bool Bp::Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT {
124  TREEITER& iter = root;
125  // TREEITER has following methods:
126  // const void* NodePtr(); // ptr to node
127  // const void* ParentNodePtr(); // ptr to parent node
128  // bool MoveNext(); // move to the next node by depth first search
129  if (num_nodes >= 0x80000000) return false;
130  if (prv_) return false;
131  Set* bv = Get1stLevelSet(); // bv = &bp_.b_
132  if (!bv) {
133  this->Reset();
134  return false;
135  }
136  bv->Init(num_nodes * 2);
137 
138  uint32_t idx = 0;
140  do {
141  const void* parent = iter.ParentNodePtr();
142  const void* node = iter.NodePtr();
143  if (stack.empty() || stack.back() == parent) {
144  bv->TurnOn(idx++);
145  if (!stack.push_back(node)) {
146  this->Reset();
147  return false;
148  }
149  } else {
150  while (stack.back() != parent) {
151  stack.pop_back();
152  ++idx;
153  if (stack.empty()) {
154  // Has multiple root nodes
155  this->Reset();
156  return false;
157  }
158  }
159  bv->TurnOn(idx++);
160  if (!stack.push_back(node)) {
161  this->Reset();
162  return false;
163  }
164  }
165  } while (iter.MoveNext());
166 
167  if (!this->Build(bv->GetBitVector(), bv->GetBitVectorSize())) {
168  this->Reset();
169  return false;
170  }
171  return true;
172 }
173 
174 } // namespace succinct
175 NLIB_NAMESPACE_END
176 
177 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Bp)
178 
179 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
180 #undef NLIB_VIS_PUBLIC
181 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
182 #endif
183 
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.
Definition: Bp.h:86
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
Gets the balanced parentheses position of the parent node in the specified balanced parentheses posit...
Definition: Bp.h:76
bool push_back(const T &v) noexcept
Adds an element to the vector.
Definition: ReallocVec.h:100
#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:183
uint32_t Pos
Represents an index in the balanced parentheses with a 32-bit non-negative integer.
Definition: Bp.h:33
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
Gets the node ID of the next sibling node of the specified node.
Definition: Bp.h:91
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.
Definition: Bp.h:96
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
Gets the balanced parentheses position of the next sibling node in the specified balanced parentheses...
Definition: Bp.h:68
std::pair< bool, Pos > GetPosOfLastChild(Pos pos) const noexcept
Gets the balanced parentheses position of the last child in the specified balanced parentheses positi...
Definition: Bp.h:64
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
Gets the node ID of the parent node of the specified node.
Definition: Bp.h:101
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...
Definition: Bp.h:72
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:87
~Bp() noexcept
Destructor.
Definition: Bp.h:35
int Parent(Pos pos) const noexcept
Returns the position of the parentheses equivalent to the parent node.
Definition: Bp.h:49
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
T & back()
Gets a reference to the last element.
Definition: ReallocVec.h:124
bool pop_back() noexcept
Deletes an element from the end of the vector.
Definition: ReallocVec.h:109
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:41
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
Gets the corresponding node ID from the parenthesis position.
Definition: Bp.h:51
uint32_t NodeId
Represents a node ID with a 32-bit non-negative integer.
Definition: Bp.h:32
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
Gets the node ID of the first child of the specified node.
Definition: Bp.h:81
Provides a compact tree structure that can provide various operations in constant time...
Definition: Bp.h:30
bool empty() const noexcept
Returns true if the number of stored elements is 0, or returns false otherwise.
Definition: ReallocVec.h:147
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:109
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:111
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:26
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:250
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
Gets the corresponding parenthesis position from the node ID.
Definition: Bp.h:55
constexpr Bp() noexcept
Instantiates the object with default parameters (default constructor). Requires initialization with I...
Definition: Bp.h:34
bool Init(uint32_t bv_size) noexcept
Initializes an object.
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
Gets the balanced parentheses position of the first child in the specified balanced parentheses posit...
Definition: Bp.h:60
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:32