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 
9 #include "nn/nlib/succinct/Sbv.h"
10 #include "nn/nlib/ReallocVec.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:
22  Trie() NLIB_NOEXCEPT : prv_(NULL) {}
24  NLIB_MOVE_MEMBER_HELPER_1(Trie, prv_);
25  void swap(Trie& rhs) NLIB_NOEXCEPT {
26  TriePrivate* tmp = rhs.prv_;
27  rhs.prv_ = this->prv_;
28  this->prv_ = tmp;
29  }
30  bool Init() NLIB_NOEXCEPT;
31  typedef bool (*MatchCallback)(const char* first, const char* last, uint32_t nodeid,
32  void* user_obj);
33  void Match(const char* cstr, MatchCallback callback, void* user_obj = NULL) NLIB_NOEXCEPT {
34  this->Match(cstr, nlib_strlen(cstr), callback, user_obj);
35  }
36  void Match(const void* data, size_t n, MatchCallback callback, void* user_obj) NLIB_NOEXCEPT;
37  void Match(const void* data, size_t n, MatchCallback callback) NLIB_NOEXCEPT {
38  Match(data, n, callback, NULL);
39  }
40  void MatchBackward(const void* data, size_t n, MatchCallback callback,
41  void* user_obj) NLIB_NOEXCEPT;
42  void MatchBackward(const void* data, size_t n, MatchCallback callback) NLIB_NOEXCEPT {
43  MatchBackward(data, n, callback, NULL);
44  }
45  errno_t GetCommonPrefixWords(const void* prefix, size_t n,
47  void Reset() NLIB_NOEXCEPT;
48  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
49  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
50 
51  private:
52  NLIB_VIS_HIDDEN int Match_(const void* data, const unsigned char* p, uint32_t pos,
53  MatchCallback callback, void* user_obj, bool isfwd) NLIB_NOEXCEPT;
54 
55  private:
56  struct TriePrivate;
57  TriePrivate* prv_;
58  friend class TrieBuilder;
60 };
61 
63  public:
64  TrieBuilder() NLIB_NOEXCEPT : prv_(NULL) {}
66  bool Init() NLIB_NOEXCEPT;
67  Trie* Build(ReallocVec<uint32_t>* keyids = NULL) NLIB_NOEXCEPT;
68  bool AddWord(const char* str) NLIB_NOEXCEPT;
69  bool AddPattern(const void* p, size_t n) NLIB_NOEXCEPT;
70  bool AddWords(const char* str, size_t len) NLIB_NOEXCEPT;
71  bool AddWords(const char* str) NLIB_NOEXCEPT {
72  return AddWords(str, strlen(str));
73  }
74 
75  private:
76  struct TrieBuilderPrivate;
77  TrieBuilderPrivate* prv_;
79 };
80 
81 } // namespace succinct
82 NLIB_NAMESPACE_END
83 
84 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
85 #undef NLIB_VIS_PUBLIC
86 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
87 #endif
88 
89 #endif // INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
Trieオブジェクトを作成するためのクラスです。
Definition: Trie.h:62
rank/select操作をベースとした基本的なクラスが定義されています。
LOUDSを構築したり、LOUDSにアクセスしたりするためのクラスが定義されています。
void swap(Trie &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Trie.h:25
Trie() noexcept
コンストラクタです。
Definition: Trie.h:22
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:145
void Match(const char *cstr, MatchCallback callback, void *user_obj=NULL) noexcept
文字列を検査してTrieに登録されている文字列を検出します。
Definition: Trie.h:33
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:214
LOUDSを利用したTrieの実装です。
Definition: Trie.h:20
#define NLIB_VIS_HIDDEN
関数やクラス等のシンボルをライブラリの外部に公開しません。
Definition: Platform_unix.h:60
bool AddWords(const char *str) noexcept
検出対象の文字列の集合が入った配列から文字列を追加します。文字列の区切りは改行(CRLFかLF)である必要が...
Definition: Trie.h:71
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:61
TrieBuilder() noexcept
コンストラクタです。
Definition: Trie.h:64
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:86
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:13
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:211
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:13
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:18
int errno_t
intのtypedefで、戻り値としてPOSIXのエラー値を返すことを示します。
Definition: NMalloc.h:24