Wiki de QtFR.org

Des tutos, des articles et des trucs et astuces

Outils pour utilisateurs

Outils du site


implementation_d_un_algorithme_de_tri_personnalise

Implémentation d'un tri personnalisé et utilisation


Préambule

L'objectif de ce tutoriel est de montrer l'utilisation d'un algorithme de tri simple sur différentes classes Qt, comme les QStringList, QListWidget, QlistView…
Il ne s'agit pas du développement d'un algorithme de tri complexe, mais juste d'en voir son intégration.


Ce tutoriel a été initié par deux questions sur le forum :

Le postulat de départ était : “Comment trier mes noms de fichiers dans l'ordre alphabétique, sachant qu'ils sont sous la forme : 1.jpg, 2.jpg, 10.jgp, 11.jpg”.
On voit très vite que la fonction “sort” de base renverra une liste triée dans cet ordre : 1.jpg, 10.jpg, 11.jpg, 2.jpg.
Nous verrons donc comment trier facilement ces QString, afin d'arriver au résultat escompté : 1.jpg, 2.jpg, 10.jpg, 11.jpg.

Le membre voulait trier sa liste en fonction d'un membre de sa classe.

Ces deux questions étant étroitement liée sur les mécanismes de tri, elle seront traitées ensembles.

C'est parti!


L'algorithme de la fonction de tri

Cette fonction est très simple, nous allons transformer temporairement, et surtout pas physiquement, les noms de fichiers pour qu'ils soient formatés de la manière suivante : 01.jpg, 02.jpg, 10.jpg, 11.jpg. Ainsi, la fonction de tri fonctionnera correctement.

L'exemple ci-dessous montre pourquoi l'algorithme par défaut ne convient pas.
Pour faciliter la lecture, je fais juste une comparaison de 2 QString.
Les données de départ :

    //données de départ
    QString const str1 = "10.jpg";
    QString const str2 = "2.jpg";
 //LE TRI Qt
    //le tri par défaut utilisé pour QStringList::sort(Qt::CaseSensitivity cs = Qt::CaseSensitive)
    //utilise la méthode QString::compare, qui fait une comparaison de la même manière que 
    //bool operator<(const QString &s1, const QString &s2)
    //au final, le retour est une comparaison unicode str1.at(n).unicode() -  str2.at(n).unicode() 
    //où n est la position du premier QChar différent.
    //Si on décompose ce qui se passe au niveau de la comparaison :
    QStringList strList;
    if (str1.compare(str2, Qt::CaseInsensitive) < 0) { //ici compare renverra -1 : car 
                                                       //str1.at(0).unicode() == 48 et str2.at(0).unicode() == 49
        strList.append(str1); //str1 est plus petit, donc nous le stockons en premier
        strList.append(str2); //str2 est plus grand, donc nous le stockons en second
    }
    else { //sinon, nous faisons l'inverse
        strList.append(str2);
        strList.append(str1);
    }
    qDebug() << strList; //affiche 10.jpg puis 2.jpg

Maintenant nous allons réaliser de la même manière l'algorithme qui nous permettra d'arriver à un tri convenable pour notre cas.

    //on a vu que 10 est < 2 en string
    //donc on va modifier les chaînes de caractères pour avoir 10 et 02,
    //comme ça nous aurons bien 02 < 10 avec la fonction QString::compare
    //on veut que 10.jpg reste identique et 2.jpg devienne 02.jpg
    //les 2 strings doivent avoir la même taille, c'est-à-dire 2, si on oculte l'extension
    //on se sert de QFileInfo pour récupérer le nom du fichier sans l'extension
    QStringList strList;
    QString const baseName1 = QFileInfo(str1).baseName();
    QString const baseName2 = QFileInfo(str2).baseName();
    //on récupère la taille maximale
    int const maxSize = baseName1.size() > baseName2.size() ? baseName1.size() : baseName2.size();
 
    //ici on remplit les chaînes avec des 0 pour atteindre la taille maxSise
    QString const newFileName1 = baseName1.rightJustified(maxSize, '0');
    QString const newFileName2 = baseName2.rightJustified(maxSize, '0');
 
    //ici on remplit la liste triée
    if (newFileName1 < newFileName2) { // équivalent à if (newFileName1.compare(newFileName2, Qt::CaseInsensitive) < 0)
        strList.append(str1);
        strList.append(str2);
    }
     else {
        strList.append(str2);
        strList.append(str1);
    }
    qDebug() << strList; //affiche 2.jpg puis 10.jpg
 

Mise en oeuvre

