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
48QT_BEGIN_NAMESPACE
49
50int 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
82QString 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
111QT_END_NAMESPACE
112

Warning: That file was not part of the compilation database. It may have many parsing errors.