src/base/utils/compare.cpp

   1 /*
   2  * Bittorrent Client using Qt and libtorrent.
   3  * Copyright (C) 2021  Mike Tzou (Chocobo1)
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  18  *
  19  * In addition, as a special exception, the copyright holders give permission to
  20  * link this program with the OpenSSL project's "OpenSSL" library (or with
  21  * modified versions of it that use the same license as the "OpenSSL" library),
  22  * and distribute the linked executables. You must obey the GNU General Public
  23  * License in all respects for all of the code used other than "OpenSSL".  If you
  24  * modify file(s), you may extend this exception to your version of the file(s),
  25  * but you are not obligated to do so. If you do not wish to do so, delete this
  26  * exception statement from your version.
  27  */
  28
  29 #include "compare.h"
  30
  31 #include <QChar>
  32 #include <QString>
  33
  34 int Utils::Compare::naturalCompare(const QString &left, const QString &right, const Qt::CaseSensitivity caseSensitivity)
  35 {
  36     // Return value <0: `left` is smaller than `right`
  37     // Return value >0: `left` is greater than `right`
  38     // Return value =0: both strings are equal
  39
  40     int posL = 0;
  41     int posR = 0;
  42     while (true)
  43     {
  44         if ((posL == left.size()) || (posR == right.size()))
  45             return (left.size() - right.size());  // when a shorter string is another string's prefix, shorter string place before longer string
  46
  47         const QChar leftChar = (caseSensitivity == Qt::CaseSensitive) ? left[posL] : left[posL].toCaseFolded();
  48         const QChar rightChar = (caseSensitivity == Qt::CaseSensitive) ? right[posR] : right[posR].toCaseFolded();
  49         // Compare only non-digits.
  50         // Numbers should be compared as a whole
  51         // otherwise the string->int conversion can yield a wrong value
  52         if ((leftChar == rightChar) && !leftChar.isDigit())
  53         {
  54             // compare next character
  55             ++posL;
  56             ++posR;
  57         }
  58         else if (leftChar.isDigit() && rightChar.isDigit())
  59         {
  60             // Both are digits, compare the numbers
  61
  62             const auto numberView = [](const QStringView str, int &pos) -> QStringView
  63             {
  64                 const int start = pos;
  65                 while ((pos < str.size()) && str[pos].isDigit())
  66                     ++pos;
  67                 return str.mid(start, (pos - start));
  68             };
  69
  70             const QStringView numViewL = numberView(left, posL);
  71             const QStringView numViewR = numberView(right, posR);
  72
  73             if (numViewL.length() != numViewR.length())
  74                 return (numViewL.length() - numViewR.length());
  75
  76             // both string/view has the same length
  77             for (int i = 0; i < numViewL.length(); ++i)
  78             {
  79                 const QChar numL = numViewL[i];
  80                 const QChar numR = numViewR[i];
  81
  82                 if (numL != numR)
  83                     return (numL.unicode() - numR.unicode());
  84             }
  85
  86             // String + digits do match and we haven't hit the end of both strings
  87             // then continue to consume the remainings
  88         }
  89         else
  90         {
  91             return QString::localeAwareCompare(leftChar, rightChar);
  92         }
  93     }
  94 }