Les collections en Pascal

Le type TCollection de l'unité Objects

Roland Chastain

Le type TCollection est apparu avec la version 6 du compilateur Turbo Pascal. Il est défini dans l'unité Objects. On retrouve cette unité dans la bibliothèque des compilateurs Free Pascal et Virtual Pascal. Cet article est une étude du type TCollection et de ses descendants. Nous verrons à quoi peuvent servir les différents types de collections. Nous aborderons aussi en passant des notions plus générales, comme les pointeurs.

Commentez

- Titre : Les collections en Pascal

- Auteur : Roland Chastain

- Parution : 20 juin 2014

- Mise à jour : 11 février 2020

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2014 Roland Chastain. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Création d'une collection

- III. Itérateurs

- III-A. L'itérateur ForEach

- III-B. Les itérateurs FirstThat et LastThat

- IV. Le type TSortedCollection

- V. Le type TStringCollection

- VI. Collections polymorphiques

- VII. Conclusion

I - Introduction

Une collection est un objet contenant une liste de pointeurs et fournissant des méthodes pour la manipulation de cette liste. La collection a encore deux autres caractéristiques qui la distinguent d'un simple tableau : elle est dynamiquement dimensionnée et polymorphique.

Alors que la taille d'un tableau est fixée une fois pour toutes au moment de la compilation, la collection reçoit une dimension initiale, mais elle peut s'agrandir à l'exécution en fonction de la quantité de données à traiter.

Une autre limitation des tableaux, c'est que tous leurs éléments doivent être du même type, lequel doit être déterminé au moment de la compilation. La collection s'affranchit de cette limitation en utilisant des pointeurs non typés. La collection peut donc être constituée d'objets de différents types et de différentes tailles.

Autrement dit, vous pouvez mettre tout ce que vous voulez dans une collection ; ou, plus exactement, vous y mettez toujours des pointeurs, mais ces derniers peuvent pointer vers différents types d'objets. Par conséquent, lorsque vous récupérez un objet de la collection, le compilateur n'a aucun moyen de contrôler l'hypothèse que vous faites quant à la nature de cet objet : c'est à vous de savoir de quoi est constituée votre collection.

Vous pouvez même mettre dans une collection autre chose que des objets : tout ce qui pointe vers quelque chose est autorisé. Toutefois certaines méthodes du type TCollection sont conçues pour opérer exclusivement sur des objets dérivés du type TObject. C'est le cas des méthodes PutItem, GetItem et FreeItem. Vous pouvez, par exemple, constituer une collection de pointeurs de type PString ; mais dans ce cas vous devrez surcharger les méthodes mentionnées plus haut, pour les adapter à vos items. C'est précisément ce que fait, par exemple, le type TStringCollection.

Si vous avez besoin de voir ou de revoir les bases de la programmation orientée objet, vous pouvez consulter ce tutoriel : Introduction à la Programmation Orientée Objet.

II - Création d'une collection

Pour créer une collection, il faut définir le type de donnée que l'on souhaite collecter.

Supposons par exemple que vous vouliez gérer une liste de contacts, autrement dit une liste contenant des noms, des adresses et des numéros de téléphone. Voici la définition de votre type TContact :

uses
Objects;

type
PContact = ^TContact;
TContact = object(TObject)
nom, adr, tel: PString;
constructor Init(aNom, aAdr, aTel: string);
destructor Done; virtual;
procedure Print; virtual;
end;

Ensuite vous devez implémenter les méthodes Init et Done, qui alloueront et libéreront les données de chaque contact. Les champs de l'objet sont du type PString. Les fonctions NewStr et DisposeStr serviront à attribuer et à libérer la mémoire nécessaire.

constructor TContact.Init(aNom, aAdr, aTel: string);
begin
nom := NewStr(aNom);
adr := NewStr(aAdr);
tel := NewStr(aTel);
end;

destructor TContact.Done;
begin
DisposeStr(nom);
DisposeStr(adr);
DisposeStr(tel);
end;

La méthode TContact.Done sera automatiquement appelée pour chaque contact lorsque la collection sera détruite.

Il ne reste plus qu'à déclarer une collection et à y insérer vos contacts. La partie principale du programme ressemblera à ceci :

var
c: PCollection;

begin
c := New(PCollection, Init(10, 10));

