154408 2007-12-21 02:24:20 +0000 collection sort should not always be lexicographic 2008-10-26 11:21:39 +0000 1 1 2 Applications amarok general 1.4.7 Debian testing Linux RESOLVED FIXED NOR wishlist --- 0 nicholas amarok-bugs-null 0 oldest_to_newest 565278 0 nicholas 2007-12-21 02:24:20 +0000 Version: 1.4.7 (using KDE KDE 3.5.8) Installed from: Debian testing/unstable Packages OS: Linux For numbers in strings, could the sorting switch to numerical ordering? In my collection, I have all sorts of incongruities, like - Mahler, Gustav | ... | Symphony 1 | Symphony 10 | Symphony 2 |-... To fix this, we might have something like (pseudocode) operator customSort (QString a, Qstring b) { int aIndex = find [0-9] in a; int bIndex; if (aIndex != npos && (bIndex = find [0-9] in b) != npos && aIndex != bIndex) return a < b; //lexicographically //tokenise at the digit boundaries: //a[initial] is a up to aIndex, a[number] is the number contained in the string, and a[final] is the end //eg. if a = "test123test123", then a[initial] = "test", a[number] = 123, and a[final] = "test123" if (a[initial] != b[inital]) return a < b; //lexicographically if (a[number] != b[number]) return a[number] < b[number]; //numerically return customSort(a[final], b[final]); //recurse on the tails } This quite simple procedure would make things much more intuitive for me, and it is restrictive enough that it should not annoy people: the numerical part never kicks in until we know all the letters before match. 567058 1 nicholas 2007-12-29 22:20:36 +0000 This works now with new versions of collectionbrowser/CollectionSortFilterProxyModel.h and collectionbrowser/CollectionSortFilterProxyModel.cpp. (Against SVN 29/12/07) collectionbrowser/CollectionSortFilterProxyModel.h: --------------------------------------------------- class CollectionSortFilterProxyModel : public QSortFilterProxyModel { public: CollectionSortFilterProxyModel( QObject * parent = 0 ); virtual ~CollectionSortFilterProxyModel(); bool hasChildren(const QModelIndex &parent) const; protected: virtual bool lessThan( const QModelIndex &left, const QModelIndex &right ) const; virtual bool lessThanString( const QString a, const QString b ) const; }; collectionbrowser/CollectionSortFilterProxyModel.cpp: ----------------------------------------------------- bool CollectionSortFilterProxyModel::lessThan( const QModelIndex &left, const QModelIndex &right ) const { CollectionTreeItem *leftItem = static_cast<CollectionTreeItem*>( left.internalPointer() ); CollectionTreeItem *rightItem = static_cast<CollectionTreeItem*>( right.internalPointer() ); //Here we catch the bottom 'track' level if( leftItem->level() == rightItem->level() ) { const Meta::TrackPtr leftTrack = Meta::TrackPtr::dynamicCast( leftItem->data() ); const Meta::TrackPtr rightTrack = Meta::TrackPtr::dynamicCast( rightItem->data() ); if( !leftTrack.isNull() && !rightTrack.isNull() ) return leftTrack->trackNumber() < rightTrack->trackNumber(); } //This should catch everything else QVariant leftData = left.data(); QVariant rightData = right.data(); if( leftData.canConvert( QVariant::String ) && rightData.canConvert( QVariant::String ) ) { return lessThanString( leftData.toString().toLower(), rightData.toString().toLower() ); } warning() << "failed: an unexpected comparison was made"; //Just in case return QSortFilterProxyModel::lessThan( left, right ); } bool CollectionSortFilterProxyModel::lessThanString( const QString a, const QString b ) const { int compareIndices[2]; compareIndices[0] = a.indexOf(QRegExp("\\d")); if ( compareIndices[0] == -1 || (compareIndices[1] = b.indexOf(QRegExp("\\d"))) == -1 || compareIndices[0] != compareIndices[1]) return QString::localeAwareCompare( a, b ) < 0; QString toCompare[2]; int intToCompare[2]; toCompare[0] = a.left( compareIndices[0] ); toCompare[1] = b.left( compareIndices[1] ); int rv = QString::localeAwareCompare( toCompare[0], toCompare[1] ); if( rv != 0 ) return rv < 0; toCompare[0] = a.mid( compareIndices[0] ); toCompare[1] = b.mid( compareIndices[1] ); for( int i = 0; i < 2; ++i ) { compareIndices[i] = toCompare[i].indexOf( QRegExp("\\D") ); if ( compareIndices[i] == -1 ) compareIndices[i] = toCompare[i].length(); intToCompare[i] = toCompare[i].left( compareIndices[i] ).toInt(); } rv = intToCompare[0] - intToCompare[1]; if( rv != 0 ) return rv < 0; for( int i = 0; i < 2; ++i ) toCompare[i] = toCompare[i].mid( compareIndices[i] ); return CollectionSortFilterProxyModel::lessThanString( toCompare[0], toCompare[1] ); } 567060 2 nicholas 2007-12-29 22:29:15 +0000 Better: Index: src/collectionbrowser/CollectionSortFilterProxyModel.h =================================================================== --- src/collectionbrowser/CollectionSortFilterProxyModel.h (revision 754278) +++ src/collectionbrowser/CollectionSortFilterProxyModel.h (working copy) @@ -38,6 +38,7 @@ protected: virtual bool lessThan( const QModelIndex &left, const QModelIndex &right ) const; + virtual bool lessThanString( const QString a, const QString b ) const; }; Index: src/collectionbrowser/CollectionSortFilterProxyModel.cpp =================================================================== --- src/collectionbrowser/CollectionSortFilterProxyModel.cpp (revision 754278) +++ src/collectionbrowser/CollectionSortFilterProxyModel.cpp (working copy) @@ -19,11 +19,16 @@ #include "CollectionSortFilterProxyModel.h" #include "CollectionTreeItem.h" +#include "debug.h" +#include "QVariant" +#include "QString" CollectionSortFilterProxyModel::CollectionSortFilterProxyModel( QObject * parent ) : QSortFilterProxyModel( parent ) { setDynamicSortFilter( true ); + setSortLocaleAware( true ); + setSortCaseSensitivity( Qt::CaseInsensitive ); } @@ -44,6 +49,7 @@ CollectionTreeItem *leftItem = static_cast<CollectionTreeItem*>( left.internalPointer() ); CollectionTreeItem *rightItem = static_cast<CollectionTreeItem*>( right.internalPointer() ); + //Here we catch the bottom 'track' level if( leftItem->level() == rightItem->level() ) { const Meta::TrackPtr leftTrack = Meta::TrackPtr::dynamicCast( leftItem->data() ); @@ -51,7 +57,50 @@ if( !leftTrack.isNull() && !rightTrack.isNull() ) return leftTrack->trackNumber() < rightTrack->trackNumber(); } - return QSortFilterProxyModel::lessThan( left, right ); //Bad idea fallthrough + + //This should catch everything else + QVariant leftData = left.data(); + QVariant rightData = right.data(); + if( leftData.canConvert( QVariant::String ) && rightData.canConvert( QVariant::String ) ) { + return lessThanString( leftData.toString().toLower(), rightData.toString().toLower() ); + } + + warning() << "failed: an unexpected comparison was made"; + + //Just in case + return QSortFilterProxyModel::lessThan( left, right ); } +bool +CollectionSortFilterProxyModel::lessThanString( const QString a, const QString b ) const +{ + int compareIndices[2]; + compareIndices[0] = a.indexOf(QRegExp("\\d")); + if ( compareIndices[0] == -1 || (compareIndices[1] = b.indexOf(QRegExp("\\d"))) == -1 + || compareIndices[0] != compareIndices[1]) + return QString::localeAwareCompare( a, b ) < 0; + QString toCompare[2]; + int intToCompare[2]; + toCompare[0] = a.left( compareIndices[0] ); + toCompare[1] = b.left( compareIndices[1] ); + int rv = QString::localeAwareCompare( toCompare[0], toCompare[1] ); + if( rv != 0 ) return rv < 0; + + toCompare[0] = a.mid( compareIndices[0] ); + toCompare[1] = b.mid( compareIndices[1] ); + for( int i = 0; i < 2; ++i ) + { + compareIndices[i] = toCompare[i].indexOf( QRegExp("\\D") ); + if ( compareIndices[i] == -1 ) compareIndices[i] = toCompare[i].length(); + intToCompare[i] = toCompare[i].left( compareIndices[i] ).toInt(); + } + + rv = intToCompare[0] - intToCompare[1]; + if( rv != 0 ) return rv < 0; + + for( int i = 0; i < 2; ++i ) + toCompare[i] = toCompare[i].mid( compareIndices[i] ); + + return CollectionSortFilterProxyModel::lessThanString( toCompare[0], toCompare[1] ); +} 567063 3 ruiz 2007-12-29 22:34:16 +0000 Thanks for the patch! But can you please attach it to the bug report, not as a text dump? Use the command: svn diff > mypatch.diff then upload the diff file. Cheers 567239 4 22777 nicholas 2007-12-30 20:31:42 +0000 Created attachment 22777 Fixes the sorting behaviour 657080 5 ruiz 2008-10-26 11:19:38 +0000 SVN commit 876025 by seb: Collection browser: Use an intelligent natural sort algorithm which isn't necessarily a lexicographical comparison. Eg: "Symphony 2" < "Symphony 10" Patch by Nicholas Wilson <nicholas@nickcwilson.co.uk> BUG: 154408 @nick: sorry it took so long to apply this patch. a combination of new years and me being overseas directly after that obviously contributing factors to overlooking your patch :) M +63 -1 CollectionSortFilterProxyModel.cpp M +1 -2 CollectionSortFilterProxyModel.h M +3 -3 CollectionTreeItemModelBase.cpp WebSVN link: http://websvn.kde.org/?view=rev&revision=876025 657081 6 ruiz 2008-10-26 11:21:39 +0000 SVN commit 876026 by seb: Update changelog CCBUG: 154408 M +3 -0 ChangeLog WebSVN link: http://websvn.kde.org/?view=rev&revision=876026 22777 2007-12-30 20:31:42 +0000 2007-12-30 20:31:42 +0000 Fixes the sorting behaviour sortingPatch.diff text/plain 3842 nicholas SW5kZXg6IHNyYy9jb2xsZWN0aW9uYnJvd3Nlci9Db2xsZWN0aW9uU29ydEZpbHRlclByb3h5TW9k ZWwuaCAKID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT0gCiAtLS0gc3JjL2NvbGxlY3Rpb25icm93c2VyL0NvbGxlY3Rpb25T b3J0RmlsdGVyUHJveHlNb2RlbC5oICAgICAgKHJldmlzaW9uIDc1NDI3OCkgCiArKysgc3JjL2Nv bGxlY3Rpb25icm93c2VyL0NvbGxlY3Rpb25Tb3J0RmlsdGVyUHJveHlNb2RlbC5oICAgICAgKHdv cmtpbmcgY29weSkgCiAgYXQgIGF0ICAtMzgsNiArMzgsNyAgYXQgIGF0IAogCiAgICAgIHByb3Rl Y3RlZDogCiAgICAgICAgICB2aXJ0dWFsIGJvb2wgbGVzc1RoYW4oIGNvbnN0IFFNb2RlbEluZGV4 ICZsZWZ0LCBjb25zdCBRTW9kZWxJbmRleCAmcmlnaHQgKSBjb25zdDsgCiArICAgICAgICB2aXJ0 dWFsIGJvb2wgbGVzc1RoYW5TdHJpbmcoIGNvbnN0IFFTdHJpbmcgYSwgY29uc3QgUVN0cmluZyBi ICkgY29uc3Q7IAogCiAKICB9OyAKIEluZGV4OiBzcmMvY29sbGVjdGlvbmJyb3dzZXIvQ29sbGVj dGlvblNvcnRGaWx0ZXJQcm94eU1vZGVsLmNwcCAKID09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0gCiAtLS0gc3JjL2NvbGxl Y3Rpb25icm93c2VyL0NvbGxlY3Rpb25Tb3J0RmlsdGVyUHJveHlNb2RlbC5jcHAgICAgKHJldmlz aW9uIDc1NDI3OCkgCiArKysgc3JjL2NvbGxlY3Rpb25icm93c2VyL0NvbGxlY3Rpb25Tb3J0Rmls dGVyUHJveHlNb2RlbC5jcHAgICAgKHdvcmtpbmcgY29weSkgCiAgYXQgIGF0ICAtMTksMTEgKzE5 LDE2ICBhdCAgYXQgCiAKICAjaW5jbHVkZSAiQ29sbGVjdGlvblNvcnRGaWx0ZXJQcm94eU1vZGVs LmgiIAogICNpbmNsdWRlICJDb2xsZWN0aW9uVHJlZUl0ZW0uaCIgCiArI2luY2x1ZGUgImRlYnVn LmgiIAogKyNpbmNsdWRlICJRVmFyaWFudCIgCiArI2luY2x1ZGUgIlFTdHJpbmciIAogCiAgQ29s bGVjdGlvblNvcnRGaWx0ZXJQcm94eU1vZGVsOjpDb2xsZWN0aW9uU29ydEZpbHRlclByb3h5TW9k ZWwoICBRT2JqZWN0ICogcGFyZW50ICkgCiAgIDogUVNvcnRGaWx0ZXJQcm94eU1vZGVsKCBwYXJl bnQgKSAKICB7IAogICAgICBzZXREeW5hbWljU29ydEZpbHRlciggdHJ1ZSApOyAKICsgICAgc2V0 U29ydExvY2FsZUF3YXJlKCB0cnVlICk7IAogKyAgICBzZXRTb3J0Q2FzZVNlbnNpdGl2aXR5KCBR dDo6Q2FzZUluc2Vuc2l0aXZlICk7IAogIH0gCiAKIAogIGF0ICBhdCAgLTQ0LDYgKzQ5LDcgIGF0 ICBhdCAKICAgICAgQ29sbGVjdGlvblRyZWVJdGVtICpsZWZ0SXRlbSA9IHN0YXRpY19jYXN0PENv bGxlY3Rpb25UcmVlSXRlbSo+KCBsZWZ0LmludGVybmFsUG9pbnRlcigpICk7IAogICAgICBDb2xs ZWN0aW9uVHJlZUl0ZW0gKnJpZ2h0SXRlbSA9IHN0YXRpY19jYXN0PENvbGxlY3Rpb25UcmVlSXRl bSo+KCByaWdodC5pbnRlcm5hbFBvaW50ZXIoKSApOyAKIAogKyAgICAvL0hlcmUgd2UgY2F0Y2gg dGhlIGJvdHRvbSAndHJhY2snIGxldmVsIAogICAgICBpZiggbGVmdEl0ZW0tPmxldmVsKCkgPT0g cmlnaHRJdGVtLT5sZXZlbCgpICkgCiAgICAgIHsgCiAgICAgICAgICBjb25zdCBNZXRhOjpUcmFj a1B0ciBsZWZ0VHJhY2sgPSBNZXRhOjpUcmFja1B0cjo6ZHluYW1pY0Nhc3QoIGxlZnRJdGVtLT5k YXRhKCkgKTsgCiAgYXQgIGF0ICAtNTEsNyArNTcsNTAgIGF0ICBhdCAKICAgICAgICAgIGlmKCAh bGVmdFRyYWNrLmlzTnVsbCgpICAmJiAhcmlnaHRUcmFjay5pc051bGwoKSApIAogICAgICAgICAg ICAgIHJldHVybiBsZWZ0VHJhY2stPnRyYWNrTnVtYmVyKCkgPCByaWdodFRyYWNrLT50cmFja051 bWJlcigpOyAKICAgICAgfSAKIC0gICAgcmV0dXJuIFFTb3J0RmlsdGVyUHJveHlNb2RlbDo6bGVz c1RoYW4oIGxlZnQsIHJpZ2h0ICk7IC8vQmFkIGlkZWEgZmFsbHRocm91Z2ggCiArIAogKyAgICAv L1RoaXMgc2hvdWxkIGNhdGNoIGV2ZXJ5dGhpbmcgZWxzZSAKICsgICAgUVZhcmlhbnQgbGVmdERh dGEgPSBsZWZ0LmRhdGEoKTsgCiArICAgIFFWYXJpYW50IHJpZ2h0RGF0YSA9IHJpZ2h0LmRhdGEo KTsgCiArICAgIGlmKCBsZWZ0RGF0YS5jYW5Db252ZXJ0KCBRVmFyaWFudDo6U3RyaW5nICkgJiYg cmlnaHREYXRhLmNhbkNvbnZlcnQoIFFWYXJpYW50OjpTdHJpbmcgKSApIHsgCiArICAgICAgICBy ZXR1cm4gbGVzc1RoYW5TdHJpbmcoIGxlZnREYXRhLnRvU3RyaW5nKCkudG9Mb3dlcigpLCByaWdo dERhdGEudG9TdHJpbmcoKS50b0xvd2VyKCkgKTsgCiArICAgIH0gCiArIAogKyAgICB3YXJuaW5n KCkgPDwgImZhaWxlZDogYW4gdW5leHBlY3RlZCBjb21wYXJpc29uIHdhcyBtYWRlIjsgCiArIAog KyAgICAvL0p1c3QgaW4gY2FzZSAKICsgICAgcmV0dXJuIFFTb3J0RmlsdGVyUHJveHlNb2RlbDo6 bGVzc1RoYW4oIGxlZnQsIHJpZ2h0ICk7IAogIH0gCiAKICtib29sIAogK0NvbGxlY3Rpb25Tb3J0 RmlsdGVyUHJveHlNb2RlbDo6bGVzc1RoYW5TdHJpbmcoIGNvbnN0IFFTdHJpbmcgYSwgY29uc3Qg UVN0cmluZyBiICkgY29uc3QgCiAreyAKICsgICAgaW50IGNvbXBhcmVJbmRpY2VzWzJdOyAKICsg ICAgY29tcGFyZUluZGljZXNbMF0gPSBhLmluZGV4T2YoUVJlZ0V4cCgiXFxkIikpOyAKICsgICAg aWYgKCBjb21wYXJlSW5kaWNlc1swXSA9PSAtMSB8fCAoY29tcGFyZUluZGljZXNbMV0gPSBiLmlu ZGV4T2YoUVJlZ0V4cCgiXFxkIikpKSA9PSAtMSAKICsgICAgICAgICAgICB8fCBjb21wYXJlSW5k aWNlc1swXSAhPSBjb21wYXJlSW5kaWNlc1sxXSkgCiArICAgICAgICByZXR1cm4gUVN0cmluZzo6 bG9jYWxlQXdhcmVDb21wYXJlKCBhLCBiICkgPCAwOyAKIAogKyAgICBRU3RyaW5nIHRvQ29tcGFy ZVsyXTsgCiArICAgIGludCBpbnRUb0NvbXBhcmVbMl07IAogKyAgICB0b0NvbXBhcmVbMF0gPSBh LmxlZnQoIGNvbXBhcmVJbmRpY2VzWzBdICk7IAogKyAgICB0b0NvbXBhcmVbMV0gPSBiLmxlZnQo IGNvbXBhcmVJbmRpY2VzWzFdICk7IAogKyAgICBpbnQgcnYgPSBRU3RyaW5nOjpsb2NhbGVBd2Fy ZUNvbXBhcmUoIHRvQ29tcGFyZVswXSwgdG9Db21wYXJlWzFdICk7IAogKyAgICBpZiggcnYgIT0g MCApIHJldHVybiBydiA8IDA7IAogKyAKICsgICAgdG9Db21wYXJlWzBdID0gYS5taWQoIGNvbXBh cmVJbmRpY2VzWzBdICk7IAogKyAgICB0b0NvbXBhcmVbMV0gPSBiLm1pZCggY29tcGFyZUluZGlj ZXNbMV0gKTsgCiArICAgIGZvciggaW50IGkgPSAwOyBpIDwgMjsgKytpICkgCiArICAgIHsgCiAr ICAgICAgICBjb21wYXJlSW5kaWNlc1tpXSA9IHRvQ29tcGFyZVtpXS5pbmRleE9mKCBRUmVnRXhw KCJcXEQiKSApOyAKICsgICAgICAgIGlmICggY29tcGFyZUluZGljZXNbaV0gPT0gLTEgKSBjb21w YXJlSW5kaWNlc1tpXSA9IHRvQ29tcGFyZVtpXS5sZW5ndGgoKTsgCiArICAgICAgICBpbnRUb0Nv bXBhcmVbaV0gPSB0b0NvbXBhcmVbaV0ubGVmdCggY29tcGFyZUluZGljZXNbaV0gKS50b0ludCgp OyAKICsgICAgfSAKICsgCiArICAgIHJ2ID0gaW50VG9Db21wYXJlWzBdIC0gaW50VG9Db21wYXJl WzFdOyAKICsgICAgaWYoIHJ2ICE9IDAgKSByZXR1cm4gcnYgPCAwOyAKICsgCiArICAgIGZvcigg aW50IGkgPSAwOyBpIDwgMjsgKytpICkgCiArICAgICAgICB0b0NvbXBhcmVbaV0gPSAgdG9Db21w YXJlW2ldLm1pZCggY29tcGFyZUluZGljZXNbaV0gKTsgCiArIAogKyAgICByZXR1cm4gQ29sbGVj dGlvblNvcnRGaWx0ZXJQcm94eU1vZGVsOjpsZXNzVGhhblN0cmluZyggdG9Db21wYXJlWzBdLCB0 b0NvbXBhcmVbMV0gKTsgCiArfSAKIAo=