damerau_levenshtein_distance_test.cc (5023B)
1 // Copyright 2022 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "absl/strings/internal/damerau_levenshtein_distance.h" 16 17 #include <cstdint> 18 19 #include "gmock/gmock.h" 20 #include "gtest/gtest.h" 21 22 namespace { 23 24 using absl::strings_internal::CappedDamerauLevenshteinDistance; 25 26 TEST(Distance, TestDistances) { 27 EXPECT_THAT(CappedDamerauLevenshteinDistance("ab", "ab", 6), uint8_t{0}); 28 EXPECT_THAT(CappedDamerauLevenshteinDistance("a", "b", 6), uint8_t{1}); 29 EXPECT_THAT(CappedDamerauLevenshteinDistance("ca", "abc", 6), uint8_t{3}); 30 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcd", "ad", 6), uint8_t{2}); 31 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcd", "cadb", 6), uint8_t{4}); 32 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcd", "bdac", 6), uint8_t{4}); 33 EXPECT_THAT(CappedDamerauLevenshteinDistance("ab", "ab", 0), uint8_t{0}); 34 EXPECT_THAT(CappedDamerauLevenshteinDistance("", "", 0), uint8_t{0}); 35 // combinations for 3-character strings: 36 // 1, 2, 3 removals, insertions or replacements and transpositions 37 EXPECT_THAT(CappedDamerauLevenshteinDistance("abc", "abc", 6), uint8_t{0}); 38 for (auto res : 39 {"", "ca", "efg", "ea", "ce", "ceb", "eca", "cae", "cea", "bea"}) { 40 EXPECT_THAT(CappedDamerauLevenshteinDistance("abc", res, 6), uint8_t{3}); 41 EXPECT_THAT(CappedDamerauLevenshteinDistance(res, "abc", 6), uint8_t{3}); 42 } 43 for (auto res : 44 {"a", "b", "c", "ba", "cb", "bca", "cab", "cba", "ace", 45 "efc", "ebf", "aef", "ae", "be", "eb", "ec", "ecb", "bec", 46 "bce", "cbe", "ace", "eac", "aeb", "bae", "eab", "eba"}) { 47 EXPECT_THAT(CappedDamerauLevenshteinDistance("abc", res, 6), uint8_t{2}); 48 EXPECT_THAT(CappedDamerauLevenshteinDistance(res, "abc", 6), uint8_t{2}); 49 } 50 for (auto res : {"ab", "ac", "bc", "acb", "bac", "ebc", "aec", "abe"}) { 51 EXPECT_THAT(CappedDamerauLevenshteinDistance("abc", res, 6), uint8_t{1}); 52 EXPECT_THAT(CappedDamerauLevenshteinDistance(res, "abc", 6), uint8_t{1}); 53 } 54 } 55 56 TEST(Distance, TestCutoff) { 57 // Returning cutoff + 1 if the value is larger than cutoff or string longer 58 // than MAX_SIZE. 59 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcd", "a", 3), uint8_t{3}); 60 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcd", "a", 2), uint8_t{3}); 61 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcd", "a", 1), uint8_t{2}); 62 EXPECT_THAT(CappedDamerauLevenshteinDistance("abcdefg", "a", 2), uint8_t{3}); 63 EXPECT_THAT(CappedDamerauLevenshteinDistance("a", "abcde", 2), uint8_t{3}); 64 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(102, 'a'), 65 std::string(102, 'a'), 105), 66 uint8_t{101}); 67 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(100, 'a'), 68 std::string(100, 'a'), 100), 69 uint8_t{0}); 70 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(100, 'a'), 71 std::string(100, 'b'), 100), 72 uint8_t{100}); 73 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(100, 'a'), 74 std::string(99, 'a'), 2), 75 uint8_t{1}); 76 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(100, 'a'), 77 std::string(101, 'a'), 2), 78 uint8_t{3}); 79 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(100, 'a'), 80 std::string(101, 'a'), 2), 81 uint8_t{3}); 82 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(UINT8_MAX + 1, 'a'), 83 std::string(UINT8_MAX + 1, 'b'), 84 UINT8_MAX), 85 uint8_t{101}); 86 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(UINT8_MAX - 1, 'a'), 87 std::string(UINT8_MAX - 1, 'b'), 88 UINT8_MAX), 89 uint8_t{101}); 90 EXPECT_THAT( 91 CappedDamerauLevenshteinDistance(std::string(UINT8_MAX, 'a'), 92 std::string(UINT8_MAX, 'b'), UINT8_MAX), 93 uint8_t{101}); 94 EXPECT_THAT(CappedDamerauLevenshteinDistance(std::string(UINT8_MAX - 1, 'a'), 95 std::string(UINT8_MAX - 1, 'a'), 96 UINT8_MAX), 97 uint8_t{101}); 98 } 99 } // namespace