OLD | NEW |
(Empty) | |
| 1 // Copyright 2016 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/divsufsort/divsufsort.h" |
| 6 |
| 7 #include <algorithm> |
| 8 #include <memory> |
| 9 #include <numeric> |
| 10 #include <string> |
| 11 #include <vector> |
| 12 |
| 13 #include "courgette/third_party/bsdiff/bsdiff_search.h" |
| 14 #include "courgette/third_party/bsdiff/paged_array.h" |
| 15 #include "testing/gtest/include/gtest/gtest.h" |
| 16 |
| 17 TEST(DivSufSortTest, Sort) { |
| 18 const char* test_strs[] = { |
| 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 (const std::string& test_str : test_strs) { |
| 34 int len = static_cast<int>(test_str.length()); |
| 35 const unsigned char* buf = |
| 36 reinterpret_cast<const unsigned char*>(test_str.data()); |
| 37 |
| 38 // Generate the suffix array as I. |
| 39 courgette::PagedArray<divsuf::saidx_t> I; |
| 40 ASSERT_TRUE(I.Allocate(len + 1)); |
| 41 divsuf::divsufsort_include_empty(buf, I.begin(), len); |
| 42 |
| 43 // Expect that I[] is a permutation of [0, len]. |
| 44 std::vector<divsuf::saidx_t> I_sorted(I.begin(), I.end()); |
| 45 std::sort(I_sorted.begin(), I_sorted.end()); |
| 46 for (divsuf::saidx_t i = 0; i < len + 1; ++i) |
| 47 EXPECT_EQ(i, I_sorted[i]); |
| 48 |
| 49 // First string must be empty string. |
| 50 EXPECT_EQ(len, I[0]); |
| 51 |
| 52 // Expect that the |len + 1| suffixes are strictly ordered. |
| 53 const unsigned char* end = buf + len; |
| 54 for (divsuf::saidx_t i = 1; i <= len; ++i) { |
| 55 const unsigned char* suf1 = buf + I[i - 1]; |
| 56 const unsigned char* suf2 = buf + I[i]; |
| 57 bool is_less = std::lexicographical_compare(suf1, end, suf2, end); |
| 58 EXPECT_TRUE(is_less); |
| 59 } |
| 60 } |
| 61 } |
| 62 |
| 63 // Test with sequence that has every character. |
| 64 TEST(DivSufSortTest, AllChar) { |
| 65 const int kNumChar = 256; |
| 66 std::vector<unsigned char> all_char(kNumChar); |
| 67 std::iota(all_char.begin(), all_char.end(), 0); |
| 68 |
| 69 { |
| 70 courgette::PagedArray<divsuf::saidx_t> I; |
| 71 ASSERT_TRUE(I.Allocate(kNumChar + 1)); |
| 72 divsuf::divsufsort_include_empty(&all_char[0], I.begin(), kNumChar); |
| 73 EXPECT_EQ(kNumChar, I[0]); // Empty character. |
| 74 for (int i = 1; i <= kNumChar; ++i) |
| 75 EXPECT_EQ(i - 1, I[i]); |
| 76 } |
| 77 |
| 78 std::vector<unsigned char> all_char_reverse( |
| 79 all_char.rbegin(), all_char.rend()); |
| 80 { |
| 81 courgette::PagedArray<divsuf::saidx_t> I; |
| 82 ASSERT_TRUE(I.Allocate(kNumChar + 1)); |
| 83 divsuf::divsufsort_include_empty(&all_char_reverse[0], I.begin(), kNumChar); |
| 84 for (int i = 0; i <= kNumChar; ++i) |
| 85 EXPECT_EQ(kNumChar - i, I[i]); |
| 86 } |
| 87 } |
OLD | NEW |