Les collections en Pascal

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.

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.

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▲

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;

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

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

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;

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));

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;

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.

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.