c^.Insert(New(PContact, Init('Joachim Du Bellay', 'Lir'#130, '0000000000')));
c^.Insert(New(PContact, Init('Charles P'#130'guy', 'Orl'#130'ans', '0000000000')));
c^.Insert(New(PContact, Init('Charles Baudelaire', 'Paris', '0000000000')));

Affiche(c);

ChercheNom(c, 'Charles');
ChercheNom(c, 'Ronsard');

Dispose(c, Done);
end.

La première ligne du programme principal crée une collection d'une taille initiale de dix éléments. Si plus de dix contacts sont insérés dans la collection, la capacité de celle-ci sera augmentée de dix unités, autant de fois que nécessaire.

Les lignes suivantes créent des objets et les insèrent dans la collection.

Enfin, l'appel de la méthode Dispose libère la collection et les objets qu'elle contient.

Nulle part vous n'avez dit à la collection quel type d'objet elle devait collecter : vous lui avez simplement transmis des pointeurs.

III - Itérateurs

Insérer et supprimer des items, c'est fort bien, mais cela ne suffit pas. Nous voulons parcourir la collection, soit pour en afficher le contenu, soit pour effectuer sur celui-ci une certaine opération. Nous voulons aussi pouvoir retrouver un élément de la collection, en fonction de tel ou tel critère de recherche.

Pour effectuer ce genre de tâches, le type TCollection possède trois méthodes d'itération : ForEach, FirstThat et LastThat. Chacune de ces méthodes reçoit comme unique paramètre un pointeur vers une procédure ou vers une fonction.

III-A - L'itérateur ForEach

La méthode ForEach reçoit comme paramètre un pointeur vers une procédure. La procédure elle-même a un seul paramètre, qui est un pointeur vers un élément de la collection. ForEach appelle cette procédure pour chaque élément de la collection.

La procédure suivante est un exemple d'utilisation de ForEach :

procedure Affiche(c: PCollection);
procedure AfficheContact(p : PContact);
begin
with p^ do
WriteLn(
nom^,
'':20 - Length(nom^),
adr^,
'':20 - Length(adr^),
tel^
);
end;
begin
c^.ForEach(@AfficheContact);
end;

Mais comme nous avons déjà donné une méthode Print à notre objet TContact, c'est cette méthode que nous appellerons.

procedure PrintAll(C: PCollection);
procedure PrintContact(P : PContact);
begin
P^.Print;
end;
begin
C^.ForEach(@PrintContact);
end;

Pour chaque élément de la collection passée comme paramètre à PrintAll, la procédure nichée PrintContact sera exécutée.

Il est impératif que la procédure appelée par l'itérateur soit, comme dans l'exemple, une procédure au sens strict (et non pas une méthode de l'objet). Il est également impératif que ce soit une procédure locale, nichée dans la routine qui l'appelle. Enfin, cette procédure doit avoir comme unique argument un pointeur vers un élément de la collection.

III-B - Les itérateurs FirstThat et LastThat

En plus d'appliquer une certaine procédure à chaque élément de la collection, on a souvent besoin de trouver un élément de la collection répondant à un certain critère. C'est à cela que servent les itérateurs FirstThat et LastThat. Comme leur nom l'indique, ils parcourent la collection jusqu'à ce qu'ils rencontrent un élément répondant au critère de la fonction booléenne passée comme argument.

FirstThat et LastThat renvoient un pointeur vers le premier (ou le dernier) élément satisfaisant le critère de recherche.

procedure ChercheNom(c: PCollection; aNom: string);
function Trouve(p: PContact): boolean;
begin
Trouve := Pos(aNom, p^.nom^) > 0;
end;
var
p: PContact;
begin
p := c^.FirstThat(@Trouve);
if p = nil then
WriteLn('Aucun nom ne correspond '#133' la requ'#136'te : "', aNom, '"')
else
p^.Print;
end;

À nouveau, remarquez que la fonction Trouve est nichée dans la procédure qui l'appelle. Cette fonction retourne True si le nom recherché est contenu dans le champ nom de l'objet. Si aucun objet de la collection ne correspond au critère de recherche, un pointeur nil est retourné.

À retenir : ForEach appelle une procédure, tandis que FirstThat et LastThat appellent une fonction booléenne. Dans tous les cas, un pointeur vers un élément de la collection est passé à la procédure ou à la fonction.

Cet article est une adaptation du chapitre 7 du Guide Turbo Vision de Turbo Pascal 6.0. Le programme Contacts est une adaptation du programme TVGUID17.

Si vous souhaitez vous initier à la programmation Turbo Vision, vous pouvez consulter ce tutoriel : Introduction à Turbo Vision.

IV - Le type TSortedCollection

Parfois vous avez besoin que vos données soient rangées dans un certain ordre. Turbo Vision fournit un type spécial de collection qui vous permet de ranger les données d'une collection dans l'ordre que vous souhaitez : il s'agit du type TSortedCollection.

TSortedCollection est un descendant de TCollection. Chaque fois qu'un nouvel élément est ajouté, l'ensemble de la collection est vérifié et les doublons sont éliminés.

TSortedCollection est un type abstrait. Pour l'utiliser, vous devez décider quel type de données vous allez collecter, et définir deux méthodes correspondant à l'ordre dans lequel vous souhaitez que les données soient rangées. Pour ce faire, vous devrez dériver un nouveau type de collection du type TSortedCollection. Dans notre cas, ce sera le type TContactCollection.

Notre type TContactCollection sait déjà insérer de nouveaux objets dans la collection et aussi les supprimer. Il hérite ces fonctionnalités du type TCollection. Ce qu'il faut lui apprendre, c'est quel champ doit être utilisé comme clé de tri et quelle méthode de comparaison il devra employer pour déterminer l'ordre relatif de deux éléments. Cela se fera en surchargeant les méthodes KeyOf et Compare.

type
PContactCollection = ^TContactCollection;
TContactCollection = object(TSortedCollection)
function KeyOf(Item: Pointer): Pointer; virtual;
function Compare(Key1, Key2: Pointer): Integer; virtual;
end;

function TContactCollection.KeyOf(Item: Pointer): Pointer;
begin
KeyOf := PContact(Item)^.nom;
end;

function TContactCollection.Compare(Key1, Key2: Pointer): Integer;
begin
if PString(Key1)^ = PString(Key2)^ then
Compare := 0
else if PString(Key1)^ < PString(Key2)^ then
Compare := -1
else
Compare := 1;
end;

La méthode KeyOf détermine quel champ sera utilisé comme clé de tri. Dans notre exemple, c'est le champ nom du contact. Compare renvoie -1, 0 ou 1 suivant que Key1 est plus petit, égal ou plus grand que Key2. Dans notre exemple, il s'agit de l'ordre alphabétique.

Remarquez que, les clés retournées par KeyOf et passées à Compare étant des pointeurs non typés, il est nécessaire de les transtyper en PStrings avant de les déréférencer.

C'est tout ce que vous avez à faire. Maintenant vous déclarez votre liste de contacts comme une variable du type TContactCollection (en modifiant également l'appel à New), et vos contacts seront rangés dans l'ordre alphabétique.

var
c: PContactCollection;

begin
c := New(PContactCollection, Init(10, 10));

V - Le type TStringCollection

Le type TStringCollection permet de constituer des collections de chaînes triées. Notez que les éléments d'une collection du type TStringCollection ne sont pas des objets : ce sont des pointeurs vers des chaînes. Comme la collection de chaînes descend du type TSortedCollection, les chaînes en double ne sont pas conservées.

Utiliser une collection de chaînes est facile. Déclarez une variable pointeur de type PCollection, initialisez cette variable en choisissant sa taille initiale ainsi que la taille de ses augmentations successives :

var
s: string;
c: PCollection;

begin
c := New(PStringCollection, Init(10, 10));

La collection aura une taille initiale de dix unités et augmentera de dix en dix. Il n'y a plus qu'à y insérer des chaînes. Dans notre exemple, ces chaînes seront des « mots » extraits d'un fichier lu par le programme. Le programme s'intitule Lexique.

repeat
s := MotSuivant(f);
if s <> '' then
c^.Insert(NewStr(s));
until s = '';

Remarquez que l'on utilise la fonction NewStr pour faire une copie du mot qui a été lu et pour passer l'adresse de cette copie à la méthode Insert.

Pour finir, l'appel de la méthode Dispose aura pour effet de libérer tous les éléments de la collection.

Dispose(c, Done);

Nous ne répéterons pas ce que nous avons dit précédemment sur les méthodes d'itération, puisqu'il n'y a rien de nouveau à ajouter. Dans notre exemple, nous utilisons l'itérateur ForEach pour afficher tous les mots de la collection.

procedure Affiche(c: PCollection);
procedure AfficheMot(p: PString);
begin
WriteLn(p^);
end;
begin
c^.ForEach(@AfficheMot);
end;

VI - Collections polymorphiques

Il nous reste à parler de la principale spécificité des collections, à savoir leur caractère polymorphique, autrement dit la faculté qu'elles ont de contenir des objets de différents types.

Jusqu'ici nous avons vu des collections constituées d'objets du même type : le type TContact, puis le type chaîne. Mais les collections peuvent contenir n'importe quel type d'objet descendant de TObject et ces différents types peuvent être librement mêlés. Naturellement, un tel mélange n'aurait aucune utilité si ces différents objets n'avaient aucun point commun, autrement dit s'ils ne descendaient pas d'un même ancêtre, d'un même type abstrait.

Voici à titre d'exemple le programme Figures, qui crée une collection d'objets graphiques (point, cercle, rectangle) et utilise l'itérateur ForEach pour parcourir la collection, et en dessiner un à un tous les éléments (en fait, nous avons remplacé les opérations de dessin par de simples lignes affichées dans la console).

D'abord nous définissons un ancêtre abstrait :

type
P_Figure = ^T_Figure;
T_Figure = object(TObject)
x, y: integer;
constructor Init;
procedure Draw; virtual;
end;

Tous les objets dérivés de ce type abstrait auront la faculté d'être initialisés (par le constructeur Init) puis dessinés (par la méthode Draw).

À présent, définissons les types T_Point , T_Cercle et T_Rectangle.

P_Point = ^T_Point;
T_Point = object(T_Figure)
procedure Draw; virtual;
end;

P_Cercle = ^T_Cercle;
T_Cercle = object(T_Figure)
rayon: integer;
constructor Init;
procedure Draw; virtual;
end;

P_Rectangle = ^T_Rectangle;
T_Rectangle = object(T_Figure)
largeur, hauteur: integer;
constructor Init;
procedure Draw; virtual;
end;

Ces trois types d'objets héritent des propriétés x et y de leur ancêtre commun. L'objet T_Cercle a en outre un rayon, l'objet T_Rectangle une largeur et une hauteur.

Pour chaque type d'objet, les méthodes Init et Draw seront donc surchargées. Par exemple, pour le cercle :

constructor T_Cercle.Init;
begin
inherited Init;
rayon := 20 + Random(20);
end;

procedure T_Cercle.Draw;
begin
WriteLn(Format('%.3d, %.3d, %.3d', [x, y, rayon]));
end;

Voici le code qui construit la collection :

procedure ConstruitCollection(var c: PCollection);
var
i: integer;
p: P_Figure;
begin
c := New(PCollection, Init(10, 10));
for i := 0 to 20 do
begin
case i mod 3 of
0: p := New(P_Point, Init);
1: p := New(P_Cercle, Init);
2: p := New(P_Rectangle, Init);
end;
c^.Insert(p);
end;
end;

La collection sera donc constituée de vingt-et-un objets du genre T_Figure. Les uns seront des points, les autres des cercles ou des rectangles. Peu importe, puisque tous auront été initialisés comme il convient, et pourront être dessinés par un unique appel de la méthode Draw.

procedure Dessine(c: PCollection);
procedure DessineFigure(p : P_Figure);
begin
p^.Draw;
end;
begin
c^.ForEach(@DessineFigure);
end;

var
fig: PCollection;

begin
Randomize;
ConstruitCollection(fig);
Dessine(fig);
Dispose(fig, Done);
end.

Cette faculté qu'ont les collections de contenir des objets de différents types dérivant d'un ancêtre commun est l'un des atouts de la programmation orientée objet.

VII - Conclusion

On trouvera joints à cet article, outre ceux qui ont déjà été commentés, d'autres exemples d'utilisation des collections : les programmes Mélodie, Nettoyeur et Encodeur.

Le code du programme Mélodie a été tiré du jeu Music Vision de Bob Ferguson. On définit un objet note, dérivé de TObject, puis un objet mélodie, dérivé de TCollection. La mélodie est initialisée à partir d'un fichier passé en paramètre. L'exemple qui accompagne le programme est une transcription du Tambourin de Jean-Philippe Rameau.

Le programme Nettoyeur dresse une liste des fichiers contenus dans un répertoire donné. Lorsqu'il est de nouveau exécuté avec les mêmes paramètres, il détecte les nouveaux fichiers et les supprime. On a utilisé le type TStrCollection, qui est une collection de chaînes à zéro terminal.

Enfin, l'Encodeur remplace les caractères spéciaux d'un document HTML par les entités correspondantes. Des collections de chaînes sont utilisées pour manipuler des listes de propriétés et d'entités.

Les exemples accompagnant cet article ont été compilés avec Free Pascal (version 2.6.4) et avec Virtual Pascal (version 2.1).

Je remercie M.Dlb pour son assistance technique et jacques_jean pour sa relecture minutieuse.