nlib
Louds.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_LOUDS_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
18 
19 #include <utility>
20 #include "nn/nlib/Swap.h"
21 #include "nn/nlib/succinct/Sbv.h"
22 
23 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
24 #undef NLIB_VIS_PUBLIC
25 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
26 #endif
27 
28 NLIB_NAMESPACE_BEGIN
29 namespace succinct {
30 
32  public:
33  typedef uint32_t NodeId;
34  typedef uint32_t Pos;
37 #ifdef __cpp_rvalue_references
38  Louds(Louds&& rhs) NLIB_NOEXCEPT : sbv_(std::move(rhs.sbv_)) {}
40  sbv_ = std::move(rhs.sbv_);
41  return *this;
42  }
43 #endif
44  Louds(Louds& rhs, move_tag) NLIB_NOEXCEPT : sbv_(rhs.sbv_, move_tag()) {}
46  sbv_.assign(rhs.sbv_, move_tag());
47  return *this;
48  }
49  template<class TREEITER>
50  bool Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT;
51 
52  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
53  int ToNodeId(Pos pos) const NLIB_NOEXCEPT;
54  int ToPos(NodeId nodeid) const NLIB_NOEXCEPT;
55  std::pair<bool, NodeId> GetNodeIdByPos(Pos pos) const NLIB_NOEXCEPT {
56  int r = ToNodeId(pos);
57  return std::make_pair((r >= 0), static_cast<NodeId>(r));
58  }
59  std::pair<bool, Pos> GetPosByNodeId(NodeId nodeid) const NLIB_NOEXCEPT {
60  int r = ToPos(nodeid);
61  return std::make_pair((r >= 0), static_cast<Pos>(r));
62  }
63 
64  int FirstChild(Pos pos) const NLIB_NOEXCEPT;
65  int NextSibling(Pos pos) const NLIB_NOEXCEPT;
66  int PrevSibling(Pos pos) const NLIB_NOEXCEPT;
67  int Parent(Pos pos) const NLIB_NOEXCEPT;
68 
69  std::pair<bool, Pos> GetPosOfFirstChild(Pos pos) const NLIB_NOEXCEPT {
70  int r = FirstChild(pos);
71  return std::make_pair((r >= 0), static_cast<Pos>(r));
72  }
73  std::pair<bool, Pos> GetPosOfNextSibling(Pos pos) const NLIB_NOEXCEPT {
74  int r = NextSibling(pos);
75  return std::make_pair((r >= 0), static_cast<Pos>(r));
76  }
77  std::pair<bool, Pos> GetPosOfPrevSibling(Pos pos) const NLIB_NOEXCEPT {
78  int r = PrevSibling(pos);
79  return std::make_pair((r >= 0), static_cast<Pos>(r));
80  }
81  std::pair<bool, Pos> GetPosOfParent(Pos pos) const NLIB_NOEXCEPT {
82  int r = Parent(pos);
83  return std::make_pair((r >= 0), static_cast<Pos>(r));
84  }
85 
86  std::pair<bool, NodeId> GetNodeIdOfFirstChild(NodeId nodeid) const NLIB_NOEXCEPT {
87  std::pair<bool, NodeId> pos = GetPosByNodeId(nodeid);
88  int r = FirstChild(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  bool IsLeaf(Pos pos) const NLIB_NOEXCEPT { return this->FirstChild(pos) < 0; }
108  size_t MemSize() const NLIB_NOEXCEPT { return sbv_.MemSize(); }
109  void Reset() NLIB_NOEXCEPT { sbv_.Reset(); }
110  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT { return sbv_.Export(w); }
111  bool Import(BinaryReader* r) NLIB_NOEXCEPT { return sbv_.Import(r); }
112 
113  private:
114  Sbv sbv_;
116 };
117 
118 template<class TREEITER>
119 bool Louds::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT {
120  // TREEITER has following methods:
121  // int GetNumChildren();
122  // bool BfsMoveNext(); // move to the next node by breadth first search
123  sbv_.Init(2 * num_nodes + 1);
124 
125  // diffrent from the Louds paper: reversed bits
126  sbv_.TurnOn(1);
127  uint32_t idx = 2; // consider super-root 01
128  do {
129  idx += iter.GetNumChildren();
130  sbv_.TurnOn(idx++);
131  } while (iter.BfsMoveNext());
132 
133  NLIB_ASSERT(idx == 2 * num_nodes + 1);
134  if (!sbv_.Build()) {
135  sbv_.Reset();
136  return false;
137  }
138  return true;
139 }
140 
141 } // namespace succinct
142 NLIB_NAMESPACE_END
143 
144 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Louds)
145 
146 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
147 #undef NLIB_VIS_PUBLIC
148 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
149 #endif
150 
151 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
Defines the basic classes that form the basis to Rank and Select operations.
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
Gets the corresponding node ID from the bit array position.
Definition: Louds.h:55
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
Definition: Louds.h:110
constexpr Louds() noexcept
Instantiates the object with default parameters (default constructor). Requires initialization with I...
Definition: Louds.h:35
#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
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:72
Louds & operator=(Louds &&rhs) noexcept
Move assignment operator.
Definition: Louds.h:39
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
Gets the node ID of the parent node of the specified node.
Definition: Louds.h:101
Louds & assign(Louds &rhs, move_tag) noexcept
Corresponds to a move assignment operator.
Definition: Louds.h:45
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
Gets the node ID of the first child of the specified node.
Definition: Louds.h:86
uint32_t NodeId
Represents a node ID with a 32-bit non-negative integer.
Definition: Louds.h:33
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
Definition: Louds.h:108
bool Import(BinaryReader *r) noexcept
Reads the written object.
Definition: Louds.h:111
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:87
An empty structure indicating that an argument to a function needs to be moved.
Definition: Config.h:270
uint32_t Pos
Represents an index in the bit array with a 32-bit non-negative integer.
Definition: Louds.h:34
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
Gets the corresponding bit array position from the node ID.
Definition: Louds.h:59
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
Gets the node ID of the next sibling node of the specified node.
Definition: Louds.h:91
Louds(Louds &rhs, move_tag) noexcept
Corresponds to a move constructor.
Definition: Louds.h:44
~Louds() noexcept
Destructor.
Definition: Louds.h:36
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
Gets the bit array position of the next sibling node in the specified bit array position.
Definition: Louds.h:73
#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
void Reset() noexcept
Resets this object to the state immediately after the default constructor was executed.
Definition: Louds.h:109
Provides a compact tree structure that can provide various operations in constant time...
Definition: Louds.h:31
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
Gets the bit array position of the first child in the specified bit array position.
Definition: Louds.h:69
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
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
Louds(Louds &&rhs) noexcept
Instantiates the object (move constructor).
Definition: Louds.h:38
std::pair< bool, NodeId > GetNodeIdOfPrevSibling(NodeId nodeid) const noexcept
Gets the node ID of the previous sibling node of the specified node.
Definition: Louds.h:96
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
Gets the bit array position of the parent node in the specified bit array position.
Definition: Louds.h:81
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
Gets the bit array position of the previous sibling node in the specified bit array position...
Definition: Louds.h:77
bool IsLeaf(Pos pos) const noexcept
Determines whether the specified node is a leaf (or external) node.
Definition: Louds.h:107