1 // Copyright 2023 The Chromium Authors
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 "base/strings/levenshtein_distance.h"
6
7 #include <string>
8
9 #include "testing/gtest/include/gtest/gtest.h"
10
11 namespace base {
12
13 namespace {
14
TEST(LevenshteinDistanceTest,WithoutMaxDistance)15 TEST(LevenshteinDistanceTest, WithoutMaxDistance) {
16 EXPECT_EQ(0u, LevenshteinDistance("banana", "banana"));
17
18 EXPECT_EQ(2u, LevenshteinDistance("ab", "ba"));
19 EXPECT_EQ(2u, LevenshteinDistance("ba", "ab"));
20
21 EXPECT_EQ(2u, LevenshteinDistance("ananas", "banana"));
22 EXPECT_EQ(2u, LevenshteinDistance("banana", "ananas"));
23
24 EXPECT_EQ(2u, LevenshteinDistance("unclear", "nuclear"));
25 EXPECT_EQ(2u, LevenshteinDistance("nuclear", "unclear"));
26
27 EXPECT_EQ(3u, LevenshteinDistance("chrome", "chromium"));
28 EXPECT_EQ(3u, LevenshteinDistance("chromium", "chrome"));
29
30 EXPECT_EQ(4u, LevenshteinDistance("", "abcd"));
31 EXPECT_EQ(4u, LevenshteinDistance("abcd", ""));
32
33 // `std::u16string_view` version.
34 EXPECT_EQ(4u, LevenshteinDistance(u"xxx", u"xxxxxxx"));
35 EXPECT_EQ(4u, LevenshteinDistance(u"xxxxxxx", u"xxx"));
36
37 EXPECT_EQ(7u, LevenshteinDistance(u"yyy", u"xxxxxxx"));
38 EXPECT_EQ(7u, LevenshteinDistance(u"xxxxxxx", u"yyy"));
39 }
40
TEST(LevenshteinDistanceTest,WithMaxDistance)41 TEST(LevenshteinDistanceTest, WithMaxDistance) {
42 EXPECT_EQ(LevenshteinDistance("aa", "aa", 0), 0u);
43
44 EXPECT_EQ(LevenshteinDistance("a", "aa", 1), 1u);
45 EXPECT_EQ(LevenshteinDistance("aa", "a", 1), 1u);
46
47 // If k is less than `LevenshteinDistance()`, the function should return k+1.
48 EXPECT_EQ(LevenshteinDistance("", "12", 1), 2u);
49 EXPECT_EQ(LevenshteinDistance("12", "", 1), 2u);
50
51 EXPECT_EQ(LevenshteinDistance("street", "str.", 1), 2u);
52 EXPECT_EQ(LevenshteinDistance("str.", "street", 1), 2u);
53
54 EXPECT_EQ(LevenshteinDistance("asdf", "fdsa", 2), 3u);
55 EXPECT_EQ(LevenshteinDistance("fdsa", "asdf", 2), 3u);
56
57 EXPECT_EQ(LevenshteinDistance(std::u16string(100, 'a'),
58 std::u16string(200, 'a'), 50),
59 51u);
60 EXPECT_EQ(LevenshteinDistance(std::u16string(200, 'a'),
61 std::u16string(100, 'a'), 50),
62 51u);
63 }
64
65 } // namespace
66
67 } // namespace base
68