Bug 154408 - collection sort should not always be lexicographic
Summary: collection sort should not always be lexicographic
Status: RESOLVED FIXED
Alias: None
Product: amarok
Classification: Unclassified
Component: general (show other bugs)
Version: 1.4.7
Platform: Debian testing Linux
: NOR wishlist (vote)
Target Milestone: ---
Assignee: Amarok Developers
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2007-12-21 02:24 UTC by Nicholas Wilson
Modified: 2008-10-26 11:21 UTC (History)
0 users

See Also:
Latest Commit:
Version Fixed In:


Attachments
Fixes the sorting behaviour (3.75 KB, patch)
2007-12-30 20:31 UTC, Nicholas Wilson
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Nicholas Wilson 2007-12-21 02:24:20 UTC
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.
Comment 1 Nicholas Wilson 2007-12-29 22:20:36 UTC
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] );
}
Comment 2 Nicholas Wilson 2007-12-29 22:29:15 UTC
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] );
+}
Comment 3 Seb Ruiz 2007-12-29 22:34:16 UTC
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
Comment 4 Nicholas Wilson 2007-12-30 20:31:42 UTC
Created attachment 22777 [details]
Fixes the sorting behaviour
Comment 5 Seb Ruiz 2008-10-26 11:19:38 UTC
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
Comment 6 Seb Ruiz 2008-10-26 11:21:39 UTC
SVN commit 876026 by seb:

Update changelog
CCBUG: 154408


 M  +3 -0      ChangeLog  


WebSVN link: http://websvn.kde.org/?view=rev&revision=876026