1// Copyright (C) 2021 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
3
4#include "editdistance.h"
5
6QT_BEGIN_NAMESPACE
7
8int editDistance(const QString &s, const QString &t)
9{
10#define D(i, j) d[(i)*n + (j)]
11 int i;
12 int j;
13 qsizetype m = s.size() + 1;
14 qsizetype n = t.size() + 1;
15 int *d = new int[m * n];
16 int result;
17
18 for (i = 0; i < m; ++i)
19 D(i, 0) = i;
20 for (j = 0; j < n; ++j)
21 D(0, j) = j;
22 for (i = 1; i < m; ++i) {
23 for (j = 1; j < n; ++j) {
24 if (s[i - 1] == t[j - 1]) {
25 D(i, j) = D(i - 1, j - 1);
26 } else {
27 int x = D(i - 1, j);
28 int y = D(i - 1, j - 1);
29 int z = D(i, j - 1);
30 D(i, j) = 1 + qMin(a: qMin(a: x, b: y), b: z);
31 }
32 }
33 }
34 result = D(m - 1, n - 1);
35 delete[] d;
36 return result;
37#undef D
38}
39
40QString nearestName(const QString &actual, const QSet<QString> &candidates)
41{
42 if (actual.isEmpty())
43 return QString();
44
45 int deltaBest = 10000;
46 int numBest = 0;
47 QString best;
48
49 for (const auto &candidate : candidates) {
50 if (candidate[0] == actual[0]) {
51 int delta = editDistance(s: actual, t: candidate);
52 if (delta < deltaBest) {
53 deltaBest = delta;
54 numBest = 1;
55 best = candidate;
56 } else if (delta == deltaBest) {
57 ++numBest;
58 }
59 }
60 }
61
62 if (numBest == 1 && deltaBest <= 2 && actual.size() + best.size() >= 5)
63 return best;
64
65 return QString();
66}
67
68QT_END_NAMESPACE
69

source code of qttools/src/qdoc/qdoc/src/qdoc/editdistance.cpp