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
|
#include "testing/testing.hpp"
#include "base/suffix_array.hpp"
#include <cstring>
#include <string>
#include <vector>
using namespace base;
using namespace std;
#define TEST_STR_EQUAL(X, Y, msg) TEST_EQUAL(string(X), string(Y), msg)
namespace
{
UNIT_TEST(Skew_Smoke) { Skew(0, nullptr /* s */, nullptr /* sa */); }
UNIT_TEST(Skew_Simple)
{
{
string const s;
vector<size_t> pos;
Skew(s, pos);
TEST_EQUAL(pos.size(), s.size(), ());
}
{
string const s = "a";
vector<size_t> pos;
Skew(s, pos);
TEST_EQUAL(pos.size(), s.size(), ());
TEST_EQUAL(pos[0], 0, ());
}
{
string const s = "aaaa";
vector<size_t> pos;
Skew(s, pos);
TEST_EQUAL(pos.size(), s.size(), ());
TEST_EQUAL(pos[0], 3, ());
TEST_EQUAL(pos[1], 2, ());
TEST_EQUAL(pos[2], 1, ());
TEST_EQUAL(pos[3], 0, ());
}
{
for (size_t length = 0; length < 100; ++length)
{
string const s(length, 'a');
vector<size_t> pos;
Skew(s, pos);
TEST_EQUAL(pos.size(), s.size(), ());
for (size_t i = 0; i < pos.size(); ++i)
TEST_EQUAL(pos[i], pos.size() - i - 1, ());
}
}
}
UNIT_TEST(Skew_Classic)
{
char const * s = "mississippi";
size_t const n = strlen(s);
vector<size_t> pos(n);
Skew(n, reinterpret_cast<const uint8_t *>(s), pos.data());
TEST_STR_EQUAL("i", s + pos[0], ());
TEST_STR_EQUAL("ippi", s + pos[1], ());
TEST_STR_EQUAL("issippi", s + pos[2], ());
TEST_STR_EQUAL("ississippi", s + pos[3], ());
TEST_STR_EQUAL("mississippi", s + pos[4], ());
TEST_STR_EQUAL("pi", s + pos[5], ());
TEST_STR_EQUAL("ppi", s + pos[6], ());
TEST_STR_EQUAL("sippi", s + pos[7], ());
TEST_STR_EQUAL("sissippi", s + pos[8], ());
TEST_STR_EQUAL("ssippi", s + pos[9], ());
TEST_STR_EQUAL("ssissippi", s + pos[10], ());
}
} // namespace
|
