Warning: That file was not part of the compilation database. It may have many parsing errors.
1 | /**************************************************************************** |
---|---|
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
5 | ** |
6 | ** This file is part of the tools applications of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 2.1 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
36 | ** |
37 | ** |
38 | ** $QT_END_LICENSE$ |
39 | ** |
40 | ****************************************************************************/ |
41 | |
42 | /* |
43 | editdistance.cpp |
44 | */ |
45 | |
46 | #include "editdistance.h" |
47 | |
48 | QT_BEGIN_NAMESPACE |
49 | |
50 | int editDistance( const QString& s, const QString& t ) |
51 | { |
52 | #define D( i, j ) d[(i) * n + (j)] |
53 | int i; |
54 | int j; |
55 | int m = s.length() + 1; |
56 | int n = t.length() + 1; |
57 | int *d = new int[m * n]; |
58 | int result; |
59 | |
60 | for ( i = 0; i < m; i++ ) |
61 | D( i, 0 ) = i; |
62 | for ( j = 0; j < n; j++ ) |
63 | D( 0, j ) = j; |
64 | for ( i = 1; i < m; i++ ) { |
65 | for ( j = 1; j < n; j++ ) { |
66 | if ( s[i - 1] == t[j - 1] ) { |
67 | D( i, j ) = D( i - 1, j - 1 ); |
68 | } else { |
69 | int x = D( i - 1, j ); |
70 | int y = D( i - 1, j - 1 ); |
71 | int z = D( i, j - 1 ); |
72 | D( i, j ) = 1 + qMin( qMin(x, y), z ); |
73 | } |
74 | } |
75 | } |
76 | result = D( m - 1, n - 1 ); |
77 | delete[] d; |
78 | return result; |
79 | #undef D |
80 | } |
81 | |
82 | QString nearestName( const QString& actual, const QSet<QString>& candidates ) |
83 | { |
84 | int deltaBest = 10000; |
85 | int numBest = 0; |
86 | QString best; |
87 | |
88 | QSet<QString>::ConstIterator c = candidates.begin(); |
89 | while ( c != candidates.end() ) { |
90 | if ( (*c)[0] == actual[0] ) { |
91 | int delta = editDistance( actual, *c ); |
92 | if ( delta < deltaBest ) { |
93 | deltaBest = delta; |
94 | numBest = 1; |
95 | best = *c; |
96 | } else if ( delta == deltaBest ) { |
97 | numBest++; |
98 | } |
99 | } |
100 | ++c; |
101 | } |
102 | |
103 | if ( numBest == 1 && deltaBest <= 2 && |
104 | actual.length() + best.length() >= 5 ) { |
105 | return best; |
106 | } else { |
107 | return ""; |
108 | } |
109 | } |
110 | |
111 | QT_END_NAMESPACE |
112 |
Warning: That file was not part of the compilation database. It may have many parsing errors.