tools/qdoc3/editdistance.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the tools applications of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** No Commercial Usage
  11 ** This file contains pre-release code and may not be distributed.
  12 ** You may use this file in accordance with the terms and conditions
  13 ** contained in the Technology Preview License Agreement accompanying
  14 ** this package.
  15 **
  16 ** GNU Lesser General Public License Usage
  17 ** Alternatively, this file may be used under the terms of the GNU Lesser
  18 ** General Public License version 2.1 as published by the Free Software
  19 ** Foundation and appearing in the file LICENSE.LGPL included in the
  20 ** packaging of this file.  Please review the following information to
  21 ** ensure the GNU Lesser General Public License version 2.1 requirements
  22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  23 **
  24 ** In addition, as a special exception, Nokia gives you certain additional
  25 ** rights.  These rights are described in the Nokia Qt LGPL Exception
  26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  27 **
  28 ** If you have questions regarding the use of this file, please contact
  29 ** Nokia at qt-info@nokia.com.
  30 **
  31 **
  32 **
  33 **
  34 **
  35 **
  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