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:
35 #ifdef __cpp_rvalue_references
36  Louds(Louds&& rhs) NLIB_NOEXCEPT : sbv_(std::move(rhs.sbv_)) {}
38  sbv_ = std::move(rhs.sbv_);
39  return *this;
40  }
41 #endif
42  Louds(Louds& rhs, move_tag) NLIB_NOEXCEPT // NOLINT
43  : sbv_(rhs.sbv_, move_tag()) {}
44  Louds& assign(Louds& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
45  sbv_.assign(rhs.sbv_, move_tag());
46  return *this;
47  }
48  NLIB_DEPRECATED void swap(Louds& rhs) NLIB_NOEXCEPT { // NOLINT
49  using std::swap;
50  swap(sbv_, rhs.sbv_);
51  }
52  template <class TREEITER>
53  bool Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
54 
55  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
56  int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
57  int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
58  int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
59  int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
60  int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
61  int Parent(uint32_t pos) const NLIB_NOEXCEPT;
62  bool IsLeaf(uint32_t pos) const NLIB_NOEXCEPT {
63  return this->FirstChild(pos) < 0;
64  }
65  size_t MemSize() const NLIB_NOEXCEPT { return sbv_.MemSize(); }
66  void Reset() NLIB_NOEXCEPT { sbv_.Reset(); }
67  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT { return sbv_.Export(w); }
68  bool Import(BinaryReader* r) NLIB_NOEXCEPT { return sbv_.Import(r); }
69 
70  private:
71  Sbv sbv_;
73 };
74 
75 template <class TREEITER>
76 bool Louds::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
77  // TREEITER has following methods:
78  // int GetNumChildren();
79  // bool BfsMoveNext(); // move to the next node by breadth first search
80  sbv_.Init(2 * num_nodes + 1);
81 
82  // diffrent from the Louds paper: reversed bits
83  sbv_.TurnOn(1);
84  uint32_t idx = 2; // consider super-root 01
85  do {
86  idx += iter.GetNumChildren();
87  sbv_.TurnOn(idx++);
88  } while (iter.BfsMoveNext());
89 
90  NLIB_ASSERT(idx == 2 * num_nodes + 1);
91  if (!sbv_.Build()) {
92  sbv_.Reset();
93  return false;
94  }
95  return true;
96 }
97 
98 } // namespace succinct
99 NLIB_NAMESPACE_END
100 
101 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Louds)
102 
103 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
104 #undef NLIB_VIS_PUBLIC
105 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
106 #endif
107 
108 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
rank/select操作をベースとした基本的なクラスが定義されています。
bool Export(BinaryWriter *w) const noexcept
オブジェクトを(ファイルに)書き出します。
Definition: Louds.h:67
constexpr Louds() noexcept
コンストラクタです。
Definition: Louds.h:33
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:179
Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
Definition: Sbv.h:73
Louds & operator=(Louds &&rhs) noexcept
ムーブ代入演算子です。C++11の利用時に有効です。
Definition: Louds.h:37
Louds & assign(Louds &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Definition: Louds.h:44
size_t MemSize() const noexcept
このクラスが明示的に確保するメモリ量を返します。
Definition: Louds.h:65
#define NLIB_DEPRECATED
関数等がdeprecatedになったことを示します。
Definition: Config.h:109
bool Import(BinaryReader *r) noexcept
書き出されたオブジェクトを読み出します。
Definition: Louds.h:68
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:89
void swap(Louds &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Louds.h:48
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:265
Louds(Louds &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
Definition: Louds.h:42
~Louds() noexcept
デストラクタです。
Definition: Louds.h:34
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:105
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:107
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: Louds.h:66
bool IsLeaf(uint32_t pos) const noexcept
ノードが葉ノードかどうかを判定します。
Definition: Louds.h:62
各種操作を で行うことができるコンパクトなツリー構造です。
Definition: Louds.h:31
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:245
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
Louds(Louds &&rhs) noexcept
ムーブコンストラクタです。C++11の利用時に有効です。
Definition: Louds.h:36