QStringList Sorting

[QbelcorT]

Hi,
I have a QStringList in which I am trying to sort before I insert into a QComboBox.
The names are "background1.jpg, background2.jpg... background15.jpg. or user1..userX.jpg
The sort applies the order as such:
background1.jpg
background10.jpg
background11.jpg..
background2.jpg..etc

I need the list sorted in this order.
background1.jpg
background2.jpg
background3.jpg
...background10.jpg
background11.jpg

I have read the QMap but I cannot understand how to apply the sorting method I am looking for. Can anyone suggest a method?

Here is my code, it will either get my background files from a USB drive (for copying) or from the local filesystem for selecting in a combobox.


QStringList getBackGroundFiles(int val)
{
QDir dir;
if (val == LOCAL)
dir.setPath(BKGNDIMAGEPATHLOCAL);
else
dir.setPath(BACKIMAGEPATH);
QStringList fileFilter,fileNames,names;
fileFilter << "*.jpg" << "*.bmp";
dir.setNameFilters(fileFilter);
names << "user*" << "background*";
fileNames = dir.entryList(names,QDir::Files);
fileNames.sort();
return fileNames;
}

[nish]

use qSort()


qSort(filenames.begin(),filenames.end(),compareNam es)

bool compareNames(const QString& s1,const QString& s2)
{
//apply section(),mid() or whatever to take out the integer part and compare

//for example if all the strings are like "userXXX.jpg"
QString temp1=s1.section("user",1);//temp1=="XXX.jpg";
temp1=temp1.section('.',0,0);//temp1=="XXX"

QString temp2=s2.section("user",1);
temp2=temp2.section('.',0,0);

return (temp1.toInt()<temp2.toInt());

//your code would be more complicated than this as u have different file names
//and filenames may also contain periods(.) more than once


}

hope this helps

[QbelcorT]

Thank you. It pointed me in the right direction. This modified sorting technique works as I want it to. There are 15 background and 9 user. So I do not need to worry about sorting the "user" numbers. I just need to make sure it is sorted alpabetically, by numbers.
background1.jpg
background2.jpg..
background15.jpg
user1.jpg..
user9.jpg



bool compareNames(const QString& s1,const QString& s2)
{
//for example if all the strings are like "userXXX.jpg"
QString temp1=s1.section("background",1);//temp1=="XXX.jpg";
temp1=temp1.section('.',0,0); //temp1=="XXX"
QString temp2=s2.section("background",1);
temp2=temp2.section('.',0,0);
if (s1.contains("user",Qt::CaseInsensitive) || s2.contains("user",Qt::CaseInsensitive))
return(s1.toLower() < s2.toLower()); // return the string sorted alpabetically
else
return (temp1.toInt()<temp2.toInt()); // return the file no sorted numerically
}

[JohannesMunk]

Hi there!

Just read this.. and thought that hardcoding "background" probably isn't the most beautiful approach :->

What about this:



