nlib
Louds.h
Go to the documentation of this file.
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
5 
6 #include "nn/nlib/Swap.h"
7 #include "nn/nlib/succinct/Sbv.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:
21  NLIB_MOVE_MEMBER_HELPER_1(Louds, m_Sbv);
22  void swap(Louds& rhs) NLIB_NOEXCEPT { m_Sbv.swap(rhs.m_Sbv); }
23  template <class TREEITER>
24  bool Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
25 
26  NLIB_VIS_PUBLIC bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
27  NLIB_VIS_PUBLIC int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
28  NLIB_VIS_PUBLIC int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
29  NLIB_VIS_PUBLIC int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
30  NLIB_VIS_PUBLIC int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
31  NLIB_VIS_PUBLIC int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
32  NLIB_VIS_PUBLIC int Parent(uint32_t pos) const NLIB_NOEXCEPT;
33  bool IsLeaf(uint32_t pos) const NLIB_NOEXCEPT {
34  return this->FirstChild(pos) < 0;
35  }
36  size_t MemSize() const NLIB_NOEXCEPT { return m_Sbv.MemSize(); }
37  void Reset() NLIB_NOEXCEPT { m_Sbv.Reset(); }
38  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT { return m_Sbv.Export(w); }
39  bool Import(BinaryReader* r) NLIB_NOEXCEPT { return m_Sbv.Import(r); }
40 
41  private:
42  Sbv m_Sbv;
44 };
45 
46 template <class TREEITER>
47 bool Louds::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
48  // TREEITER has following methods:
49  // int GetNumChildren();
50  // bool BfsMoveNext(); // move to the next node by breadth first search
51  m_Sbv.Init(2 * num_nodes + 1);
52 
53  // diffrent from the Louds paper: reversed bits
54  m_Sbv.TurnOn(1);
55  uint32_t idx = 2; // consider super-root 01
56  do {
57  idx += iter.GetNumChildren();
58  m_Sbv.TurnOn(idx++);
59  } while (iter.BfsMoveNext());
60 
61  NLIB_ASSERT(idx == 2 * num_nodes + 1);
62  if (!m_Sbv.Build()) {
63  m_Sbv.Reset();
64  return false;
65  }
66  return true;
67 }
68 
69 } // namespace succinct
70 NLIB_NAMESPACE_END
71 
72 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
73 #undef NLIB_VIS_PUBLIC
74 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
75 #endif
76 
77 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_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.
Louds() noexcept
Instantiates the object.
Definition: Louds.h:19
#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
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:358
bool IsLeaf(uint32_t pos) const noexcept
Determines whether the specified node is a leaf (or external) node.
Definition: Louds.h:33
bool Import(BinaryReader *r) noexcept
Reads the written object.
Definition: Louds.h:39
void swap(Louds &rhs) noexcept
Swaps the contents of an object.
Definition: Louds.h:22
~Louds() noexcept
Destructor.
Definition: Louds.h:20
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: Louds.h:37
Provides a compact tree structure that can provide various operations in constant time...
Definition: Louds.h:17
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
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:13
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
Definition: Louds.h:38
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
Definition: Louds.h:36