nlib
Trie.h
[詳解]
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
5 
6 #include <string.h>
7 
8 #include "nn/nlib/UniquePtr.h"
10 #include "nn/nlib/succinct/Sbv.h"
11 
12 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
13 #undef NLIB_VIS_PUBLIC
14 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
15 #endif
16 
17 NLIB_NAMESPACE_BEGIN
18 namespace succinct {
19 
21  public:
24  NLIB_MOVE_MEMBER_HELPER_3(Trie, m_Louds, m_IsTerminal, m_Labels);
25  void swap(Trie& rhs) NLIB_NOEXCEPT {
26  m_Louds.swap(rhs.m_Louds);
27  m_IsTerminal.swap(rhs.m_IsTerminal);
28  m_Labels.swap(rhs.m_Labels);
29  }
31  this->Reset();
32  return true;
33  }
34  typedef bool (*MatchCallback)(const char* first, const char* last, uint32_t nodeid,
35  void* user_obj);
36  void Match(const char* cstr, MatchCallback callback, void* user_obj = NULL) NLIB_NOEXCEPT {
37  this->Match(cstr, nlib_strlen(cstr), callback, user_obj);
38  }
39  NLIB_VIS_PUBLIC void Match(const void* data, size_t n, MatchCallback callback,
40  void* user_obj = NULL) NLIB_NOEXCEPT;
41  NLIB_VIS_PUBLIC void MatchBackward(const void* data, size_t n, MatchCallback callback,
42  void* user_obj = NULL) NLIB_NOEXCEPT;
43  NLIB_VIS_PUBLIC errno_t GetCommonPrefixWords(const void* prefix, size_t n,
44  ReallocCstringVec* vec) NLIB_NOEXCEPT;
45  void Reset() NLIB_NOEXCEPT {
46  m_Louds.Reset();
47  m_IsTerminal.Reset();
48  m_Labels.Reset();
49  }
50  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
52 
53  private:
54  NLIB_VIS_HIDDEN int Match_(const void* data, const unsigned char* p, uint32_t pos,
55  MatchCallback callback, void* user_obj, bool isfwd) NLIB_NOEXCEPT;
56 
57  private:
58  Louds m_Louds;
59  detail::BitVector32 m_IsTerminal;
60  detail::PlainArray32<unsigned char> m_Labels;
61  friend class TrieBuilder;
63 };
64 
66  public:
69  NLIB_VIS_PUBLIC bool Init() NLIB_NOEXCEPT;
70  NLIB_VIS_PUBLIC Trie* Build(ReallocVec<uint32_t>* keyids = NULL) NLIB_NOEXCEPT;
71  NLIB_VIS_PUBLIC bool AddWord(const char* str) NLIB_NOEXCEPT;
72  NLIB_VIS_PUBLIC bool AddPattern(const void* p, size_t n) NLIB_NOEXCEPT;
73  NLIB_VIS_PUBLIC bool AddWords(const char* str, size_t len) NLIB_NOEXCEPT;
74  bool AddWords(const char* str) NLIB_NOEXCEPT {
75  return AddWords(str, strlen(str));
76  }
77 
78  private:
79  ReallocCstringVec m_Words;
81 };
82 
83 } // namespace succinct
84 NLIB_NAMESPACE_END
85 
86 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
87 #undef NLIB_VIS_PUBLIC
88 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
89 #endif
90 
91 #endif // INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Platform.h:2151
Trieオブジェクトを作成するためのクラスです。
Definition: Trie.h:65
rank/select操作をベースとした基本的なクラスが定義されています。
LOUDSを構築したり、LOUDSにアクセスしたりするためのクラスが定義されています。
void swap(Trie &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Trie.h:25
Trie() noexcept
コンストラクタです。
Definition: Trie.h:22
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:126
void Match(const char *cstr, MatchCallback callback, void *user_obj=NULL) noexcept
文字列を検査してTrieに登録されている文字列を検出します。
Definition: Trie.h:36
~TrieBuilder() noexcept
デストラクタです。
Definition: Trie.h:68
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:214
#define NLIB_VIS_HIDDEN
関数やクラス等のシンボルをライブラリの外部に公開しません。
Definition: Platform_unix.h:50
LOUDSを利用したTrieの実装です。
Definition: Trie.h:20
std::unique_ptrに相当するクラスが定義されています。
bool Init() noexcept
オブジェクトの内容をリセットします。
Definition: Trie.h:30
TrieBuilder() noexcept
コンストラクタです。
Definition: Trie.h:67
~Trie() noexcept
デストラクタです。
Definition: Trie.h:23
各種操作を で行うことができるコンパクトなツリー構造です。
Definition: Louds.h:17
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:13
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:51
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:13
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:18
int errno_t
intのtypedefで、戻り値としてPOSIXのエラー値を返すことを示します。
Definition: NMalloc.h:24