Mini-projet n°5 : Tableaux Associatifs

Enoncé

Certains langages de programmation comme PHP proposent un type de données particulièrement intéressant qui n'a aucun équivalent en Pascal Objet. Ce genre de tableau utilise en fait n'importe quel indice pour contenir n'importe quelle donnée. Ainsi, on peut trouver dans un tableau associatif une chaîne indexée par un entier et un enregistrement indexé par une chaîne. La taille de ce type de tableau est en outre variable, et dépend des éléments ajoutés et retirés du tableau associatif.

Ce mini-projet consiste à réaliser une classe permettant l'utilisation d'un tableau associatif simple indexé uniquement par des chaînes de caractères et dont chaque élément est également une chaîne de caractères. Pour ce qui est du stockage d'un nombre quelconque d'éléments, vous avez le droit d'utiliser la classe "TList" qui permet de sauvegarder un nombre variable de pointeurs. L'accès aux éléments du tableau associatif doit se faire via une propriété tableau par défaut, pour un maximum de simplicité. Ainsi, les instructions suivantes, où "TA" est un tableau associatif, se doivent de fonctionner :

TA['prénom'] := 'Jacques';
TA['nom'] := 'Dupont';
TA['age'] := '53';
ShowMessage(TA['prénom'] + ' ' + TA['nom'] + ' a ' + TA['age'] + ' ans.');

Etapes de progression
  1. Comme dans tout projet donnant lieu à la création de classes, commencez par réfléchir : quels sont vos objectifs, vos contraintes en termes de programmation, en termes de connaissances ? Quelle est votre marge de manoeuvre ?

  2. Créez un projet vierge et une unité sans fiche. Dans cette dernière, déclarez la classe "TableauAsssociatif" avec deux sections privées et publiques.

  3. Documentez-vous un peu sur TList : regardez l'aide de Delphi sur "TList", sur son constructeur (Create), son destructeur (Destroy), les méthodes "add", "remove" et "pack".

  4. Déclarez un champ (privé) de classe TList. Surchargez le constructeur et le destructeur pour créer et détruire cet objet à la volée.

  5. Un élément sera stocké sous la forme d'un pointeur vers un enregistrement. Déclarez donc un enregistrement et le type pointeur correspondant. L'enregistrement doit contenir deux chaînes : "cle" et "valeur".

  6. Commencez par coder les méthodes les plus simples, celles ne nécessitant pas trop de recherche. Ainsi, il est impératif de pouvoir connaître la taille d'un tableau associatif (son nombre d'éléments). Créez donc une propriété "Count" en lecture seule. Utilisez en lecture une méthode faisant appel à la méthode de même nom de l'instance de "TList".

  7. Les méthodes suivantes sont plus complexes, puisqu'à une clé ne peut correspondre qu'une seule valeur. Il va nous falloir un moyen de savoir si une clé donnée existe déjà dans le tableau. Créez pour cela une méthode privée acceptant une chaîne en paramètre ("cle") et retournant un pointeur vers un élément du type enregistrement créé auparavant. Cette méthode recherchera dans la liste un élément comportant comme clé la chaîne transmise. Si cet élément est trouvé, il est retourné comme résultat. Dans le cas contraire, la méthode retournera nil.

  8. Créez maintenant une méthode d'ajout d'élément à deux paramètres de type chaîne ("cle" et "valeur"). Cette méthode recherche d'abord dans la liste fElems si la clé existe déjà (utilisez la méthode créée juste avant). Dans l'affirmative, sa valeur associée est remplacée par la "valeur" transmise. Dans la négative, un nouvel élément est créé et placé dans la liste interne "fElems".

  9. Le programmeur doit avoir un moyen simple d'accèder à la valeur associée à une clé. Créez donc une méthode obtenirValeur qui à partir d'un paramètre "cle" de type chaîne fourni un résultat de type chaîne. Si la clé existe, la valeur est retournée, sinon on prend comme convention la chaîne vide.

  10. A l'aide des deux méthodes d'ajout (AjoutElement) et de recherche de valeur (obtenirValeur), vous pouvez maintenant déclarer une propriété tableau de type chaîne indexée par une chaîne (l'aviez-vous vue venir ? Si oui bravo, si non remarquez l'ordre dans lequel nous avons procédé : les deux méthodes puis la propriété). Les deux accesseurs sont évidemment les deux méthodes citées précédemment.

  11. Il manque encore la possibilité de supprimer une entrée en spécifiant sa clé. Créez donc une méthode publique "retirerElement" prenant un paramètre chaîne et tentant de retirer l'élément comportant cette chaîne comme clé. Aucune erreur ne sera signalée en cas d'absence de l'élément dans le tableau. Vous pouvez utiliser la méthode "extract" de la classe "TList" pour vous aider.

  12. Il manque une dernière chose pour que la classe soit acceptable : la libération de la mémoire associée aux pointeurs non retirés du tableau lors de sa destruction. En effet, cette mémoire n'est pour l'instant libérée nulle part. Le meilleur endroit pour réaliser cela est lors de la destruction, donc lors de l'appel au destructeur "Destroy". Complètez donc le destructeur surchargé en y incorporant la libération de mémoire.

  13. La toute dernière étape consiste à vérifier que l'extrait de code fourni fonctionne.
