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
|
#include "testing/testing.hpp"
#include "base/dfa_helpers.hpp"
#include "base/levenshtein_dfa.hpp"
#include "std/string.hpp"
using namespace strings;
namespace
{
enum class Status
{
Accepts,
Rejects,
Intermediate
};
Status GetStatus(LevenshteinDFA const & dfa, string const & s)
{
auto it = dfa.Begin();
DFAMove(it, s);
if (it.Accepts())
return Status::Accepts;
if (it.Rejects())
return Status::Rejects;
return Status::Intermediate;
}
bool Accepts(LevenshteinDFA const & dfa, string const & s)
{
return GetStatus(dfa, s) == Status::Accepts;
}
bool Rejects(LevenshteinDFA const & dfa, string const & s)
{
return GetStatus(dfa, s) == Status::Rejects;
}
bool Intermediate(LevenshteinDFA const & dfa, string const & s)
{
return GetStatus(dfa, s) == Status::Intermediate;
}
UNIT_TEST(LevenshteinDFA_Smoke)
{
{
LevenshteinDFA dfa("", 0 /* maxErrors */);
auto it = dfa.Begin();
TEST(it.Accepts(), ());
TEST(!it.Rejects(), ());
it.Move('a');
TEST(!it.Accepts(), ());
TEST(it.Rejects(), ());
it.Move('b');
TEST(!it.Accepts(), ());
TEST(it.Rejects(), ());
}
{
LevenshteinDFA dfa("abc", 1 /* maxErrors */);
TEST(Accepts(dfa, "ab"), ());
TEST(Accepts(dfa, "abd"), ());
TEST(Accepts(dfa, "abcd"), ());
TEST(Accepts(dfa, "bbc"), ());
TEST(Rejects(dfa, "cba"), ());
TEST(Rejects(dfa, "abcde"), ());
TEST(Accepts(dfa, "ac"), ());
TEST(Intermediate(dfa, "acb"), ()); // transpositions are not supported yet
TEST(Accepts(dfa, "acbc"), ());
TEST(Rejects(dfa, "acbd"), ());
TEST(Intermediate(dfa, "a"), ());
}
{
LevenshteinDFA dfa("ленинградский", 2 /* maxErrors */);
TEST(Accepts(dfa, "ленинградский"), ());
TEST(Accepts(dfa, "ленингадский"), ());
TEST(Accepts(dfa, "ленигнрадский"), ());
TEST(Rejects(dfa, "ленинский"), ());
}
{
LevenshteinDFA dfa("atm", 1 /* maxErrors */);
TEST(Rejects(dfa, "san"), ());
}
}
} // namespace
|
