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  NLIB_CEXPR Bp() NLIB_NOEXCEPT : prv_(nullptr) {}
33  ~Bp() NLIB_NOEXCEPT { Reset(); }
34  NLIB_DEFMOVE_PIMPL(Bp);
36  BpPrivate* tmp = rhs.prv_;
37  rhs.prv_ = prv_;
38  prv_ = tmp;
39  }
40  template <class TREEITER>
41  bool Init(TREEITER& root, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
42  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
43  int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
44  int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
45  int FindOpen(uint32_t pos) const NLIB_NOEXCEPT;
46  int FindClose(uint32_t pos) const NLIB_NOEXCEPT;
47  int Enclose(uint32_t pos) const NLIB_NOEXCEPT;
48  int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
49  int LastChild(uint32_t pos) const NLIB_NOEXCEPT;
50  int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
51  int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
52  int Parent(uint32_t pos) const NLIB_NOEXCEPT { return this->Enclose(pos); }
53  size_t MemSize() const NLIB_NOEXCEPT;
54  void Reset() NLIB_NOEXCEPT;
55  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
56  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
57 
58  private:
59  Set* Get1stLevelSet() NLIB_NOEXCEPT;
60  bool Build(const uint32_t* bv, uint32_t bvsize) NLIB_NOEXCEPT;
61 
62  private:
63  struct BpPrivate;
64  BpPrivate* prv_;
66 };
67 
68 template <class TREEITER>
69 bool Bp::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
70  // TREEITER has following methods:
71  // const void* NodePtr(); // ptr to node
72  // const void* ParentNodePtr(); // ptr to parent node
73  // bool MoveNext(); // move to the next node by depth first search
74  if (num_nodes >= 0x80000000) return false;
75  if (prv_) return false;
76  Set* bv = Get1stLevelSet(); // bv = &bp_.b_
77  if (!bv) {
78  this->Reset();
79  return false;
80  }
81  bv->Init(num_nodes * 2);
82 
83  uint32_t idx = 0;
85  do {
86  const void* parent = iter.ParentNodePtr();
87  const void* node = iter.NodePtr();
88  if (stack.empty() || stack.back() == parent) {
89  bv->TurnOn(idx++);
90  if (!stack.push_back(node)) {
91  this->Reset();
92  return false;
93  }
94  } else {
95  while (stack.back() != parent) {
96  stack.pop_back();
97  ++idx;
98  }
99  bv->TurnOn(idx++);
100  if (!stack.push_back(node)) {
101  this->Reset();
102  return false;
103  }
104  }
105  } while (iter.MoveNext());
106 
107  if (!this->Build(bv->GetBitVector(), bv->GetBitVectorSize())) {
108  this->Reset();
109  return false;
110  }
111  return true;
112 }
113 
114 } // namespace succinct
115 NLIB_NAMESPACE_END
116 
117 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Bp)
118 
119 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
120 #undef NLIB_VIS_PUBLIC
121 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
122 #endif
123 
124 #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:101
#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:179
uint32_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
#define NLIB_DEPRECATED
Indicates that a function or something has been deprecated.
Definition: Config.h:109
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:89
~Bp() noexcept
Destructor.
Definition: Bp.h:33
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
T & back()
Gets the last element.
Definition: ReallocVec.h:119
bool pop_back() noexcept
Deletes an element from the end of the vector.
Definition: ReallocVec.h:110
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:41
Provides a compact tree structure that can provide various operations in constant time...
Definition: Bp.h:30
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:144
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:105
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:107
void swap(Bp &rhs) noexcept
Swaps the contents of an object.
Definition: Bp.h:35
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:245
constexpr Bp() noexcept
Instantiates the object.
Definition: Bp.h:32
bool Init(uint32_t bv_size) noexcept
Initializes an object.
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
int Parent(uint32_t pos) const noexcept
Returns the position of the parentheses equivalent to the parent node.
Definition: Bp.h:52
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:32