File indexing completed on 2024-05-19 04:35:09
0001 /* 0002 Natural order sorting of strings which contains numbers. 0003 0004 SPDX-FileCopyrightText: 2007 Tobias Koenig <tokoe@kde.org> 0005 SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only 0006 based on the natural order code by Martin Pool <mbp sourcefrog net> 0007 */ 0008 0009 #include "qnatsort.h" 0010 0011 static int compare_right(const QString &leftStr, int left, const QString &rightStr, int right) 0012 { 0013 int bias = 0; 0014 0015 /** 0016 * The longest run of digits wins. That aside, the greatest 0017 * value wins, but we can't know that it will until we've scanned 0018 * both numbers to know that they have the same magnitude, so we 0019 * remember it in BIAS. 0020 */ 0021 for (;; left++, right++) { 0022 if (left >= leftStr.length() && right < rightStr.length()) { 0023 return -1; 0024 } else if (right >= rightStr.length() && left < leftStr.length()) { 0025 return +1; 0026 } else if (right >= rightStr.length() && left >= leftStr.length()) { 0027 return bias; 0028 } else if (!leftStr[left].isDigit() && !rightStr[right].isDigit()) { 0029 return bias; 0030 } else if (!leftStr[left].isDigit()) { 0031 return -1; 0032 } else if (!rightStr[right].isDigit()) { 0033 return +1; 0034 } else if (leftStr[left] < rightStr[right]) { 0035 if (!bias) { 0036 bias = -1; 0037 } 0038 } else if (leftStr[left] > rightStr[right]) { 0039 if (!bias) { 0040 bias = +1; 0041 } 0042 } else if (leftStr[left].isNull() && rightStr[right].isNull()) { 0043 return bias; 0044 } 0045 } 0046 0047 return 0; 0048 } 0049 0050 static int compare_left(const QString &leftStr, int left, const QString &rightStr, int right) 0051 { 0052 /** 0053 * Compare two left-aligned numbers: the first to have a 0054 * different value wins. 0055 */ 0056 for (;; left++, right++) { 0057 if (left >= leftStr.length() && right < rightStr.length()) { 0058 return -1; 0059 } else if (right >= rightStr.length() && left < leftStr.length()) { 0060 return +1; 0061 } else if (right >= rightStr.length() && left >= leftStr.length()) { 0062 return 0; 0063 } else if (!leftStr[left].isDigit() && !rightStr[right].isDigit()) { 0064 return 0; 0065 } else if (!leftStr[left].isDigit()) { 0066 return -1; 0067 } else if (!rightStr[right].isDigit()) { 0068 return +1; 0069 } else if (leftStr[left] < rightStr[right]) { 0070 return -1; 0071 } else if (leftStr[left] > rightStr[right]) { 0072 return +1; 0073 } 0074 } 0075 0076 return 0; 0077 } 0078 0079 static int natural_order_compare(const QString &leftStr, const QString &rightStr, bool fold_case) 0080 { 0081 if (leftStr.isEmpty() && rightStr.isEmpty()) { 0082 return 0; 0083 } 0084 0085 int ai, bi; 0086 QChar ca, cb; 0087 int fractional, result; 0088 0089 ai = bi = 0; 0090 const int aSize = leftStr.size(); 0091 const int bSize = rightStr.size(); 0092 0093 while (true) { 0094 ca = leftStr[ai]; 0095 cb = rightStr[bi]; 0096 0097 /* skip over leading spaces or zeros */ 0098 while (ca.isSpace() && ++ai < aSize) { 0099 ca = leftStr[ai]; 0100 } 0101 0102 while (cb.isSpace() && ++bi < bSize) { 0103 cb = rightStr[bi]; 0104 } 0105 0106 /* process run of digits */ 0107 if (ca.isDigit() && cb.isDigit()) { 0108 fractional = (ca == QLatin1Char('0') || cb == QLatin1Char('0')); 0109 0110 if (fractional) { 0111 if ((result = compare_left(leftStr, ai, rightStr, bi)) != 0) { 0112 return result; 0113 } 0114 } else { 0115 if ((result = compare_right(leftStr, ai, rightStr, bi)) != 0) { 0116 return result; 0117 } 0118 } 0119 } 0120 0121 if (ca.isNull() && cb.isNull()) { 0122 /* The strings compare the same. Perhaps the caller 0123 will want to call strcmp to break the tie. */ 0124 return 0; 0125 } 0126 0127 if (fold_case) { 0128 ca = ca.toUpper(); 0129 cb = cb.toUpper(); 0130 } 0131 0132 if (ca < cb) { 0133 return -1; 0134 } else if (ca > cb) { 0135 return +1; 0136 } 0137 0138 ++ai; 0139 ++bi; 0140 if (aSize == ai) { 0141 return aSize <= bSize ? -1 : 1; 0142 } 0143 if (bSize == bi) { 0144 return bSize <= aSize ? 1 : -1; 0145 } 0146 } 0147 } 0148 0149 bool caseSensitiveNaturalOrderLessThen(const QString &left, const QString &right) 0150 { 0151 return (natural_order_compare(left, right, false) < 0); 0152 } 0153 0154 bool caseInsensitiveNaturalOrderLessThen(const QString &left, const QString &right) 0155 { 0156 return (natural_order_compare(left, right, true) < 0); 0157 }