Developpez.com

Plus de 2 000 forums
et jusqu'à 5 000 nouveaux messages par jour

Les génériques avec Delphi 2009 Win32

Avec en bonus les routines anonymes et les références de routine


précédentsommairesuivant

III. Conception d'une classe générique

Maintenant que nous savons comment on utilise des classes génériques au quotidien, il est temps de voir comment fonctionne une classe générique à l'intérieur.

Pour cela, nous allons développer une classe TTreeNode<T>, qui sera une implémentation générique d'un arbre. Cette fois, il ne s'agit plus du tout d'un cas d'école. C'est une véritable classe que vous pourrez utiliser dans vos projets réels.

III-A. Déclaration de la classe

Commençons par le commencement : la déclaration de la classe. Comme vous avez pu l'apercevoir dans l'extrait de la déclaration de TList<T>, on indique un paramètre générique (traditionnellement T lorsqu'il n'a pas de signification précise) en chevrons. On va donc avoir :

 
Sélectionnez

unit Generics.Trees;

type
  TTreeNode<T> = class(TObject)
  end;
				

Un noeud d'un arbre sera étiqueté d'une valeur de type T, et aura de 0 à plusieurs enfants. Lorsqu'il est détruit, un noeud libère tous ses enfants.

Quand on dit une valeur de type T, eh bien, c'est simple, on déclare FValue: T; de la même manière qu'avec n'importe quel type normal. Pour garder la liste des enfants, on utilisera une TObjectList<U>, déclarée dans Generics.Collections. J'ai volontairement utilisé U ici, car il ne faut pas confondre. En fait, U sera TTreeNode<T> ! Eh oui, on peut utiliser comme paramètre générique réel une classe générique.

Nous n'implémentons pas ici un arbre de recherche ou de tri. En conséquence, nous n'avons pas besoin d'un comparateur comme TList<T>.

En ce qui concerne les champs, cela va donc donner ceci :

 
Sélectionnez

type
  TTreeNode<T> = class(TObject)
  private
    FParent: TTreeNode<T>;
    FChildren: TObjectList<TTreeNode<T>>;
    FValue: T;
  end;
				

Étrange ? Si on y réfléchit bien, pas tant que ça. On a dit plus haut qu'un type générique pouvait être remplacé par n'importe quel type. Donc pourquoi pas un type classe générique ?

J'attire votre attention sur le fait que, dans le nom TTreeNode<T>, T est un paramètre générique non réel (formel, si vous préférez). Tandis qu'au sein de la classe, il devient un type réel ! C'est exactement comme les paramètres d'une routine. Dans la signature de la routine, ce sont des paramètres formels ; mais une fois dans le corps de la routine, ce sont des variable locales comme les autres. C'est pourquoi on peut utiliser T comme type de FValue, ou même comme type réel servant à paramétriser TTreeNode<T> dans la déclaration de FChildren.

Lorsque j'ai dit qu'on pouvait utiliser n'importe quel type comme paramètre réel, je vous ai mentis. Ce n'est pas toujours vrai. Par exemple, dans TObjectList<T>, T doit être un type classe. C'est parce que TObjectList<T> a posé une contrainte sur son paramètre de type. Nous verrons cela plus en détails dans un autre chapitre, mais je me dois de vous le signaler ici, puisque nous utilisons cette classe. Nous l'utilisons car nous voulons bénéficier de la libération automatique des objets contenus offerte par TObjectList<T>, ce que ne fait pas TList<T>.

Comme méthodes, outre les constructeur et destructeur, nous proposerons des méthodes de parcours en profondeur (préfixe et suffixe), ainsi que des méthodes d'ajout/déplacement/suppression de noeud. En fait, l'ajout sera demandé par l'enfant lui-même, lorsqu'on lui donnera un parent.

Pour les parcours, nous aurons besoin d'un type de call-back. Nous allons utiliser un type référence de routine. Et nous ferons deux versions de chaque parcours : un parcours sur les noeuds, et un parcours sur les valeurs des noeuds. Le second sera le plus souvent employé lors de l'utilisation de la classe TTreeNode<T>. Le premier est là pour permettre d'être plus général, et sera utilisé par plusieurs méthodes de TTreeNode<T> (notamment la seconde version du parcours).

