nlib
Louds.h
[詳解]
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_
rank/select操作をベースとした基本的なクラスが定義されています。
std::pair< bool, NodeId > GetNodeIdByPos(Pos pos) const noexcept
ビット列の位置から対応するノードIDを取得します。
Definition: Louds.h:55
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
Definition: Louds.h:110
constexpr Louds() noexcept
デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
Definition: Louds.h:35
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:183
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:72
Louds & operator=(Louds &&rhs) noexcept
ムーブ代入演算子です。
Definition: Louds.h:39
std::pair< bool, NodeId > GetNodeIdOfParent(NodeId nodeid) const noexcept
指定されたノードの親ノードのノードIDを取得します。
Definition: Louds.h:101
Louds & assign(Louds &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Definition: Louds.h:45
std::pair< bool, NodeId > GetNodeIdOfFirstChild(NodeId nodeid) const noexcept
指定されたノードの最初の子のノードIDを取得します。
Definition: Louds.h:86
uint32_t NodeId
32bit非負整数でノードIDを表します。
Definition: Louds.h:33
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
Definition: Louds.h:108
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
Definition: Louds.h:111
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:87
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:270
uint32_t Pos
32bit非負整数でビット列上のインデックスを表します。
Definition: Louds.h:34
std::pair< bool, Pos > GetPosByNodeId(NodeId nodeid) const noexcept
ノードIDから対応するビット列での位置を取得します。
Definition: Louds.h:59
std::pair< bool, NodeId > GetNodeIdOfNextSibling(NodeId nodeid) const noexcept
指定されたノードの次の兄弟ノードのノードIDを取得します。
Definition: Louds.h:91
Louds(Louds &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
Definition: Louds.h:44
~Louds() noexcept
デストラクタです。
Definition: Louds.h:36
std::pair< bool, Pos > GetPosOfNextSibling(Pos pos) const noexcept
指定されたビット列上の位置の次の兄弟ノードのビット列上の位置を取得します。
Definition: Louds.h:73
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:111
void Reset() noexcept
このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
Definition: Louds.h:109
各種操作を で行うことができるコンパクトなツリー構造です。
Definition: Louds.h:31
std::pair< bool, Pos > GetPosOfFirstChild(Pos pos) const noexcept
指定されたビット列上の位置の最初の子のビット列上の位置を取得します。
Definition: Louds.h:69
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:250
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
Louds(Louds &&rhs) noexcept
ムーブコンストラクタです。
Definition: Louds.h:38
std::pair< bool, NodeId > GetNodeIdOfPrevSibling(NodeId nodeid) const noexcept
指定されたノードの前の兄弟ノードのノードIDを取得します。
Definition: Louds.h:96
std::pair< bool, Pos > GetPosOfParent(Pos pos) const noexcept
指定されたビット列上の位置の親ノードのビット列上の位置を取得します。
Definition: Louds.h:81
std::pair< bool, Pos > GetPosOfPrevSibling(Pos pos) const noexcept
指定されたビット列上の位置の前の兄弟ノードのビット列上の位置を取得します。
Definition: Louds.h:77
bool IsLeaf(Pos pos) const noexcept
ノードが葉ノードかどうかを判定します。
Definition: Louds.h:107