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