Enfin, il y aura bien sûr des propriétés permettant d'accéder au parent, aux enfants et à la valeur étiquettée. Ce qui donne ceci. Vous pouvez voir qu'il n'y a rien de très nouveau, en dehors du fait qu'il y a plein de T partout.

Voici la déclaration complète de la classe - que, rassurez-vous, je vous donne après l'avoir complètement implémentée ^^.

 
Sélectionnez

type
  /// Référence à une routine de call-back avec un paramètre
  TValueCallBack<T> = reference to procedure(const Value: T);

  {*
    Structure arborescente générique
  *}
  TTreeNode<T> = class(TObject)
  private
    FParent: TTreeNode<T>;                /// Noeud parent (nil si racine)
    FChildren: TObjectList<TTreeNode<T>>; /// Liste des enfants
    FValue: T;                            /// Valeur étiquettée

    FDestroying: Boolean; /// Indique si est en train d'être détruit

    procedure DoAncestorChanged;

    function GetRootNode: TTreeNode<T>;
    function GetChildCount: Integer; inline;
    function GetChildren(Index: Integer): TTreeNode<T>; inline;
    function GetIndexAsChild: Integer; inline;

    function GetIsRoot: Boolean; inline;
    function GetIsLeaf: Boolean; inline;
    function GetDepth: Integer;
  protected
    procedure AncestorChanged; virtual;
    procedure Destroying; virtual;

    procedure AddChild(Index: Integer; Child: TTreeNode<T>); virtual;
    procedure RemoveChild(Child: TTreeNode<T>); virtual;

    procedure SetValue(const AValue: T); virtual;

    property IsDestroying: Boolean read FDestroying;
  public
    constructor Create(AParent: TTreeNode<T>; const AValue: T); overload;
    constructor Create(AParent: TTreeNode<T>); overload;
    constructor Create(const AValue: T); overload;
    constructor Create; overload;
    destructor Destroy; override;

    procedure AfterConstruction; override;
    procedure BeforeDestruction; override;

    procedure MoveTo(NewParent: TTreeNode<T>; Index: Integer = -1); overload;
    procedure MoveTo(Index: Integer); overload;

    function IndexOf(Child: TTreeNode<T>): Integer; inline;

    procedure PreOrderWalk(
      const Action: TValueCallBack<TTreeNode<T>>); overload;
    procedure PreOrderWalk(const Action: TValueCallBack<T>); overload;

    procedure PostOrderWalk(
      const Action: TValueCallBack<TTreeNode<T>>); overload;
    procedure PostOrderWalk(const Action: TValueCallBack<T>); overload;

    property Parent: TTreeNode<T> read FParent;
    property RootNode: TTreeNode<T> read GetRootNode;
    property ChildCount: Integer read GetChildCount;
    property Children[Index: Integer]: TTreeNode<T> read GetChildren;
    property IndexAsChild: Integer read GetIndexAsChild;

    property IsRoot: Boolean read GetIsRoot;
    property IsLeaf: Boolean read GetIsLeaf;

    property Value: T read FValue write SetValue;
  end;
				

Identifions ce qu'il y a encore de remarquable ici. En fait, pas grand chose. Si ce n'est qu'à chaque fois qu'un paramètre est de type T, il est déclaré const. En effet, nous ne savons pas à l'avance ce que pourra bien être T en vrai. Et il y a donc des possibilités pour que ce soit un type "lourd" (comme une string ou un record), pour lequel il est plus efficace d'utiliser const. Et comme const n'est jamais pénalisant (il est sans effet sur les types "légers", comme Integer), on le met toujours lorsqu'on travaille avec des types génériques.

