Les génériques avec Delphi 2009 Win32

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 :

unit Generics.Trees;

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

Un nœud d'un arbre sera étiqueté d'une valeur de type T, et aura de 0 à plusieurs enfants. Lorsqu'il est détruit, un nœud 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.

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

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 ?

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 nœud. 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 nœuds, et un parcours sur les valeurs des nœuds. 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 étiqueté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 ^^.

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 étiqueté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.

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.

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 :

{*
  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.

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 pseudoroutine 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 pseudoroutine « renvoie » la valeur par défaut du type demandé. On peut donc écrire :

{*
  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;

Afin d'illustrer l'utilisation des références de routine de l'autre côté du miroir, 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 nœuds, que voici :

{*
  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 !

{*
  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 ?

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

{*
  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;

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.

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.

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;