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/bsdiff/qsufsort.h" | 5 #include "courgette/third_party/bsdiff/qsufsort.h" |
6 | 6 |
7 #include <stddef.h> | |
8 | |
9 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <cstddef> |
10 #include <cstring> | 9 #include <cstring> |
11 #include <string> | |
12 #include <vector> | 10 #include <vector> |
13 | 11 |
14 #include "base/macros.h" | 12 #include "base/macros.h" |
15 #include "testing/gtest/include/gtest/gtest.h" | 13 #include "testing/gtest/include/gtest/gtest.h" |
16 | 14 |
| 15 namespace { |
| 16 |
| 17 bool IsPermutation(const std::vector<int> v) { |
| 18 std::vector<int> v_sorted(v); |
| 19 std::sort(v_sorted.begin(), v_sorted.end()); |
| 20 for (int i = 0; i < static_cast<int>(v.size()); ++i) |
| 21 if (i != v_sorted[i]) |
| 22 return false; |
| 23 return true; |
| 24 } |
| 25 |
| 26 } // namespace |
| 27 |
17 TEST(QSufSortTest, Sort) { | 28 TEST(QSufSortTest, Sort) { |
18 const char* test_cases[] = { | 29 const char* test_cases[] = { |
19 "", | 30 "", |
20 "a", | 31 "a", |
21 "za", | 32 "za", |
22 "CACAO", | 33 "CACAO", |
23 "banana", | 34 "banana", |
24 "tobeornottobe", | 35 "tobeornottobe", |
25 "The quick brown fox jumps over the lazy dog.", | 36 "The quick brown fox jumps over the lazy dog.", |
26 "elephantelephantelephantelephantelephant", | 37 "elephantelephantelephantelephantelephant", |
27 "-------------------------", | 38 "-------------------------", |
28 "011010011001011010010110011010010", | 39 "011010011001011010010110011010010", |
29 "3141592653589793238462643383279502884197169399375105", | 40 "3141592653589793238462643383279502884197169399375105", |
30 "\xFF\xFE\xFF\xFE\xFD\x80\x30\x31\x32\x80\x30\xFF\x01\xAB\xCD", | 41 "\xFF\xFE\xFF\xFE\xFD\x80\x30\x31\x32\x80\x30\xFF\x01\xAB\xCD", |
31 }; | 42 }; |
32 | 43 |
33 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | 44 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { |
34 int len = static_cast<int>(::strlen(test_cases[idx])); | 45 int size = static_cast<int>(::strlen(test_cases[idx])); |
35 const unsigned char* s = | 46 const unsigned char* buf = |
36 reinterpret_cast<const unsigned char*>(test_cases[idx]); | 47 reinterpret_cast<const unsigned char*>(test_cases[idx]); |
37 | 48 |
38 // Generate the suffix array as I. | 49 // Generate the suffix array as I. |
39 std::vector<int> I(len + 1); | 50 std::vector<int> I(size + 1); |
40 std::vector<int> V(len + 1); | 51 std::vector<int> V(size + 1); |
41 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], s, len); | 52 qsuf::qsufsort<int*>(&I[0], &V[0], buf, size); |
42 | 53 |
43 // Expect that I[] is a permutation of [0, len]. | 54 // Expect I[] and V[] to be a permutation of [0, size]. |
44 std::vector<int> I_sorted(I); | 55 EXPECT_TRUE(IsPermutation(I)); |
45 std::sort(I_sorted.begin(), I_sorted.end()); | 56 EXPECT_TRUE(IsPermutation(V)); |
46 for (int i = 0; i < len + 1; ++i) | 57 |
47 EXPECT_EQ(i, I_sorted[i]); | 58 // Expect V[] to be inverse of I[]. |
| 59 for (int i = 0; i < size + 1; ++i) |
| 60 EXPECT_EQ(i, V[I[i]]); |
48 | 61 |
49 // First string must be empty string. | 62 // First string must be empty string. |
50 EXPECT_EQ(len, I[0]); | 63 EXPECT_EQ(size, I[0]); |
51 | 64 |
52 // Expect that the |len + 1| suffixes are strictly ordered. | 65 // Expect that the |size + 1| suffixes are strictly ordered. |
53 const unsigned char* end = s + len; | 66 const unsigned char* end = buf + size; |
54 for (int i = 0; i < len; ++i) { | 67 for (int i = 0; i < size; ++i) { |
55 const unsigned char* suf1 = s + I[i]; | 68 const unsigned char* suf1 = buf + I[i]; |
56 const unsigned char* suf2 = s + I[i + 1]; | 69 const unsigned char* suf2 = buf + I[i + 1]; |
57 bool is_less = std::lexicographical_compare(suf1, end, suf2, end); | 70 bool is_less = std::lexicographical_compare(suf1, end, suf2, end); |
58 EXPECT_TRUE(is_less); | 71 EXPECT_TRUE(is_less); |
59 } | 72 } |
60 } | 73 } |
61 } | 74 } |
OLD | NEW |