La notion de type lourd ou léger est une notion qui m'est propre, et en rien officielle, doù les guillemets. J'entends par type lourd un type dont les paramètres gagnent (en rapidité d'exécution) à être passés comme const lorsque c'est possible. Il s'agit, de manière générale, des types qui s'étendent sur plus de 4 octets (hors flottants et Int64), et ceux qui nécessitent une initialisation. En (très) gros, on retiendra les chaînes, les record, les tableaux, interfaces (pas classes) et Variant.

En revanche, lorsqu'un paramètre est de type TTreeNode<T>, on ne met pas const. En effet, quel que sera T, TTreeNode<T> restera un type classe, qui est un type léger.

III-B. Implémentation d'une méthode

Pour montrer les particularités de l'implémentation d'une méthode de classe générique, travaillons sur GetRootNode, qui est très simple. Elle s'écrit comme suit :

 
Sélectionnez

{*
  Noeud racine de l'arbre
  @return Noeud racine de l'arbre
*}
function TTreeNode<T>.GetRootNode: TTreeNode<T>;
begin
  if IsRoot then
    Result := Self
  else
    Result := Parent.RootNode;
end;
				

La seule chose à prendre en considération ici est que, à chaque implémentation d'une méthode d'une classe générique, il faut respécifier le <T> à côté du nom de la classe. En effet, c'est nécessaire car TTreeNode pourrait très bien exister par ailleurs, et identifie donc un autre identificateur.

III-C. La pseudo-routine Default

Pour implémenter les deux constructeurs qui n'ont pas de paramètre AValue, il faudra initialiser FValue avec une valeur. Oui mais, comme on ne connaît pas le type de la valeur, comment écrire une valeur par défaut, et ce pour tous les types possibles ?

La solution est dans la nouvelle pseudo-routine Default. Tout comme TypeInfo, celle-ci prend en paramètre un identificateur de type. Et le nom d'un type générique est bien un identificateur de type.

Cette pseudo-routine "renvoie" la valeur par défaut du type demandé. On peut donc écrire :

 
Sélectionnez

{*
  Crée un noeud avec un parent mais sans valeur étiquetée
  @param AParent   Parent
*}
constructor TTreeNode<T>.Create(AParent: TTreeNode<T>);
begin
  Create(AParent, Default(T));
end;

{*
  Crée un noeud sans parent ni valeur étiquetée
*}
constructor TTreeNode<T>.Create;
begin
  Create(nil, Default(T));
end;
				

Dans le cas de l'initialisation d'un champ d'objet, ce n'est pas à proprement parler nécessaire. Car l'instanciation d'un objet initialise déjà tous ses champs à leur valeur par défaut. Mais je n'ai pas trouvé de meilleur endroit pour vous introduire à cette pseudo-routine.

III-D. Les références de routine avec les parcours d'arbre

Afin d'illustrer l'utilisation des références de routine de l'autre côté du mirroir, voici un commentaire sur l'implémentation des parcours d'arbre.

Chacune des deux surcharges du parcours prend en paramètre une référence de routine de rappel (communément appelée routine de call-back). Remarquez que, ici aussi, on a utilisé un paramètre const. En effet, le lecteur attentif se souviendra que les références de routine sont des interfaces, en réalité. Or une interface est un type lourd. Il faut donc utiliser const quand c'est possible.

Mise à part cette petite considération, il n'y a rien de spécial à dire sur la version parcours sur les noeuds, que voici :

 
Sélectionnez

{*
  Parcours préfixe sur les noeuds de l'arbre
  @param Action   Action à effectuer pour chaque noeud
*}
procedure TTreeNode<T>.PreOrderWalk(const Action: TValueCallBack<TTreeNode<T>>);
var
  Index: Integer;
begin
  Action(Self);
  for Index := 0 to ChildCount-1 do
    Children[Index].PreOrderWalk(Action);
end;
				

Pour appeler le call-back, on écrit exactement la même chose qu'avec un type procédural, à savoir la même forme qu'un appel de routine, mais avec la variable de type référence de routine en lieu et place du nom de la routine.

Pour implémenter la seconde version, on se sert de la première, en transmettant au paramètre Action... Une routine anonyme !

 
Sélectionnez

{*
  Parcours préfixe sur les valeurs des noeuds de l'arbre
  @param Action   Action à effectuer pour chaque valeur
*}
procedure TTreeNode<T>.PreOrderWalk(const Action: TValueCallBack<T>);
begin
  PreOrderWalk(
    procedure(const Node: TTreeNode<T>)
    begin
      Action(Node.Value);
    end);
end;
				

C'est quand même élégant comme style de programmation, non ?

Vous allez dire que je radotte avec mes const, mais bon quand même : le paramètre Node de la routine anonyme a été déclaré const alors qu'il est manifestement de type classe. C'est que : il faut quand même être compatible avec la signature du type TValueCallBack<TTreeNode<T>>, qui demande que son paramètre soit const ;-).