Solution pas à pas

la classe que nous créons ici va servir de "boite noire" permettant de créer un tableau associatif restreint. L'intérêt de créer une classe est qu'on pourra en déclarer autant d'instance que nous voulons. Ces instances seront indépendantes les unes des autres. Le fait d'avoir des éléments publics et privée ainsi qu'une propriété tableau par défaut donne à la fois accès uniquement aux membres importants de la classe et facilite leur accès.

Cette solution pas à pas reprend les intitulés précédent en les complétant autant que possible pour donner tout le cheminement qui amène à la résolution complète du mini-projet :

  1. Comme dans tout projet donnant lieu à la création de classes, commencez par réfléchir : quels sont vos objectifs, vos contraintes en termes de programmation, en termes de connaissances ? Quelle est votre marge de manoeuvre ?

    L'objectif (mais pas forcément sa réalisation, ce qui n'a rien à voir) est ici très simple : créer une classe implémentant des fonctionnalités. Les contraintes de programmation sont nombreuses : programmer sous Delphi, en utilisant la programmation objet, utiliser une propriété tableau par défaut, utiliser la classe "TList" (sachez lire entre les lignes : ce qui est "possible" est la plupart du temps conseillé et ici un impératif. Vous devrez sans cela réaliser vous-même un TAD liste permettant de stocker les éléments du tableau). Les contraintes en termes de connaissances sont ici le nerf de la guerre car c'est justement pour acquérir des connaissances que vous réalisez ce mini-projet. Vous devrez donc porter toute votre attention sur l'utilisation scrupuleuse des notions concernant la programmation objet. L'utilisation de la classe "TList" est un passage presque incontournable, mais pas l'essentiel : gardez en tête que l'utilisation des objets a été vue dans un chapitre antérieur.

  2. Créez un projet vierge et une unité sans fiche. Dans cette dernière, déclarez la classe "TableauAsssociatif" avec deux sections privées et publiques.

    Il s'agit ici de créer la base de travail sous Delphi. Le projet vous servira à tester directement la classe à créer, et l'unité vierge permet d'écrire du code indépendant de toute fiche, ce qui est impératif puisque nous devons créer une classe et non une application. Voici le code source de l'unité destinée à contenir la classe terminée :

    unit tabassoc;

    interface

    type
      TableauAssociatif = class
      private

      public

      end;

    implementation

    end.

  3. Documentez-vous un peu sur TList : regardez l'aide de Delphi sur "TList", sur son constructeur (Create), son destructeur (Destroy), les méthodes "add", "remove" et "pack".

    Si ca n'a pas été fait auparavant (et c'est une erreur fréquente de débutant que de se lancer dans l'aventure sans emmener sa bible, à savoir la documentation de Delphi), il est impératif de regarder comment fonctionne la classe "TList". Elle manipuile des pointeurs génériques (Pointer), ce qui va nous donner l'occasion de quelques transtypages. On ajoute un élément via la méthode "Add", on en retire via "Remove". Il est précisé dans l'aide de Delphi que ces deux méthodes ne gèrent pas la méthode associée aux pointeurs : ce sera à vous de le faire.

  4. Déclarez un champ (privé) de classe TList. Surchargez le constructeur et le destructeur pour créer et détruire cet objet à la volée.

    Comme le tableau associatif va stocker ses éléments dans un objet de classe TList, et qu'on ne peut pas utiliser de variable globale ou locale (où pourrions-nous les placer ???), il reste le choix idéal du champ. Ainsi, chaque objet de classe "TableauAssociatif" aura sa propre instance de la classe "TList" dans laquelle les éléments du tableau seront stockés. Voici la déclaration des trois nouveaux membres de "TableauAssociatif" :

      TableauAssociatif = class
      private
        fElems: TList;
      public
        constructor Create; virtual;
        destructor Destroy; override;
      end;

    et voici le code source du constructeur et du destructeur. Notez l'emploi de "Free" :

    constructor TableauAssociatif.Create;
    begin
      fElems := TList.Create;
    end;

    destructor TableauAssociatif.Destroy;
    begin
      fElems.Free;
      inherited;
    end;

  5. Un élément sera stocké sous la forme d'un pointeur vers un enregistrement. Déclarez donc un enregistrement et le type pointeur correspondant. L'enregistrement doit contenir deux chaînes : "cle" et "valeur".

    Rien de compliqué ici. Le type enregistrement et son pointeur associé vont être les éléments stockés dans l'instance de "TList". C'est une chose à faire avant de commencer à coder les différentes méthodes d'ajout, de retrait, de recherche... Placez simplement les deux déclarations de type avant la déclaration de la classe :

    type
      TElementTableauAssociatif = record
        Cle: string;
        Valeur: string;
      end;
      PElementTableauAssociatif = ^TElementTableauAssociatif;

  6. Commencez par coder les méthodes les plus simples, celles ne nécessitant pas trop de recherche. Ainsi, il est impératif de pouvoir connaître la taille d'un tableau associatif (son nombre d'éléments). Créez donc une propriété "Count" en lecture seule. Utilisez en lecture une méthode faisant appel à la méthode de même nom de l'instance de "TList".

    Il s'agit ici d'une mise en bouche. Voici la déclaration de cette propriété très simple :

        property Count: integer
          read getCount;

    déclarez la méthode "getCount" comme suit :

        ....
        fElems: TList;
        function getCount: integer;
      public
      ...

    Voici le code source de cette méthode :

    function TableauAssociatif.getCount: integer;
    begin
      Result := fElems.Count;
    end;

  7. Les méthodes suivantes sont plus complexes, puisqu'à une clé ne peut correspondre qu'une seule valeur. Il va nous falloir un moyen de savoir si une clé donnée existe déjà dans le tableau. Créez pour cela une méthode privée acceptant une chaîne en paramètre ("cle") et retournant un pointeur vers un élément du type enregistrement créé auparavant. Cette méthode recherchera dans la liste un élément comportant comme clé la chaîne transmise. Si cet élément est trouvé, il est retourné comme résultat. Dans le cas contraire, la méthode retournera nil.

    Cette méthode va nous rendre beaucoup de services puisque c'est elle qui permettra d'atteindre des éléments déjà placés dans le tableau (mais en interne uniquement : le programmeur utilisant la classe terminée ne devra pas avoir connaissance de cette méthode). Il s'agit ici d'un bête parcours de la liste, avec à chaque fois un transtypage de pointeur puis une comparaison de chaîne. Voici le code source ; étudiez-le à fond :

    function TableauAssociatif.rechercheElem(Cle: string): PElementTableauAssociatif;
    var
      indx: integer;
    begin
      indx := 0;
      Result := nil;
      { recherche jusqu'à ce que Result soit modifié (clé trouvée) ou qu'il n'y ait plus aucun
        élément à trouver. Remarquez le choix du while bien préférable à un for. }

      while (indx < fElems.Count) and (Result = nil) do
        begin
          { remarquez que Items est une propriété tableau par défaut et que l'on
            pourrait écrire fElems[indx] à la place de fElems.Items[indx].
            Remarquez le transtypae et la comparaison dans la foulée... }

          if PElementTableauAssociatif(fElems.Items[indx])^.Cle = Cle then
            // ici, on exploite le coté "par défaut" de Items
            Result := fElems[indx];
          inc(indx);
        end;
    end;

    N'oubliez pas de déclarer cette méthode dans la section privée de la classe.

  8. Créez maintenant une méthode d'ajout d'élément à deux paramètres de type chaîne ("cle" et "valeur"). Cette méthode recherche d'abord dans la liste fElems si la clé existe déjà (utilisez la méthode créée juste avant). Dans l'affirmative, sa valeur associée est remplacée par la "valeur" transmise. Dans la négative, un nouvel élément est créé et placé dans la liste interne "fElems".

    On rentre ici dans le vif du sujet. Voici la déclaration de la méthode, qui doit être privée (nous verrons plus tard pourquoi) :

        ...
        function rechercheElem(Cle: string): PElementTableauAssociatif;
        procedure AjoutElement(Cle: string; Valeur: string);
      public
      ...

    La méthode marche en deux temps : le premier recherche une entrée correspondante à la clé. Si cette entrée existe, la valeur est simplement mise à jour dans un second temps. Sinon, on doit réaliser un ajout complet. Voici le code source :

    procedure TableauAssociatif.AjoutElement(Cle, Valeur: string);
    var
      Elem: PElementTableauAssociatif;
    begin
      // recherche d'une entrée comportant la clé transmise
      Elem := rechercheElem(Cle);
      // si l'entrée existe
      if Elem <> nil then
        { mise à jour de la valeur (l'entrée sera toujours référencée dans la liste,
          il n'y a donc rien de plus à faire au niveau du pointeur puisque ce n'est
          pas lui qui change mais une des valeurs pointées. }

        Elem^.Valeur := Valeur
      else
        begin
          { Création d'un nouvel élément }
          new(Elem);
          Elem^.Cle := Cle;
          Elem^.Valeur := Valeur;
          { ajout d'une entrée dans la liste des pointeurs. Notez le transtypage implicite
            de Elem en type Pointer. Notez également qu'on ne DOIT PAS appeler Dispose
            sur Elem ici : ce sera fait lorsque l'élément sera plus tard retiré. }

          fElems.Add(Elem);
        end;
    end;

  9. Le programmeur doit avoir un moyen simple d'accèder à la valeur associée à une clé. Créez donc une méthode obtenirValeur qui à partir d'un paramètre "cle" de type chaîne fourni un résultat de type chaîne. Si la clé existe, la valeur est retournée, sinon on prend comme convention la chaîne vide.

    Cette méthode est très simple : elle fait appel à la recherche d'un élément avec la clé transmise. Si l'élément est trouvé, sa partie valeur est retournée, sinon, c'est une chaîne vide. Voici le code source :

    function TableauAssociatif.obtenirValeur(Cle: string): string;
    var
      Elem: PElementTableauAssociatif;
    begin
      // recherche d'une entrée comportant la clé transmise
      Elem := rechercheElem(Cle);
      if Elem <> nil then
        Result := Elem^.Valeur
      else
        Result := '';
    end;

    N'oubliez pas encore une fois de déclarer cette méthode dans la section privée de la classe.
  10. A l'aide des deux méthodes d'ajout (AjoutElement) et de recherche de valeur (obtenirValeur), vous pouvez maintenant déclarer une propriété tableau de type chaîne indexée par une chaîne (l'aviez-vous vue venir ? Si oui bravo, si non remarquez l'ordre dans lequel nous avons procédé : les deux méthodes puis la propriété). Les deux accesseurs sont évidemment les deux méthodes citées précédemment.

    Nous avons créé auparavant exactement ce qu'il faut pour faire fonctionner une propriété tableau de type chaîne indexée par une chaîne. En effet, nous avons, pour la lecture, une fonction à un seul paramètre chaîne qui retourne une chaîne, et pour l'écriture une procédure à deux paramètres de type chaîne. Reste à deviner la fonction de la propriété : c'est tout simplement une propriété "Valeur" (som nom est sans importance) auquel on accède en donnant une chaîne servant de clé entre crochets. Le nom est bien sans importance puisque la propriété va être déclarée "par défaut". Voici la déclaration preprement dite (il n'y a besoin d'aucun code source supplémentaire !) :

        ...
        property Count: integer
          read getCount;
        property Valeur[cle: string]: string
          read obtenirValeur
          write AjoutElement; default;
      end;
      ...

  11. Il manque encore la possibilité de supprimer une entrée en spécifiant sa clé. Créez donc une méthode publique "retirerElement" prenant un paramètre chaîne et tentant de retirer l'élément comportant cette chaîne comme clé. Aucune erreur ne sera signalée en cas d'absence de l'élément dans le tableau. Vous pouvez utiliser la méthode "extract" de la classe "TList" pour vous aider.

    Pouvoir ajouter des éléments de manière transparente est bien joli, mais il peut être intéressant d'en retirer de manière explicite cette fois. Cette méthode le fera, sans toutefois râler si la clé transmise n'est pas présente dans le tableau. La méthode extract de TList permet d'extraire sans douleur un pointeur d'une liste, il faut donc connaître la valeur du pointeur avant l'appel de cette méthode, et libèrer la mémoire associée à ce pointeur après l'appel, car l'élemnt doit être supprimé. Voici le code source :

    procedure TableauAssociatif.RetirerElement(Cle: string);
    var
      Elem: PElementTableauAssociatif;
    begin
      // recherche d'une entrée comportant la clé transmise
      Elem := rechercheElem(Cle);
      if Elem <> nil then
        begin
          fElems.Extract(Elem);
          Dispose(Elem);
        end;
    end;

  12. Il manque une dernière chose pour que la classe soit acceptable : la libération de la mémoire associée aux pointeurs non retirés du tableau lors de sa destruction. En effet, cette mémoire n'est pour l'instant libérée nulle part. Le meilleur endroit pour réaliser cela est lors de la destruction, donc lors de l'appel au destructeur "Destroy". Complètez donc le destructeur surchargé en y incorporant la libération de mémoire.

    La libération en elle-même se fait facilement puisqu'il suffit d'un parcours de la liste et d'un "Dispose" sur chaque pointeur transtypé au préalable (appeler dispose sur un pointeur de type Pointer n'a aucun sens).

    destructor TableauAssociatif.Destroy;
    var
      indx: integer;
    begin
      for indx := 0 to fElems.Count - 1 do
        Dispose(PElementTableauAssociatif(fElems[indx]));
      fElems.Free;
      inherited;
    end;
  13. La toute dernière étape consiste à vérifier que l'extrait de code fourni fonctionne.

    Pour cela, placez un simple bouton sur l'unique fiche de l'application. Utilisez le code ci-dessous, qui reprend le code fourni, pour complèter la méthode de réponse au clic sur le bouton :

    procedure TForm1.Button1Click(Sender: TObject);
    var
      TA: TableauAssociatif;
    begin
      TA := TableauAssociatif.Create;
      TA['prénom'] := 'Jacques';
      TA['nom'] := 'Dupont';
      TA['age'] := '53';
      ShowMessage(TA['prénom'] + ' ' + TA['nom'] + ' a ' + TA['age'] + ' ans.');
      TA.Destroy;
    end;

    Le résultat obtenu lors d'un clic confirme le bon fonctionnement du tableau :



    Libre à vous de créer un exemple plus complet, ou d'utiliser cette classe dans vos projets. Ce mini-projet est maintenant terminé.
Téléchargement

Code source du projet : 05_tableaux_associatifs.zip


© Copyright 2000 par Frédéric BEAULIEU. Tous droits de reproduction réservés.