1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#pragma once
#include "comptrie_trie.h"
#include "first_symbol_iterator.h"
#include <util/str_stl.h>
#include <util/digest/numeric.h>
#include <util/digest/multi.h>
// Iterator for incremental searching.
// All Advance() methods shift the iterator using specifed key/char.
// The subsequent Advance() call starts searching from the previous state.
// The Advance() returns 'true' if specified key part exists in the trie and
// returns 'false' for unsuccessful search. In case of 'false' result
// all subsequent calls also will return 'false'.
// If current iterator state is final then GetValue() method returns 'true' and
// associated value.
template <class TTrie>
class TSearchIterator {
public:
using TData = typename TTrie::TData;
using TSymbol = typename TTrie::TSymbol;
using TKeyBuf = typename TTrie::TKeyBuf;
TSearchIterator() = default;
explicit TSearchIterator(const TTrie& trie)
: Trie(&trie)
, DataPos(trie.DataHolder.AsCharPtr())
, DataEnd(DataPos + trie.DataHolder.Length())
, ValuePos(trie.EmptyValue)
{
}
explicit TSearchIterator(const TTrie& trie, const TTrie& subTrie)
: Trie(&trie)
, DataPos(subTrie.Data().AsCharPtr())
, DataEnd(trie.DataHolder.AsCharPtr() + trie.DataHolder.Length())
, ValuePos(subTrie.EmptyValue)
{
}
bool operator==(const TSearchIterator& other) const {
Y_ASSERT(Trie && other.Trie);
return Trie == other.Trie &&
DataPos == other.DataPos &&
DataEnd == other.DataEnd &&
ValuePos == other.ValuePos;
}
bool operator!=(const TSearchIterator& other) const {
return !(*this == other);
}
inline bool Advance(TSymbol label) {
Y_ASSERT(Trie);
if (DataPos == nullptr || DataPos >= DataEnd) {
return false;
}
return NCompactTrie::Advance(DataPos, DataEnd, ValuePos, label, Trie->Packer);
}
inline bool Advance(const TKeyBuf& key) {
return Advance(key.data(), key.size());
}
bool Advance(const TSymbol* key, size_t keylen);
bool GetValue(TData* value = nullptr) const;
bool HasValue() const;
inline size_t GetHash() const;
private:
const TTrie* Trie = nullptr;
const char* DataPos = nullptr;
const char* DataEnd = nullptr;
const char* ValuePos = nullptr;
};
template <class TTrie>
inline TSearchIterator<TTrie> MakeSearchIterator(const TTrie& trie) {
return TSearchIterator<TTrie>(trie);
}
template <class TTrie>
struct THash<TSearchIterator<TTrie>> {
inline size_t operator()(const TSearchIterator<TTrie>& item) {
return item.GetHash();
}
};
//----------------------------------------------------------------------------
template <class TTrie>
bool TSearchIterator<TTrie>::Advance(const TSymbol* key, size_t keylen) {
Y_ASSERT(Trie);
if (!key || DataPos == nullptr || DataPos >= DataEnd) {
return false;
}
if (!keylen) {
return true;
}
const TSymbol* keyend = key + keylen;
while (key != keyend && DataPos != nullptr) {
if (!NCompactTrie::Advance(DataPos, DataEnd, ValuePos, *(key++), Trie->Packer)) {
return false;
}
if (key == keyend) {
return true;
}
}
return false;
}
template <class TTrie>
bool TSearchIterator<TTrie>::GetValue(TData* value) const {
Y_ASSERT(Trie);
bool result = false;
if (value) {
if (ValuePos) {
result = true;
Trie->Packer.UnpackLeaf(ValuePos, *value);
}
}
return result;
}
template <class TTrie>
bool TSearchIterator<TTrie>::HasValue() const {
Y_ASSERT(Trie);
return ValuePos;
}
template <class TTrie>
inline size_t TSearchIterator<TTrie>::GetHash() const {
Y_ASSERT(Trie);
return MultiHash(
static_cast<const void*>(Trie),
static_cast<const void*>(DataPos),
static_cast<const void*>(DataEnd),
static_cast<const void*>(ValuePos));
}
|
