| // Copyright 2023 The Chromium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "base/strings/levenshtein_distance.h" |
| |
| #include <string> |
| |
| #include "testing/gtest/include/gtest/gtest.h" |
| |
| namespace gurl_base { |
| |
| namespace { |
| |
| TEST(LevenshteinDistanceTest, WithoutMaxDistance) { |
| EXPECT_EQ(0u, LevenshteinDistance("banana", "banana")); |
| |
| EXPECT_EQ(2u, LevenshteinDistance("ab", "ba")); |
| EXPECT_EQ(2u, LevenshteinDistance("ba", "ab")); |
| |
| EXPECT_EQ(2u, LevenshteinDistance("ananas", "banana")); |
| EXPECT_EQ(2u, LevenshteinDistance("banana", "ananas")); |
| |
| EXPECT_EQ(2u, LevenshteinDistance("unclear", "nuclear")); |
| EXPECT_EQ(2u, LevenshteinDistance("nuclear", "unclear")); |
| |
| EXPECT_EQ(3u, LevenshteinDistance("chrome", "chromium")); |
| EXPECT_EQ(3u, LevenshteinDistance("chromium", "chrome")); |
| |
| EXPECT_EQ(4u, LevenshteinDistance("", "abcd")); |
| EXPECT_EQ(4u, LevenshteinDistance("abcd", "")); |
| |
| // `std::u16string_view` version. |
| EXPECT_EQ(4u, LevenshteinDistance(u"xxx", u"xxxxxxx")); |
| EXPECT_EQ(4u, LevenshteinDistance(u"xxxxxxx", u"xxx")); |
| |
| EXPECT_EQ(7u, LevenshteinDistance(u"yyy", u"xxxxxxx")); |
| EXPECT_EQ(7u, LevenshteinDistance(u"xxxxxxx", u"yyy")); |
| } |
| |
| TEST(LevenshteinDistanceTest, WithMaxDistance) { |
| EXPECT_EQ(LevenshteinDistance("aa", "aa", 0), 0u); |
| |
| EXPECT_EQ(LevenshteinDistance("a", "aa", 1), 1u); |
| EXPECT_EQ(LevenshteinDistance("aa", "a", 1), 1u); |
| |
| // If k is less than `LevenshteinDistance()`, the function should return k+1. |
| EXPECT_EQ(LevenshteinDistance("", "12", 1), 2u); |
| EXPECT_EQ(LevenshteinDistance("12", "", 1), 2u); |
| |
| EXPECT_EQ(LevenshteinDistance("street", "str.", 1), 2u); |
| EXPECT_EQ(LevenshteinDistance("str.", "street", 1), 2u); |
| |
| EXPECT_EQ(LevenshteinDistance("asdf", "fdsa", 2), 3u); |
| EXPECT_EQ(LevenshteinDistance("fdsa", "asdf", 2), 3u); |
| |
| EXPECT_EQ(LevenshteinDistance(std::u16string(100, 'a'), |
| std::u16string(200, 'a'), 50), |
| 51u); |
| EXPECT_EQ(LevenshteinDistance(std::u16string(200, 'a'), |
| std::u16string(100, 'a'), 50), |
| 51u); |
| } |
| |
| } // namespace |
| |
| } // namespace base |