1 // Copyright 2023 gRPC 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 // http://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 "test/core/util/osa_distance.h"
16
17 #include <stdint.h>
18
19 #include <algorithm>
20 #include <limits>
21 #include <utility>
22 #include <vector>
23
24 namespace grpc_core {
25
OsaDistance(absl::string_view s1,absl::string_view s2)26 size_t OsaDistance(absl::string_view s1, absl::string_view s2) {
27 if (s1.size() > s2.size()) std::swap(s1, s2);
28 if (s1.empty()) return static_cast<uint8_t>(s2.size());
29
30 const auto width = s1.size() + 1;
31 const auto height = s2.size() + 1;
32 std::vector<size_t> matrix(width * height,
33 std::numeric_limits<size_t>::max());
34 #define MATRIX_CELL(x, y) matrix[(y) * width + (x)]
35
36 MATRIX_CELL(0, 0) = 0;
37 for (size_t i = 1; i <= s1.size(); ++i) {
38 MATRIX_CELL(i, 0) = i;
39 }
40 for (size_t j = 1; j <= s2.size(); ++j) {
41 MATRIX_CELL(0, j) = j;
42 }
43 for (size_t i = 1; i <= s1.size(); ++i) {
44 for (size_t j = 1; j <= s2.size(); ++j) {
45 const size_t cost = s1[i - 1] == s2[j - 1] ? 0 : 1;
46 MATRIX_CELL(i, j) = std::min({
47 MATRIX_CELL(i - 1, j) + 1, // deletion
48 MATRIX_CELL(i, j - 1) + 1, // insertion
49 MATRIX_CELL(i - 1, j - 1) + cost // substitution
50 });
51 if (i > 1 && j > 1 && s1[i - 1] == s2[j - 2] && s1[i - 2] == s2[j - 1]) {
52 MATRIX_CELL(i, j) = std::min(
53 MATRIX_CELL(i, j), MATRIX_CELL(i - 2, j - 2) + 1); // transposition
54 }
55 }
56 }
57 return MATRIX_CELL(s1.size(), s2.size());
58 }
59
60 } // namespace grpc_core
61