Nous voyons donc que le tri se réalise avec un opérateur de comparaison. Prenons nos 2 fichiers 10.jpg (str1) et 02.jpg (str2).
Dans le cas de QString::compare Qt ferait :

return str1.at(0).unicode() -  str2.at(0).unicode(); //ce qui donne : return 49 - 48 == 1

equivalent à :

return str2.at(0).unicode() < str1.at(0).unicode(); //ce qui donne : return 48 < 49 == true == 1 


Regardons la doc de std::sort vu que qSort est obsolète :

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Les 2 premiers paramètres concernent les limites (iterators de la liste) à comparer,
le 3ème est l' outil de comparaison. Il peut être sous la forme d'une fonction ou d'un objet (struct, class). Compare doit retourner un bool.
Attaquons nous à notre fonction Compare :

bool lessThan(QString const& str1, QString const& str2)
{
    QString const baseName1 = QFileInfo(str1).baseName();
    QString const baseName2 = QFileInfo(str2).baseName();
    int const maxSize = baseName1.size() > baseName2.size() ? baseName1.size() : baseName2.size();
    return baseName1.rightJustified(maxSize, '0') < baseName2.rightJustified(maxSize, '0');
}
 

Nous pouvons le faire sous forme de classe :

class LessThan {
public:
  bool operator() (QString const& str1, QString const& str2) 
  { 
    QString const baseName1 = QFileInfo(str1).baseName();
    QString const baseName2 = QFileInfo(str2).baseName();
    int const maxSize = baseName1.size() > baseName2.size() ? baseName1.size() : baseName2.size();
    return baseName1.rightJustified(maxSize, '0') < baseName2.rightJustified(maxSize, '0');
  }
};
 

Utilisation :
Les données de départ

    QString const str1 = "10.jpg";
    QString const str2 = "2.jpg";
    QStringList strList;
    strList << str1 << str2;

Dans le cas de la fonction lessThan :

    std::sort(strList.begin(), strList.end(), lessThan);
    qDebug() << strList; //affiche 2.jpg puis 10.jpg

Dans le cas de la class LessThan :

  LessThan lt;
  std::sort(strList.begin(), strList.end(), lt);
  qDebug() << strList; //affiche 2.jpg puis 10.jpg

Notez la simplicité et la puissance de ce genre d'algorithme : nous pouvons trier ce que nous voulons, n'importe quelle classe peut être triée sur n'importe quel membre.
Nous allons créer une classe Animal :

  class Animal {
public:
    Animal(int const& id) : m_id(id) {;}
 
    int id() const {return m_id;}
    bool operator <(Animal const& other) {
        return id() < other.id();
    }
 
private:
    int m_id;
};

Si nous voulons afficher notre classe Animal dans la fenêtre de sortie

QDebug operator<<(QDebug debug, const Animal &a)
{
    debug.nospace() << '(' << a.id() << ')';
    return debug;
}

Notre fonction de tri qui sera appelée par std::sort (utilisation avec pointeurs)

bool animalLessThanP(Animal* a1, Animal* a2)
{
    return *a1 < *a2;
}

Notre fonction de tri qui sera appelée par std::sort (utilisation sans pointeurs)

bool animalLessThan(Animal& a1, Animal& a2)
{
    return a1 < a2;
}

Utilisation :

  //avec pointeurs
    QList<Animal*> listAnimalsP;
    Animal* animal = new Animal(3);
    listAnimalsP << animal;
    animal = new Animal(5);
    listAnimalsP << animal;
    animal = new Animal(2);
    listAnimalsP << animal;
    qDebug() << listAnimalsP; //pour ma session, affiche : (0x1014cc0a0, 0x108017010, 0x1014c6200)
    std::sort(listAnimalsP.begin(), listAnimalsP.end(), animalLessThanP);
    qDebug() << listAnimalsP; //pour ma session, affiche : (0x1014c6200, 0x1014cc0a0, 0x108017010), le tri a fonctionné
 
  //sans pointeurs
    QList<Animal> listAnimals;
    Animal animal1(3);
    listAnimals << animal1;
    Animal animal2(5);
    listAnimals << animal2;
    Animal animal3(2);
    listAnimals << animal3;
    qDebug() << listAnimals; //affiche ((3), (5), (2))
    std::sort(listAnimals.begin(), listAnimals.end(), animalLessThan);
    qDebug() << listAnimals; //affiche ((2), (3), (5)), le tri a fonctionné

Allons plus loin

Toujours avec le même algorithme :


  • Avec les Q*Widget :

