OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "courgette/third_party/qsufsort.h" | 5 #include "courgette/third_party/qsufsort.h" |
6 | 6 |
7 #include <stddef.h> | 7 #include <stddef.h> |
8 | 8 |
9 #include <algorithm> | 9 #include <algorithm> |
10 #include <cstring> | 10 #include <cstring> |
(...skipping 20 matching lines...) Expand all Loading... |
31 }; | 31 }; |
32 | 32 |
33 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | 33 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { |
34 int len = static_cast<int>(::strlen(test_cases[idx])); | 34 int len = static_cast<int>(::strlen(test_cases[idx])); |
35 const unsigned char* s = | 35 const unsigned char* s = |
36 reinterpret_cast<const unsigned char*>(test_cases[idx]); | 36 reinterpret_cast<const unsigned char*>(test_cases[idx]); |
37 | 37 |
38 // Generate the suffix array as I. | 38 // Generate the suffix array as I. |
39 std::vector<int> I(len + 1); | 39 std::vector<int> I(len + 1); |
40 std::vector<int> V(len + 1); | 40 std::vector<int> V(len + 1); |
41 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], s, len); | 41 courgette::qsuf::qsufsort<std::vector<int>&>(I, V, s, len); |
42 | 42 |
43 // Expect that I[] is a permutation of [0, len]. | 43 // Expect that I[] is a permutation of [0, len]. |
44 std::vector<int> I_sorted(I); | 44 std::vector<int> I_sorted(I); |
45 std::sort(I_sorted.begin(), I_sorted.end()); | 45 std::sort(I_sorted.begin(), I_sorted.end()); |
46 for (int i = 0; i < len + 1; ++i) { | 46 for (int i = 0; i < len + 1; ++i) { |
47 EXPECT_EQ(i, I_sorted[i]) << "test_case[" << idx << "]"; | 47 EXPECT_EQ(i, I_sorted[i]) << "test_case[" << idx << "]"; |
48 } | 48 } |
49 | 49 |
50 // First string must be empty string. | 50 // First string must be empty string. |
51 EXPECT_EQ(len, I[0]) << "test_case[" << idx << "]"; | 51 EXPECT_EQ(len, I[0]) << "test_case[" << idx << "]"; |
(...skipping 12 matching lines...) Expand all Loading... |
64 TEST(QSufSortTest, Search) { | 64 TEST(QSufSortTest, Search) { |
65 // Initialize main string and the suffix array. | 65 // Initialize main string and the suffix array. |
66 // Positions: 00000000001111111111122222222233333333334444 | 66 // Positions: 00000000001111111111122222222233333333334444 |
67 // 01234567890123456789012345678901234567890123 | 67 // 01234567890123456789012345678901234567890123 |
68 const char* old_str = "the quick brown fox jumps over the lazy dog."; | 68 const char* old_str = "the quick brown fox jumps over the lazy dog."; |
69 int old_size = static_cast<int>(::strlen(old_str)); | 69 int old_size = static_cast<int>(::strlen(old_str)); |
70 const unsigned char* old_buf = | 70 const unsigned char* old_buf = |
71 reinterpret_cast<const unsigned char*>(old_str); | 71 reinterpret_cast<const unsigned char*>(old_str); |
72 std::vector<int> I(old_size + 1); | 72 std::vector<int> I(old_size + 1); |
73 std::vector<int> V(old_size + 1); | 73 std::vector<int> V(old_size + 1); |
74 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], old_buf, old_size); | 74 courgette::qsuf::qsufsort<std::vector<int>&>(I, V, old_buf, old_size); |
75 | 75 |
76 // Test queries. | 76 // Test queries. |
77 const struct { | 77 const struct { |
78 int exp_pos; // -1 means "don't care". | 78 int exp_pos; // -1 means "don't care". |
79 int exp_match_len; | 79 int exp_match_len; |
80 const char* query_str; | 80 const char* query_str; |
81 } test_cases[] = { | 81 } test_cases[] = { |
82 // Entire string. | 82 // Entire string. |
83 {0, 44, "the quick brown fox jumps over the lazy dog."}, | 83 {0, 44, "the quick brown fox jumps over the lazy dog."}, |
84 // Empty string. | 84 // Empty string. |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
127 EXPECT_LE(pos, old_size - match_len) << "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)) | 128 EXPECT_EQ(0, ::memcmp(old_buf + pos, new_buf, match_len)) |
129 << "test_case[" << idx << "]"; | 129 << "test_case[" << idx << "]"; |
130 } | 130 } |
131 if (test_case.exp_pos >= 0) { | 131 if (test_case.exp_pos >= 0) { |
132 EXPECT_EQ(test_case.exp_pos, pos) << "test_case[" << idx << "]"; | 132 EXPECT_EQ(test_case.exp_pos, pos) << "test_case[" << idx << "]"; |
133 } | 133 } |
134 EXPECT_EQ(test_case.exp_match_len, match_len) << "test_case[" << idx << "]"; | 134 EXPECT_EQ(test_case.exp_match_len, match_len) << "test_case[" << idx << "]"; |
135 } | 135 } |
136 } | 136 } |
OLD | NEW |