Trier un TList sur un ou plusieurs critères

On connaît l'objet TStringList qui permet de stocker des chaînes de caractères. Si l'on veut trier la liste en ordre croissant, on utilise la méthode sort. Ça, c'est très simple. Mais si l'on veut créer une liste d'ensemble de données du style suivant (par exemple) :

type TPersonne = record
Nom: string[30];
Prenom: string[25];
Age: byte;
end;

… nous allons utiliser un TList. Un bon exemple valant mieux qu'un trop long discours théorique, voyons ce que nous pouvons faire.

Pour faciliter la manipulation des éléments du TList, nous allons dériver un nouvel objet que nous appellerons TListPersonnes.

TListPersonnes = class(TList)
public
procedure Reset;
procedure AddEnreg(Enregs: array of string); 
function GetItem(const i: Integer): TEnreg; 
end; 
PPersonne = ^TPersonne;

Pour le code de ces procédures, vous pourrez vous référer au code exemple téléchargeable ici.

Chaque record du type TPersonne sera stocké dans le TListPersonnes. Maintenant, pour des besoins d'affichage ou de recherches, on peut avoir besoin de trier notre liste de personnes sur le nom, le prénom, l'âge. Ou alors on peut vouloir utiliser un tri composé de plusieurs critères (nom, prénom, âge ou âge, prénom, nom, etc.). Pour réaliser cela, nous allons utiliser la fonction sort héritée de l'objet TList. La fonction sort utilise la méthode de tri QuickSort (une des plus rapides) à partir d'une fonction de comparaison (type TListSortCompare) qui doit être définie et écrite par le programmeur. Cette fonction sera passée comme paramètre à la fonction sort. Nous allons passer directement au tri multicritère. Une fois que nous aurons défini la méthode la plus compliquée, la plus simple découlera d'elle-même.

Le fichier d'aide Delphi donne la définition suivante de la fonction sort :

tiré du fichier d'aide de Borland

Trie la liste, en employant l'algorithme Tri Rapide (QuickSort) et en utilisant Compare comme fonction de comparaison.
type TListSortCompare = function (Item1, Item2: Pointer): Integer;
procedure Sort(Compare: TListSortCompare);
Description : la méthode Sort permet de trier les éléments du tableau Items. Compare est une fonction de comparaison indiquant comment les éléments sont ordonnés.
Compare renvoie < 0 si Item1 est inférieur à Item2, 0 s'ils sont égaux et > 0 si Item1 est supérieur à Item2.

Pour notre tri multicritère, nous allons définir un type ordonné reprenant les diverses « colonnes » de tri.

Type TChampsComparaison = (cdcNom, cdcPrenom, cdcAge);

À présent, nous allons créer un tableau qui contiendra les clés de tri dans l'ordre que nous aurons choisi.

var ClesTri: array[1..3] of TChampsComparaison;

Ce tableau va nous servir à définir l'ordre de tri des éléments de notre TListPersonnes. Voyons quelques exemples :

Tri nom, prénom, âge : 
ClesTri[1] := cdcNom;
ClesTri[2] := cdcPrenom;
ClesTri[3] := cdcAge;

Dans ce premier tri, on commencera par comparer les noms. Si pour les deux records traités au passage dans la procédure de comparaison, on a une égalité, on triera alors sur le second champ (Prénom) défini par l'ordre des clés de tri.

Tri âge, prénom, nom : 
ClesTri[1] := cdcAge;
ClesTri[2] := cdcPrenom;
ClesTri[3] := cdcNom;
etc.

À présent, écrivons notre fonction de comparaison de type TListSortCompare.

function CompareMulti(Item1, Item2: Pointer): Integer; 
var 
Entry1, Entry2: PPersonne; 
R, J: integer; 
ResComp: array[TChampsComparaison] of integer; 
begin 
.......
end;

Dans cette fonction, nous utiliserons deux variables du type PPersonne pour comparer les valeurs des enregistrements passés sous forme de pointeur. ResComp servira à stocker des résultats intermédiaires permettant de définir le résultat de l'appel de fonction à chaque passage.

Cette fonction devra définir l'ordre entre deux éléments du type PPersonne en fonction de l'ordre défini dans le tableau ClesTri. La méthode va donc consister à comparer chaque élément des enregistrements entre eux. C'est-à-dire
le champ Nom de Item1 avec le champ Nom de Item2,
le champ Prenom de Item1 avec le champ Prenom de Item2,
etc.

Les résultats de chaque comparaison sont stockés dans le tableau ResComp. En fin de fonction, on traite le tableau selon l'ordre défini afin d'obtenir la préséance des éléments. Voici maintenant le code complet de la fonction : (les fonctions StringCompare et NumericCompare sont définies dans le code exemple).

function CompareMulti(Item1, Item2: Pointer): Integer; 
var 
Entry1, Entry2: PPersonne; 
R, J: integer; 
ResComp: array[TChampsComparaison] of integer; 
begin 
Entry1 := Item1;
Entry2 := Item2;
{En affectant maintenant aux éléments du tableau ResComp les résultats des "sous"-fonctions de comparaison on va pouvoir déterminer un ordre de préséance en tenant compte de chaque élément de la structure}
ResComp[cdcNom] := stringCompare(Entry1.Nom, Entry2.Nom);
ResComp[cdcPrenom] := stringCompare(Entry1.Prenom, Entry2.Prenom);
ResComp[cdcAge] := NumericCompare(Entry1.Age, Entry2.Age);

{Le tableau ResComp (RessourcesSomparaisons) contient maintenant le résultat de la comparaison de chaque champ sur lequel on voulait faire le tri. }
R := 0;
for J := 1 to 3 do
if ResComp[ClesTri[J]] <> 0 then {On cherche la première différence pour arrêter la boucle}
begin
R := ResComp[ClesTri[J]];
break;
end;
result := R;
end;

La fonction TList.sort va passer autant de fois que nécessaire par cette fonction que nous venons de définir pour ordonner les éléments tel que nous le voulons. Ce code utilise les fonctions StringCompare et NumericCompare que j'ai écrites, mais vous pouvez bien sûr écrire une fonction pour chaque type de données que vous désirez (DateCompare par exemple).

Pour trier notre TListPersonnes définie dans notre code, nous appellerons simplement la fonction sort : Lst.Sort(CompareMulti);.
Et voilà, notre TListPersonnes est trié selon nos besoins.

Vous trouverez tous les détails du code dans le fichier exemple téléchargeable plus haut.

!

P.-S. Remerciements à Dinh Doan Van Bien de Strasbourg qui m'a inspiré cette technique et beaucoup appris sur Delphi et la programmation.