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
TEST(Distance,TestDistances)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
TEST(Distance,TestCutoff)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
100