Un membre du forum voulait trier de la même manière une QListWidget, comment faire :
La doc de QListWidget::sortItems(Qt::SortOrder order = Qt::AscendingOrder) n'en parle pas,
donc remontons à la source :

void QListWidget::sortItems(Qt::SortOrder order)
{
    Q_D(QListWidget);
    d->sortOrder = order;
    d->listModel()->sort(0, order); //il faut remonter au model
}

le modèle :

void QListModel::sort(int column, Qt::SortOrder order)
{
    ...
 
    LessThan compare = (order == Qt::AscendingOrder ? &itemLessThan : &itemGreaterThan); //regardons la méthode itemLessThan
    std::sort(sorting.begin(), sorting.end(), compare);
 
    ...
}
bool QListModel::itemLessThan(const QPair<QListWidgetItem*,int> &left,
                              const QPair<QListWidgetItem*,int> &right)
{
    return (*left.first) < (*right.first); //nous y sommes : il s'agit ici de l'utilisation de virtual 
                                           //bool QListWidgetItem::operator<(const QListWidgetItem & other) const
}

Il ne nous reste plus qu'à surcharger cette méthode :

class MyListWidgetItem  : public QListWidgetItem {
public:
    MyListWidgetItem(QListWidget * parent = 0, int type = Type) : QListWidgetItem(parent, type) {;}
    MyListWidgetItem(const QString & text, QListWidget * parent = 0, int type = Type) : 
        QListWidgetItem(text, parent, type) {;}
    MyListWidgetItem(const QIcon & icon, const QString & text, QListWidget * parent = 0, int type = Type) : 
        QListWidgetItem(icon, text, parent, type) {;}
    MyListWidgetItem(const QListWidgetItem & other);
    bool operator<(const QListWidgetItem &other) const
    {
        int justifyCount = qMax(QFileInfo(text()).baseName().size(), QFileInfo(other.text()).baseName().size());
        return (QFileInfo(text()).baseName().rightJustified(justifyCount, '0') < 
            QFileInfo(other.text()).baseName().rightJustified(justifyCount, '0'));
 
    }
};

Utilisation :

    QStringList strList;
    strList << "10.jpg";
    strList << "2.jpg";
    MyListWidgetItem* it = nullptr;
    foreach(QString str, strList) {
        it = new MyListWidgetItem(str,ui->listWidget);
    }
    ui->listWidget->sortItems();

Bien sûr, cette même technique peut être étendue aux QTreeWidget, QTableWidget, à condition d'hériter QTreeWidgetItem et QTableWidgetItem.


  • Avec les Q*View :

Pour gagner un peu en généricité, plutôt s'orienter vers les MVC. Ainsi,

class MyItem  : public QStandardItem {
public:
    MyItem() : QStandardItem() {;}
    MyItem(const QString & text) : QStandardItem(text) {;}
    MyItem(const QIcon & icon, const QString & text) : QStandardItem(icon, text) {;}
    MyItem(int rows, int columns = 1) : QStandardItem(rows, columns) {;}
    bool operator<(const QStandardItem & other) const {
        int justifyCount = qMax(QFileInfo(text()).baseName().size(), QFileInfo(other.text()).baseName().size());
        return (QFileInfo(text()).baseName().rightJustified(justifyCount, '0') < 
            QFileInfo(other.text()).baseName().rightJustified(justifyCount, '0'));
    }
};

Utilisation :

  //on crée un model
  QStandardItemModel *model = new QStandardItemModel(strList.count(), 4);
  MyItem *item = nullptr;
  //on le remplit
  for (int row = 0; row < strList.count(); ++row) {
       for (int column = 0; column < 4; ++column) {
           if (column == 0)
               item = new MyItem(QString("%0").arg(strList.at(row)));
           else
               item = new MyItem(QString("Something else"));
           model->setItem(row, column, item);
        }
    }
    //on le trie
    model->sort(0);
    //on l'affiche dans la vue que l'on souhaite
    ui->listView->setModel(model);
    ui->tableView->setModel(model);
    ui->columnView->setModel(model);
    ui->treeView->setModel(model);

Conclusion

Nous n'avons sûrement pas vu toutes les utilisations d'un algorithme de tri, mais j'espère que cet article pourra aider.
Bien sûr, n'étant pas verrouillé, ce dernier pourra être complété avec d'autres cas d'utilisation.
A vous de jouer ;-)

babaOroms

implementation_d_un_algorithme_de_tri_personnalise.txt · Dernière modification: 2015/10/04 13:11 par gbdivers