bool compareNames(const QString& s1,const QString& s2)
{
// ignore common prefix..
int i = 0;
while ((i < s1.length()) && (i < s2.length()) && (s1.at(i).toLower() == s2.at(i).toLower())) ++i;
++i;
// something left to compare?
if ((i < s1.length()) && (i < s2.length()))
{
// get relevant/signficant number string for s1
int k = i;QString n1 = "";
while ((k < s1.length()) && (s1.at(k).isNumber()) {n1 += s1.at(k);++k;}

// get relevant/signficant number string for s2
k = i;QString n2 = "";
while ((k < s2.length()) && (s2.at(k).isNumber()) {n2 += s2.at(k);++k;}

// got two numbers to compare?
if (!n1.isEmpty() && !n2.isEmpty())
{
return n1.toInt() < n2.toInt();
}
else {
// not a number has to win over a number.. number could have ended earlier... same prefix..
if (!n1.isEmpty()) return false;
if (!n2.isEmpty()) return true;
return s1.at(i) < s2.at(i);
}
}
else {
// shortest string wins
return s1.length() < s2.length();
}
}


Didn't compile/test this.. just to give you the idea.. Should also be able to sort something like: "abc 10.1.txt, abc 1.4.txt, abc 10.10.txt, def 1.txt"

Now I can forget about this again :->

Joh

Edit: Added to Lower in the prefix compare..
Edit: Added empty case.. more complicated than I thought.. should test this.. :->

[Lykurg]

Hi,

a lot of loops, QRegExp would might be the better solution to separate any prefix from counting at the end...


Should also be able to sort something like: "abc 10.1.txt, abc 1.4.txt, abc 10.10.txt, def 1.txt"

No, because of:



while ((k < s1.length()) && (s1.at(k).isNumber()) {n1 += s1.at(k);++k;}

Example:

bla_10.1.txt => 101
bla_2.34.txt => 234

==> order will be 10.1, 2.34

Beside points in file names aren't the best decision.



That's just a quick note.

[JohannesMunk]

Hi,
a lot of loops, QRegExp would might be the better solution to separate any prefix from counting at the end...


Yeah.. thought about QRegExp.. but than.. it occured to me.. that maybe the file list might get bigger than two entries.. and than creating a QRegExp for each n*log(n) compares is really slow. And BTW.. QRegExp needs to loop over the characters as well!



No, because of:
Example:

bla_10.1.txt => 101
bla_2.34.txt => 234



No.. the while goes on only as long as it finds numbers.. read it again!



That's just a quick note.


Too quick, I'm afraid!

[Lykurg]

Ok, I see, too quick:o

But with "abc-2.00234" and "abc-2.12352" n1 == n2 == 2?

Anyway, may it not be better/quicker first to determinate the number on the end of the string, and then chop the x characters (x = length of the determinated number)? Of course it depends of the string list you compare. Many different prefixes exterminating from the front would be faster...


Also interesting would be a speed comparison with a member reg expression...

[JohannesMunk]

Ok, I see, too quick:o
But with "abc-2.00234" and "abc-2.12352" n1 == n2 == 2?


No! "abc-2." would fall into the common prefix (while s1.at(i) == s2.at(i)). Thus: n1="00234", n2="12352"



Anyway, may it not be better/quicker first to determinate the number on the end of the string, and then chop the x characters (x = length of the determinated number)? Of course it depends of the string list you compare. Many different prefixes exterminating from the front would be faster...


Well the last number could be equal. I think the approach to find the biggest common prefix and then look for the difference is the way to go. Thats how a natural/human sort does work anyway.



Also interesting would be a speed comparison with a member reg expression...


There is no doubt in my mind, that the explicit while loop will be faster. Even when you use a member RegExp, so that its mask-parsing is only done once.. the reg-exp-fitting code is much more general and thus carries a lot of overhead, compared to this specialized solution..

The code would perhaps be more readable.. But I'm not so sure :->

Greetings!

Joh

[JohannesMunk]

Thinking about it again.. my natural sort doesn't work for "a2002, a20001". Here n1 would be ="2" and n2="01". So n2.toInt() < n1.toInt().. which is wrong, when you look at the whole number..

So from the first different character we also need to look backward and add all adjacent numbers:



bool compareNames(const QString& s1,const QString& s2)
{
// ignore common prefix..
int i = 0;
while ((i < s1.length()) && (i < s2.length()) && (s1.at(i).toLower() == s2.at(i).toLower())) ++i;
++i;
// something left to compare?
if ((i < s1.length()) && (i < s2.length()))
{
// get number prefix from position i - doesnt matter from which string
int k = i-1;QString n = "";
while ((k >= 0) && (s1.at(k).isNumber())) {n = s1.at(k)+n;--k;}

// get relevant/signficant number string for s1
k = i;QString n1 = "";
while ((k < s1.length()) && (s1.at(k).isNumber()) {n1 += s1.at(k);++k;}

// get relevant/signficant number string for s2
k = i;QString n2 = "";
while ((k < s2.length()) && (s2.at(k).isNumber()) {n2 += s2.at(k);++k;}

// got two numbers to compare?
if (!n1.isEmpty() && !n2.isEmpty())
{
return (n+n1).toInt() < (n+n2).toInt();
}
else {
// not a number has to win over a number.. number could have ended earlier... same prefix..
if (!n1.isEmpty()) return false;
if (!n2.isEmpty()) return true;
return s1.at(i) < s2.at(i);
}
}
else {
// shortest string wins
return s1.length() < s2.length();
}
}

[^Nisok^]

I want to do the same thing sort of a class QStrings as integers. But I don't know where to put the functinon compareNames. As a class function? Or should I extend the qSort class?

[faldzip]

qSort is not a class but function.
make your function compareNames as a global function or static class method or a struct with operator() (and pass object of that struct).

[soxs060389]

I'd suggest first to determine the name sheme before throwing solutions at each other and then just use the one that fits the purpose....

[QwertyManiac]

For an implementation of Natural-Order Sorting (Case sensitive or non) you can have a look at the GPL code by Tobias Koenig <tokoe@kde.org> in these links: [Header - qnatsort.h (http://websvn.kde.org/trunk/KDE/kdegraphics/okular/generators/comicbook/qnatsort.h?view=markup)] [Source - qnatsort.cpp (http://websvn.kde.org/trunk/KDE/kdegraphics/okular/generators/comicbook/qnatsort.cpp?view=markup)]

An implementation using qSort() is explained in the comments - you simply have to pass the included function.

[bismitapadhy]

in qsort you are passing comparenames, comparenames taking two string parameter, what are those parameter we need to give?

[JohannesMunk]

In the above examples we provided our own LessThan-function, so we were using this qsort definition:


template <typename RandomAccessIterator, typename LessThan>
inline void qSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)


The third argument is a function pointer to a user-defined-function with two parameters of the container type, that returns true only if the first argument is "less" than the second.


bool compareNames(const T &t1, const T &t2) const ..

So you do not give any parameters to compareNames. You just call:


qSort(strlist.begin(),strlist.end(),compareNames);

qSort then calls compareNames each time it needs to establish the order of two strings while sorting the whole thing.

HIH

Johannes

[bismitapadhy]

passing comparenames as 3rd paramete in qsort, it is giving a error that

rror C2664: 'void __cdecl qSort(class QList<class QString>::iterator,class QList<class QString>::iterator,bool (__thiscall *)(const class QString &,const class QString &))' : cannot convert parameter 3 from 'bool
(const class QString &,const class QString &)' to 'bool (__thiscall *)(const class QString &,const class QString &)'
None of the functions with this name in scope match the target type.

How i will pass comparenames as a parameter?

[JohannesMunk]

compareNames must be a plain method, not a member function.

Below you can see a complete code example, that compiles and works as it should.



#include <QtGui>
#include <QStringList>
#include <QDebug>

bool compareNames(const QString& s1,const QString& s2)
{
// ignore common prefix..
int i = 0;
while ((i < s1.length()) && (i < s2.length()) && (s1.at(i).toLower() == s2.at(i).toLower())) ++i;
++i;
// something left to compare?
if ((i < s1.length()) && (i < s2.length()))
{
// get number prefix from position i - doesnt matter from which string
int k = i-1;QString n = "";
while ((k >= 0) && (s1.at(k).isNumber())) {n = s1.at(k)+n;--k;}

// get relevant/signficant number string for s1
k = i;QString n1 = "";
while ((k < s1.length()) && (s1.at(k).isNumber())) {n1 += s1.at(k);++k;}

// get relevant/signficant number string for s2
k = i;QString n2 = "";
while ((k < s2.length()) && (s2.at(k).isNumber())) {n2 += s2.at(k);++k;}

// got two numbers to compare?
if (!n1.isEmpty() && !n2.isEmpty())
{
return (n+n1).toInt() < (n+n2).toInt();
}
else {
// not a number has to win over a number.. number could have ended earlier... same prefix..
if (!n1.isEmpty()) return false;
if (!n2.isEmpty()) return true;
return s1.at(i) < s2.at(i);
}
}
else {
// shortest string wins
return s1.length() < s2.length();
}
}

int main(int argc, char *argv[])
{
QApplication a(argc, argv);

QStringList strlist;
strlist << "a_9898" << "a_55" << "a_100000";

qSort(strlist.begin(),strlist.end(),compareNames);

qDebug() << strlist;

return 0;
}


Johannes

[Gizmo]

compareNames must be a plain method, not a member function.

Below you can see a complete code example, that compiles and works as it should.


Nice function, very useful. Therefore I think there is a mistake on the indexes and for my part I would add a test if there is no number.


bool SailSlideShowWidget::compareNames(const QString& s1,const QString& s2)
{
// ignore common prefix..
int i = 0;
while ((i < s1.length()) && (i < s2.length()) && (s1.at(i).toLower() == s2.at(i).toLower()))
++i;
++i;
// something left to compare?
if ((i < s1.length()) && (i < s2.length()))
{
// get number prefix from position i - doesnt matter from which string
int k = i-1;
//If not number return native comparator
if(!s1.at(k).isNumber() || !s2.at(k).isNumber())
{
return QString::compare(s1, s2, Qt::CaseSensitive) < 0;
}
QString n = "";
k--;
while ((k >= 0) && (s1.at(k).isNumber()))
{
n = s1.at(k)+n;
--k;
}
// get relevant/signficant number string for s1
k = i-1;
QString n1 = "";
while ((k < s1.length()) && (s1.at(k).isNumber()))
{
n1 += s1.at(k);
++k;
}

// get relevant/signficant number string for s2
//Decrease by
k = i-1;
QString n2 = "";
while ((k < s2.length()) && (s2.at(k).isNumber()))
{
n2 += s2.at(k);
++k;
}

// got two numbers to compare?
if (!n1.isEmpty() && !n2.isEmpty())
{
return (n+n1).toInt() < (n+n2).toInt();
}
else
{
// not a number has to win over a number.. number could have ended earlier... same prefix..
if (!n1.isEmpty())
return false;
if (!n2.isEmpty())
return true;
return s1.at(i) < s2.at(i);
}
}
else {
// shortest string wins
return s1.length() < s2.length();
}
}


Thank you anyway for that!
Giz

[Gizmo]

Nice function, very useful. Therefore I think there is a mistake on the indexes and for my part I would add a test if there is no number.

There's a slight error in the code I posted. If for example the number to compare is not at the end of the string, before ".jpg" but at the beginning followed by a underscore ("_"). The function will return a wrong and unstable value. Why? Because "." is before numbers and "_" after numbers in the ASCII table. As long as I am doing the native comparison for two numbers with a different length, a bug should pop up. Example with "1_..." & "12_..." sometimes it will return true sometimes false. But it should return the smallest which is always "1" (1 < 12).


bool SailSlideShowWidget::compareNames(const QString& s1,const QString& s2)
{
// ignore common prefix..
int i = 0;
while ((i < s1.length()) && (i < s2.length()) && (s1.at(i).toLower() == s2.at(i).toLower()))
++i;
++i;
// something left to compare?
if ((i < s1.length()) && (i < s2.length()))
{
// get number prefix from position i - doesnt matter from which string
int k = i-1;
//If not number return native comparator
if(!s1.at(k).isNumber() || !s2.at(k).isNumber())
{
//Two next lines
//E.g. 1_... < 12_...
if(s1.at(k).isNumber())
return false;
if(s2.at(k).isNumber())
return true;
return QString::compare(s1, s2, Qt::CaseSensitive) < 0;
}
QString n = "";
k--;
while ((k >= 0) && (s1.at(k).isNumber()))
{
n = s1.at(k)+n;
--k;
}
// get relevant/signficant number string for s1
k = i-1;
QString n1 = "";
while ((k < s1.length()) && (s1.at(k).isNumber()))
{
n1 += s1.at(k);
++k;
}

// get relevant/signficant number string for s2
//Decrease by
k = i-1;
QString n2 = "";
while ((k < s2.length()) && (s2.at(k).isNumber()))
{
n2 += s2.at(k);
++k;
}

// got two numbers to compare?
if (!n1.isEmpty() && !n2.isEmpty())
return (n+n1).toInt() < (n+n2).toInt();
else
{
// not a number has to win over a number.. number could have ended earlier... same prefix..
if (!n1.isEmpty())
return false;
if (!n2.isEmpty())
return true;
return s1.at(i) < s2.at(i);
}
}
else
{
// shortest string wins
return s1.length() < s2.length();
}
}


I hope this is correct and at least now I get a decent result with all strings.

Giz

[nish]

There's a slight error in the code I posted. If for example the number to compare is not at the end of the string, before ".jpg" but at the beginning followed by a underscore ("_"). The function will return a wrong and unstable value. Why? Because "." is before numbers and "_" after numbers in the ASCII table. As long as I am doing the native comparison for two numbers with a different length, a bug should pop up. Example with "1_..." & "12_..." sometimes it will return true sometimes false. But it should return the smallest which is always "1" (1 < 12).


bool SailSlideShowWidget::compareNames(const QString& s1,const QString& s2)
{
// ignore common prefix..
int i = 0;
while ((i < s1.length()) && (i < s2.length()) && (s1.at(i).toLower() == s2.at(i).toLower()))
++i;
++i;
// something left to compare?
if ((i < s1.length()) && (i < s2.length()))
{
// get number prefix from position i - doesnt matter from which string
int k = i-1;
//If not number return native comparator
if(!s1.at(k).isNumber() || !s2.at(k).isNumber())
{
//Two next lines
//E.g. 1_... < 12_...
if(s1.at(k).isNumber())
return false;
if(s2.at(k).isNumber())
return true;
return QString::compare(s1, s2, Qt::CaseSensitive) < 0;
}
QString n = "";
k--;
while ((k >= 0) && (s1.at(k).isNumber()))
{
n = s1.at(k)+n;
--k;
}
// get relevant/signficant number string for s1
k = i-1;
QString n1 = "";
while ((k < s1.length()) && (s1.at(k).isNumber()))
{
n1 += s1.at(k);
++k;
}

// get relevant/signficant number string for s2
//Decrease by
k = i-1;
QString n2 = "";
while ((k < s2.length()) && (s2.at(k).isNumber()))
{
n2 += s2.at(k);
++k;
}

// got two numbers to compare?
if (!n1.isEmpty() && !n2.isEmpty())
return (n+n1).toInt() < (n+n2).toInt();
else
{
// not a number has to win over a number.. number could have ended earlier... same prefix..
if (!n1.isEmpty())
return false;
if (!n2.isEmpty())
return true;
return s1.at(i) < s2.at(i);
}
}
else
{
// shortest string wins
return s1.length() < s2.length();
}
}


I hope this is correct and at least now I get a decent result with all strings.

Giz

Man, you do remember to fix your code! After almost an year!!