III-D-1. D'autres méthodes qui utilisent les routines anonymes ?

Oui, deux autres. DoAncestorChanged, qui a pour mission de faire un parcours préfixe sur la méthode AncestorChanged. Et BeforeDestruction, qui doit faire un parcours préfixe sur la méthode Destroying de tous les enfants. C'est toujours la même chose :

 
Sélectionnez

{*
  Appelle la procédure AncestorChanged sur toute la descendance (préfixe)
*}
procedure TTreeNode<T>.DoAncestorChanged;
begin
  PreOrderWalk(
    procedure(const Node: TTreeNode<T>)
    begin
      Node.AncestorChanged;
    end);
end;

{*
  [@inheritDoc]
*}
procedure TTreeNode<T>.BeforeDestruction;
begin
  inherited;

  if not IsDestroying then
    PreOrderWalk(procedure(const Node: TTreeNode<T>) begin Node.Destroying end);

  if (Parent <> nil) and (not Parent.IsDestroying) then
    Parent.RemoveChild(Self);
end;
					

III-E. Et le reste

Le reste, eh bien... Il est classique ;-) Rien de nouveau. Je ne vais donc pas m'éterniser dessus, mais le source complet est téléchargeable, comme tous les autres, en fin de tutorielTélécharger les sources.

III-F. Comment utiliser TTreeNode<T> ?

C'est bien beau d'écrire une classe d'arbre générique, mais comment on l'utilise ?

Après une description en long et en large de la classe TList<T>, il n'y a pas grand chose à dire. Je vais donc juste vous donner le code d'un petit programme de test.

 
Sélectionnez

procedure TestGenericTree;
const
  NodeCount = 20;
var
  Tree, Node: TTreeNode<Integer>;
  I, J, MaxDepth, Depth: Integer;
begin
  Tree := TTreeNode<Integer>.Create(0);
  try
    // Créer l'arbre
    MaxDepth := 0;
    for I := 1 to NodeCount do
    begin
      Depth := Random(MaxDepth+1);
      Node := Tree;

      for J := 0 to Depth-1 do
      begin
        if Node.IsLeaf then
          Break;
        Node := Node.Children[Random(Node.ChildCount)];
      end;

      if TTreeNode<Integer>.Create(Node, I).Depth > MaxDepth then
        Inc(MaxDepth);
    end;

    // Afficher l'arbre avec un parcours préfixe
    Tree.PreOrderWalk(
      procedure(const Node: TTreeNode<Integer>)
      begin
        Write(StringOfChar(' ', 2*Node.Depth));
        Write('- ');
        WriteLn(Node.Value);
      end);
  finally
    Tree.Free;
  end;
end;
				

précédentsommairesuivant

Tutoriels
Les génériques avec Delphi 2009 Win32 (English version) - également disponible en espagnol et en russe
Réaliser un plug-in comportant un composant
Construire une procédure pointant sur une méthode
Création de composants - en 4 parties
Refactoring avec Delphi 2007
Prise en main de Delphi 2005
Analyseurs syntaxiques - Leur fonctionnement par l'exemple
Créer un fichier d'aide HLP
Pourquoi un paramètre const change-t-il mystérieusement de valeur ?
Sources
SJRDUnits - Routines et classes diverses
SJRDComps - Quelques composants
Projet Sepi
Présentation
FAQ Sepi
Programmes
FunLabyrinthe - Jeu de labyrinthe très spécial et très fun
TrickTakingGame - Jeux de cartes à plis en ligne
MultiAgenda - Agenda multi-répertoires
DecodeFormulaires - Décode les formulaires
Excel --> HTML - Convertisseur de tableaux Excel en HTML
AddressLinks - Lie les adresses Internet et e-mail d'un document HTML
Vipion - Tic Tac Toe sur 4x4 cases avec jeu de l'ordinateur
BigCalc - Calculatrice de haut niveau
Espace paroissial Astérion de Watermael-Boitsfort
  

Copyright © 2008 Sébastien Doeraene. 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.