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
|
#ifndef MORPHTRIE_H_
#define MORPHTRIE_H_
#include <vector>
#include "Node.h"
namespace Moses2
{
template<class KeyClass, class ValueClass>
class MorphTrie
{
public:
MorphTrie()
{
}
Node<KeyClass, ValueClass>* insert(const std::vector<KeyClass>& word,
const ValueClass& value);
const Node<KeyClass, ValueClass>* getNode(
const std::vector<KeyClass>& words) const;
const Node<KeyClass, ValueClass> &getNode(const std::vector<KeyClass>& words,
size_t &stoppedAtInd) const;
std::vector<const Node<KeyClass, ValueClass>*> getNodes(
const std::vector<KeyClass>& words, size_t &stoppedAtInd) const;
private:
Node<KeyClass, ValueClass> root;
};
template<class KeyClass, class ValueClass>
Node<KeyClass, ValueClass>* MorphTrie<KeyClass, ValueClass>::insert(
const std::vector<KeyClass>& word, const ValueClass& value)
{
Node<KeyClass, ValueClass>* cNode = &root;
for (size_t i = 0; i < word.size(); ++i) {
KeyClass cKey = word[i];
cNode = cNode->addSubnode(cKey);
}
cNode->setValue(value);
return cNode;
}
template<class KeyClass, class ValueClass>
const Node<KeyClass, ValueClass>* MorphTrie<KeyClass, ValueClass>::getNode(
const std::vector<KeyClass>& words) const
{
size_t stoppedAtInd;
const Node<KeyClass, ValueClass> &ret = getNode(words, stoppedAtInd);
if (stoppedAtInd < words.size()) {
return NULL;
}
return &ret;
}
template<class KeyClass, class ValueClass>
const Node<KeyClass, ValueClass> &MorphTrie<KeyClass, ValueClass>::getNode(
const std::vector<KeyClass>& words, size_t &stoppedAtInd) const
{
const Node<KeyClass, ValueClass> *prevNode = &root, *newNode;
for (size_t i = 0; i < words.size(); ++i) {
const KeyClass &cKey = words[i];
newNode = prevNode->findSub(cKey);
if (newNode == NULL) {
stoppedAtInd = i;
return *prevNode;
}
prevNode = newNode;
}
stoppedAtInd = words.size();
return *newNode;
}
template<class KeyClass, class ValueClass>
std::vector<const Node<KeyClass, ValueClass>*> MorphTrie<KeyClass, ValueClass>::getNodes(
const std::vector<KeyClass>& words, size_t &stoppedAtInd) const
{
std::vector<const Node<KeyClass, ValueClass>*> ret;
const Node<KeyClass, ValueClass> *prevNode = &root, *newNode;
ret.push_back(prevNode);
for (size_t i = 0; i < words.size(); ++i) {
const KeyClass &cKey = words[i];
newNode = prevNode->findSub(cKey);
if (newNode == NULL) {
stoppedAtInd = i;
return ret;
}
else {
ret.push_back(newNode);
}
prevNode = newNode;
}
stoppedAtInd = words.size();
return ret;
}
}
#endif /* end of include guard: MORPHTRIE_H_ */
|
