File indexing completed on 2024-05-12 17:22:02
0001 /* 0002 SPDX-FileCopyrightText: 2002 Shie Erlich <erlich@users.sourceforge.net> 0003 SPDX-FileCopyrightText: 2002 Rafi Yanai <yanai@users.sourceforge.net> 0004 SPDX-FileCopyrightText: 2004-2022 Krusader Krew <https://krusader.org> 0005 0006 SPDX-License-Identifier: GPL-2.0-or-later 0007 */ 0008 0009 #include "krsort.h" 0010 0011 #include <utility> 0012 0013 #include "../FileSystem/fileitem.h" 0014 #include "krview.h" 0015 0016 namespace KrSort 0017 { 0018 0019 void SortProps::init(FileItem *fileitem, int col, const KrViewProperties *props, bool isDummy, bool asc, int origNdx, QVariant customData) 0020 { 0021 _col = col; 0022 _prop = props; 0023 _isdummy = isDummy; 0024 _ascending = asc; 0025 _fileItem = fileitem; 0026 _index = origNdx; 0027 _name = fileitem->getName(); 0028 _customData = std::move(customData); 0029 0030 if (_prop->sortOptions & KrViewProperties::IgnoreCase) 0031 _name = _name.toLower(); 0032 0033 switch (_col) { 0034 case KrViewProperties::Ext: { 0035 if (fileitem->isDir()) { 0036 _ext = ""; 0037 } else { 0038 // check if the file has an extension 0039 const QString &fileitemName = fileitem->getName(); 0040 int loc = fileitemName.lastIndexOf('.'); 0041 if (loc > 0) { // avoid mishandling of .bashrc and friend 0042 // check if it has one of the predefined 'atomic extensions' 0043 for (const auto &atomicExtension : props->atomicExtensions) { 0044 if (fileitemName.endsWith(atomicExtension) && fileitemName != atomicExtension) { 0045 loc = fileitemName.length() - atomicExtension.length(); 0046 break; 0047 } 0048 } 0049 _ext = _name.mid(loc); 0050 } else 0051 _ext = ""; 0052 } 0053 break; 0054 } 0055 case KrViewProperties::Type: 0056 _data = isDummy ? "" : KrView::mimeTypeText(fileitem); 0057 break; 0058 case KrViewProperties::Permissions: 0059 _data = isDummy ? "" : KrView::permissionsText(properties(), fileitem); 0060 break; 0061 case KrViewProperties::KrPermissions: 0062 _data = isDummy ? "" : KrView::krPermissionText(fileitem); 0063 break; 0064 case KrViewProperties::Owner: 0065 _data = isDummy ? "" : fileitem->getOwner(); 0066 break; 0067 case KrViewProperties::Group: 0068 _data = isDummy ? "" : fileitem->getGroup(); 0069 break; 0070 default: 0071 break; 0072 } 0073 } 0074 0075 // compares numbers within two strings 0076 int compareNumbers(QString &aS1, int &aPos1, QString &aS2, int &aPos2) 0077 { 0078 int res = 0; 0079 int start1 = aPos1; 0080 int start2 = aPos2; 0081 while (aPos1 < aS1.length() && aS1.at(aPos1).isDigit()) 0082 aPos1++; 0083 while (aPos2 < aS2.length() && aS2.at(aPos2).isDigit()) 0084 aPos2++; 0085 // the left-most difference determines what's bigger 0086 int i1 = aPos1 - 1; 0087 int i2 = aPos2 - 1; 0088 for (; i1 >= start1 || i2 >= start2; i1--, i2--) { 0089 int c1 = 0; 0090 int c2 = 0; 0091 if (i1 >= start1) 0092 c1 = aS1.at(i1).digitValue(); 0093 if (i2 >= start2) 0094 c2 = aS2.at(i2).digitValue(); 0095 if (c1 < c2) 0096 res = -1; 0097 else if (c1 > c2) 0098 res = 1; 0099 } 0100 return res; 0101 } 0102 0103 bool compareTextsAlphabetical(QString &aS1, QString &aS2, const KrViewProperties *_viewProperties, bool aNumbers) 0104 { 0105 int lPositionS1 = 0; 0106 int lPositionS2 = 0; 0107 // sometimes, localeAwareCompare is not case sensitive. in that case, we need to fallback to a simple string compare (KDE bug #40131) 0108 bool lUseLocaleAware = ((_viewProperties->sortOptions & KrViewProperties::IgnoreCase) || _viewProperties->localeAwareCompareIsCaseSensitive) 0109 && (_viewProperties->sortOptions & KrViewProperties::LocaleAwareSort); 0110 int j = 0; 0111 QChar lchar1; 0112 QChar lchar2; 0113 while (true) { 0114 lchar1 = aS1[lPositionS1]; 0115 lchar2 = aS2[lPositionS2]; 0116 // detect numbers 0117 if (aNumbers && lchar1.isDigit() && lchar2.isDigit()) { 0118 int j = compareNumbers(aS1, lPositionS1, aS2, lPositionS2); 0119 if (j != 0) 0120 return j < 0; 0121 } else if (lUseLocaleAware 0122 && ((lchar1 >= 128 && ((lchar2 >= 'A' && lchar2 <= 'Z') || (lchar2 >= 'a' && lchar2 <= 'z') || lchar2 >= 128)) 0123 || (lchar2 >= 128 && ((lchar1 >= 'A' && lchar1 <= 'Z') || (lchar1 >= 'a' && lchar1 <= 'z') || lchar1 >= 128)))) { 0124 // use localeAwareCompare when a unicode character is encountered 0125 j = QString::localeAwareCompare(lchar1, lchar2); 0126 if (j != 0) 0127 return j < 0; 0128 lPositionS1++; 0129 lPositionS2++; 0130 } else { 0131 // if characters are latin or localeAwareCompare is not case sensitive then use simple characters compare is enough 0132 if (lchar1 < lchar2) 0133 return true; 0134 if (lchar1 > lchar2) 0135 return false; 0136 lPositionS1++; 0137 lPositionS2++; 0138 } 0139 // at this point strings are equal, check if ends of strings are reached 0140 if (lPositionS1 == aS1.length() && lPositionS2 == aS2.length()) 0141 return false; 0142 if (lPositionS1 == aS1.length() && lPositionS2 < aS2.length()) 0143 return true; 0144 if (lPositionS1 < aS1.length() && lPositionS2 == aS2.length()) 0145 return false; 0146 } 0147 } 0148 0149 bool compareTextsCharacterCode(QString &aS1, QString &aS2, const KrViewProperties *_viewProperties, bool aNumbers) 0150 { 0151 Q_UNUSED(_viewProperties); 0152 0153 int lPositionS1 = 0; 0154 int lPositionS2 = 0; 0155 while (true) { 0156 // detect numbers 0157 if (aNumbers && aS1[lPositionS1].isDigit() && aS2[lPositionS2].isDigit()) { 0158 int j = compareNumbers(aS1, lPositionS1, aS2, lPositionS2); 0159 if (j != 0) 0160 return j < 0; 0161 } else { 0162 if (aS1[lPositionS1] < aS2[lPositionS2]) 0163 return true; 0164 if (aS1[lPositionS1] > aS2[lPositionS2]) 0165 return false; 0166 lPositionS1++; 0167 lPositionS2++; 0168 } 0169 // at this point strings are equal, check if ends of strings are reached 0170 if (lPositionS1 == aS1.length() && lPositionS2 == aS2.length()) 0171 return false; 0172 if (lPositionS1 == aS1.length() && lPositionS2 < aS2.length()) 0173 return true; 0174 if (lPositionS1 < aS1.length() && lPositionS2 == aS2.length()) 0175 return false; 0176 } 0177 } 0178 0179 bool compareTextsKrusader(const QString &aS1, const QString &aS2, const KrViewProperties *_viewProperties) 0180 { 0181 // sometimes, localeAwareCompare is not case sensitive. in that case, we need to fallback to a simple string compare (KDE bug #40131) 0182 if (((_viewProperties->sortOptions & KrViewProperties::IgnoreCase) || _viewProperties->localeAwareCompareIsCaseSensitive) 0183 && (_viewProperties->sortOptions & KrViewProperties::LocaleAwareSort)) 0184 return QString::localeAwareCompare(aS1, aS2) < 0; 0185 else 0186 // if localeAwareCompare is not case sensitive then use simple compare is enough 0187 return QString::compare(aS1, aS2) < 0; 0188 } 0189 0190 bool compareTexts(QString aS1, QString aS2, const KrViewProperties *_viewProperties, bool asc, bool isName) 0191 { 0192 // check empty strings 0193 if (aS1.length() == 0 && aS2.length() == 0) { 0194 return false; 0195 } else if (aS1.length() == 0) { 0196 return true; 0197 } else if (aS2.length() == 0) { 0198 return false; 0199 } 0200 0201 if (isName) { 0202 if (aS1 == "..") { 0203 return !asc; 0204 } else { 0205 if (aS2 == "..") 0206 return asc; 0207 } 0208 } 0209 0210 switch (_viewProperties->sortMethod) { 0211 case KrViewProperties::Alphabetical: 0212 return compareTextsAlphabetical(aS1, aS2, _viewProperties, false); 0213 case KrViewProperties::AlphabeticalNumbers: 0214 return compareTextsAlphabetical(aS1, aS2, _viewProperties, true); 0215 case KrViewProperties::CharacterCode: 0216 return compareTextsCharacterCode(aS1, aS2, _viewProperties, false); 0217 case KrViewProperties::CharacterCodeNumbers: 0218 return compareTextsCharacterCode(aS1, aS2, _viewProperties, true); 0219 case KrViewProperties::Krusader: 0220 default: 0221 return compareTextsKrusader(aS1, aS2, _viewProperties); 0222 } 0223 } 0224 0225 bool itemLessThan(SortProps *sp, SortProps *sp2) 0226 { 0227 FileItem *file1 = sp->fileitem(); 0228 FileItem *file2 = sp2->fileitem(); 0229 bool isdir1 = file1->isDir(); 0230 bool isdir2 = file2->isDir(); 0231 bool dirsFirst = sp->properties()->sortOptions & KrViewProperties::DirsFirst; 0232 bool alwaysSortDirsByName = sp->properties()->sortOptions & KrViewProperties::AlwaysSortDirsByName && dirsFirst && isdir1 && isdir2; 0233 0234 if (dirsFirst) { 0235 if (isdir1 && !isdir2) 0236 return sp->isAscending(); 0237 if (isdir2 && !isdir1) 0238 return !sp->isAscending(); 0239 } 0240 0241 if (sp->isDummy()) 0242 return sp->isAscending(); 0243 if (sp2->isDummy()) 0244 return !sp->isAscending(); 0245 0246 int column = sp->column(); 0247 0248 if (dirsFirst && isdir1 && isdir2 && alwaysSortDirsByName) { 0249 alwaysSortDirsByName = !sp->isAscending(); 0250 column = KrViewProperties::Name; 0251 } 0252 0253 switch (column) { 0254 case KrViewProperties::Name: 0255 return compareTexts(sp->name(), sp2->name(), sp->properties(), sp->isAscending(), true) ^ alwaysSortDirsByName; 0256 case KrViewProperties::Ext: 0257 if (sp->extension() == sp2->extension()) 0258 return compareTexts(sp->name(), sp2->name(), sp->properties(), sp->isAscending(), true); 0259 return compareTexts(sp->extension(), sp2->extension(), sp->properties(), sp->isAscending(), true); 0260 case KrViewProperties::Size: 0261 if (file1->getSize() == file2->getSize()) 0262 return compareTexts(sp->name(), sp2->name(), sp->properties(), sp->isAscending(), true); 0263 return file1->getSize() < file2->getSize(); 0264 case KrViewProperties::Modified: 0265 return compareTime(file1->getModificationTime(), file2->getModificationTime(), sp, sp2); 0266 case KrViewProperties::Changed: 0267 return compareTime(file1->getChangeTime(), file2->getChangeTime(), sp, sp2); 0268 case KrViewProperties::Accessed: 0269 return compareTime(file1->getAccessTime(), file2->getAccessTime(), sp, sp2); 0270 case KrViewProperties::Type: 0271 case KrViewProperties::Permissions: 0272 case KrViewProperties::KrPermissions: 0273 case KrViewProperties::Owner: 0274 case KrViewProperties::Group: 0275 if (sp->data() == sp2->data()) 0276 return compareTexts(sp->name(), sp2->name(), sp->properties(), sp->isAscending(), true); 0277 return compareTexts(sp->data(), sp2->data(), sp->properties(), sp->isAscending(), true); 0278 } 0279 return sp->name() < sp2->name(); 0280 } 0281 0282 bool compareTime(time_t time1, time_t time2, SortProps *sp, SortProps *sp2) 0283 { 0284 return time1 != time2 ? time1 < time2 : compareTexts(sp->name(), sp2->name(), sp->properties(), sp->isAscending(), true); 0285 } 0286 0287 bool itemGreaterThan(SortProps *sp, SortProps *sp2) 0288 { 0289 return !itemLessThan(sp, sp2); 0290 } 0291 0292 Sorter::Sorter(int reserveItems, const KrViewProperties *viewProperties, LessThanFunc lessThanFunc, LessThanFunc greaterThanFunc) 0293 : _viewProperties(viewProperties) 0294 , _lessThanFunc(lessThanFunc) 0295 , _greaterThanFunc(greaterThanFunc) 0296 { 0297 _items.reserve(reserveItems); 0298 _itemStore.reserve(reserveItems); 0299 } 0300 0301 void Sorter::addItem(FileItem *fileitem, bool isDummy, int idx, QVariant customData) 0302 { 0303 _itemStore << SortProps(fileitem, _viewProperties->sortColumn, _viewProperties, isDummy, !descending(), idx, std::move(customData)); 0304 _items << &_itemStore.last(); 0305 } 0306 0307 void Sorter::sort() 0308 { 0309 std::stable_sort(_items.begin(), _items.end(), descending() ? _greaterThanFunc : _lessThanFunc); 0310 } 0311 0312 int Sorter::insertIndex(FileItem *fileitem, bool isDummy, QVariant customData) 0313 { 0314 SortProps props(fileitem, _viewProperties->sortColumn, _viewProperties, isDummy, !descending(), -1, std::move(customData)); 0315 const QVector<SortProps *>::iterator it = std::lower_bound(_items.begin(), _items.end(), &props, descending() ? _greaterThanFunc : _lessThanFunc); 0316 0317 if (it != _items.end()) 0318 return _items.indexOf((*it)); 0319 else 0320 return _items.count(); 0321 } 0322 0323 bool Sorter::descending() const 0324 { 0325 return _viewProperties->sortOptions & KrViewProperties::Descending; 0326 } 0327 0328 } // namespace KrSort