OLD | NEW |
| (Empty) |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "courgette/third_party/qsufsort.h" | |
6 | |
7 #include <stddef.h> | |
8 | |
9 #include <algorithm> | |
10 #include <cstring> | |
11 #include <string> | |
12 #include <vector> | |
13 | |
14 #include "base/macros.h" | |
15 #include "testing/gtest/include/gtest/gtest.h" | |
16 | |
17 TEST(QSufSortTest, Sort) { | |
18 const char* test_cases[] = { | |
19 "", | |
20 "a", | |
21 "za", | |
22 "CACAO", | |
23 "banana", | |
24 "tobeornottobe", | |
25 "The quick brown fox jumps over the lazy dog.", | |
26 "elephantelephantelephantelephantelephant", | |
27 "-------------------------", | |
28 "011010011001011010010110011010010", | |
29 "3141592653589793238462643383279502884197169399375105", | |
30 "\xFF\xFE\xFF\xFE\xFD\x80\x30\x31\x32\x80\x30\xFF\x01\xAB\xCD", | |
31 }; | |
32 | |
33 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | |
34 int len = static_cast<int>(::strlen(test_cases[idx])); | |
35 const unsigned char* s = | |
36 reinterpret_cast<const unsigned char*>(test_cases[idx]); | |
37 | |
38 // Generate the suffix array as I. | |
39 std::vector<int> I(len + 1); | |
40 std::vector<int> V(len + 1); | |
41 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], s, len); | |
42 | |
43 // Expect that I[] is a permutation of [0, len]. | |
44 std::vector<int> I_sorted(I); | |
45 std::sort(I_sorted.begin(), I_sorted.end()); | |
46 for (int i = 0; i < len + 1; ++i) { | |
47 EXPECT_EQ(i, I_sorted[i]) << "test_case[" << idx << "]"; | |
48 } | |
49 | |
50 // First string must be empty string. | |
51 EXPECT_EQ(len, I[0]) << "test_case[" << idx << "]"; | |
52 | |
53 // Expect that the |len + 1| suffixes are strictly ordered. | |
54 const unsigned char* end = s + len; | |
55 for (int i = 0; i < len; ++i) { | |
56 const unsigned char* suf1 = s + I[i]; | |
57 const unsigned char* suf2 = s + I[i + 1]; | |
58 bool is_less = std::lexicographical_compare(suf1, end, suf2, end); | |
59 EXPECT_TRUE(is_less) << "test_case[" << idx << "]"; | |
60 } | |
61 } | |
62 } | |
63 | |
64 TEST(QSufSortTest, Search) { | |
65 // Initialize main string and the suffix array. | |
66 // Positions: 00000000001111111111122222222233333333334444 | |
67 // 01234567890123456789012345678901234567890123 | |
68 const char* old_str = "the quick brown fox jumps over the lazy dog."; | |
69 int old_size = static_cast<int>(::strlen(old_str)); | |
70 const unsigned char* old_buf = | |
71 reinterpret_cast<const unsigned char*>(old_str); | |
72 std::vector<int> I(old_size + 1); | |
73 std::vector<int> V(old_size + 1); | |
74 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], old_buf, old_size); | |
75 | |
76 // Test queries. | |
77 const struct { | |
78 int exp_pos; // -1 means "don't care". | |
79 int exp_match_len; | |
80 const char* query_str; | |
81 } test_cases[] = { | |
82 // Entire string. | |
83 {0, 44, "the quick brown fox jumps over the lazy dog."}, | |
84 // Empty string. | |
85 {-1, 0, ""}, // Current algorithm does not enforce |pos| == 0. | |
86 // Exact and unique suffix match. | |
87 {43, 1, "."}, | |
88 {31, 13, "the lazy dog."}, | |
89 // Exact and unique non-suffix match. | |
90 {4, 5, "quick"}, | |
91 {0, 9, "the quick"}, // Unique prefix. | |
92 // Entire word match with mutiple results: take lexicographical first. | |
93 {31, 3, "the"}, // Non-unique prefix: "the l"... < "the q"... | |
94 {9, 1, " "}, // " brown"... wins. | |
95 // Partial and unique match of query prefix. | |
96 {16, 10, "fox jumps with the hosps"}, | |
97 // Partial and multiple match of query prefix: no guarantees on |pos|. | |
98 // Take lexicographical first for matching portion *only*, so same results: | |
99 {-1, 4, "the apple"}, // query < "the l"... < "the q"... | |
100 {-1, 4, "the opera"}, // "the l"... < query < "the q"... | |
101 {-1, 4, "the zebra"}, // "the l"... < "the q"... < query | |
102 // Prefix match dominates suffix match. | |
103 {26, 5, "over quick brown fox"}, | |
104 // No match. | |
105 {-1, 0, ","}, | |
106 {-1, 0, "1234"}, | |
107 {-1, 0, "THE QUICK BROWN FOX"}, | |
108 {-1, 0, "(the"}, | |
109 }; | |
110 | |
111 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | |
112 const auto& test_case = test_cases[idx]; | |
113 int new_size = static_cast<int>(::strlen(test_case.query_str)); | |
114 const unsigned char* new_buf = | |
115 reinterpret_cast<const unsigned char*>(test_case.query_str); | |
116 | |
117 // Perform the search. | |
118 int pos = 0; | |
119 int match_len = courgette::qsuf::search( | |
120 &I[0], old_buf, old_size, new_buf, new_size, &pos); | |
121 | |
122 // Check basic properties and match with expected values. | |
123 EXPECT_GE(match_len, 0) << "test_case[" << idx << "]"; | |
124 EXPECT_LE(match_len, new_size) << "test_case[" << idx << "]"; | |
125 if (match_len > 0) { | |
126 EXPECT_GE(pos, 0) << "test_case[" << idx << "]"; | |
127 EXPECT_LE(pos, old_size - match_len) << "test_case[" << idx << "]"; | |
128 EXPECT_EQ(0, ::memcmp(old_buf + pos, new_buf, match_len)) | |
129 << "test_case[" << idx << "]"; | |
130 } | |
131 if (test_case.exp_pos >= 0) { | |
132 EXPECT_EQ(test_case.exp_pos, pos) << "test_case[" << idx << "]"; | |
133 } | |
134 EXPECT_EQ(test_case.exp_match_len, match_len) << "test_case[" << idx << "]"; | |
135 } | |
136 } | |
OLD | NEW |