E-mail

Generics with Delphi 2009 Win32

With, as a bonus, anonymous routines and routine references

Date de publication : November 13th, 2008

Version PDF (Miroir) Version hors-ligne (Miroir)

III. Design of a generic class
III-A. Class declaration
III-B. Implementing a method
III-C. The pseudo-routine Default
III-D. Routine references with tree walks
III-D-1. Other methods using anonymous routines?
III-E. And the rest
III-F. How to use TTreeNode<T> ?

III. Design of a generic class

Now that we know how one can use generic classes, it is time to see how does a generic class work internally.

Therefore, we are going to develop a TTreeNode<T> class, which is going to be a generic implementation of a tree. This time, it will not be a study case any more. It is a real class, which you will be able to use in your real projects.

III-A. Class declaration

Let us begin with the beginning: the class declaration. As you may recall from the extract of the declaration of TList<T>, the generic parameter (traditionally called T when it has no precise meaning) is added between angle brackets. On should then write:


unit Generics.Trees;

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

A tree node will be labelled by a value of type T, and will have 0 to many children. When a node is destroyed, it frees all its children.

A value of type T? Well, this is as simple as this: FValue: T; the same way as for any normal type. To keep a list of the children, we will use a TObjectList<U>, declared in Generics.Collections. I have used U on purpose here, because I do not want you to be misleaded. Actually, U will be set to TTreeNode<T>! So yes, one can use a generic class as an actual generic parameter.

We do not implement a search tree. Consequently, we do not need any comparer like TList<T> does.

Our class will then have the following fields:


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

Weird? If we think a bit about it, not that much. We have said previously that a generic type could be replaced by any type. So, why not a generic class type?

I draw your attention to the fact that, in the name TTreeNode<T>, T is a non actual generic parameter (a formal paremeter, if you prefer). But in the inside of the class, it becomes a actual type! It behaves exactly as with the parameters of a routine. In the signature, you have formal parameters; but in the routine body, they are local variables just as much as any other. That is why on can use T as a type for FValue, or even as an actual parameter parameterizing TTreeNode<T>, in the declaration of FChildren.

When I said that we could use any type as actual parameter, I sort of lied to you. It is not exactly always true. For example, in TObjectList<T>, T must be a class type. This is so because TObjectList<T> has imposed a constraint on its parameterized type. We will see this concept later in more details, but I must point it out now, since we are using this class. We use it because we want to take profit from the automatic freeing of the objects stored in a TObjectList<T>, TList<T> not doing it.

As methods, besides the constructor and destructor, we provide methods for in-depth walks (preorder and postorder), along with methods for adding/moving/deleting child nodes. Actually, the addition will be asked by the child itself, when it will be given its parent.

For the walks, we will need a call-back type. Guess what? We will use a routine reference type. And we will provide two overloads for each walk: a walk on the nodes, and a walk on the values of the nodes. The second one will probably be used more often when using the TTreeNode<T> class. The first one is provided for completeness, and is more general. It will be used by several methods of TTreeNode<T> (e.g. the second overload).

Finally, there will be, of course, properties accessing the parent, children and labelled value. Which leads to the code below. You may see there is nothing new, besides the fact there are many T's everywhere.

Here is the complete declaration of the class -which, be reassured, I give you after I have completely impleted the class ^^.


type
  /// Call-back routine reference with an only parameter
  TValueCallBack<T> = reference to procedure(const Value: T);

  {*
    Generic tree structure
  *}
  TTreeNode<T> = class(TObject)
  private
    FParent: TTreeNode<T>;                /// Parent node (nil ifor the root)
    FChildren: TObjectList<TTreeNode<T>>; /// List of the children
    FValue: T;                            /// Label

    FDestroying: Boolean; /// True when the object is being destroyed

    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;

Let us identify what is remarkable here. Actually, not much, beside the fact that every parameter of type T is declared as const. Indeed, we do not know, at the time of writing, what could be the actual T. And thus there are some possibilities for it being a "heavy" type (as a string or record), for which it is more efficient to use const. And, as const is never penalizing (it is effectless on "light" types, such as Integer), we always put it when working with generic types.

The concept of heavy and light types is a concept of my own, nothing official, hence the quotes. I intend for heavy type a type whose parameters are better (in execution time) passed as const when it is possible. Those types are, in a general view, those who stretch on more than 4 bytes (floats and Int64 excluded), and those who require an initialization. One should remember strings, records, arrays, interfaces (not classes) and Variants.

However, when a parameter is of type TTreeNode<T>, we do not put const. Indeed, no matter what is T, TTreeNode<T> will remain a class type, which is a light type.

III-B. Implementing a method

In order to illustrate the particularities of the implementation of generic method, let us work with GetRootNode, which is very easy. It is written as below:


{*
  Root node of the tree
  @return Root node of the tree
*}
function TTreeNode<T>.GetRootNode: TTreeNode<T>;
begin
  if IsRoot then
    Result := Self
  else
    Result := Parent.RootNode;
end;

The only thing to notice here is that, each time your write the implementation of a generic method, you must specify the <T> next to the class name. It is mandatory, indeed, because TTreeNode (without <T>) would be another type, maybe existing in the same unit.

III-C. The pseudo-routine Default

In order to implement the two constructors that have no AValue parameter, we will need to initialize FValue one way or the other. Sure but, since we do not know the actual type of the value, how can we write a default value, for any possible type?

The solution is the new pseudo-routine Default. As well as TypeInfo, this pseudo-routine takes, as parameter, a type identifier. And the name of a generic type is actually a type identifier.

This pseudo-routine "returns" the default value of the provided type. One can then write:


{*
  Create a node with a parent and without label
  @param AParent   Parent
*}
constructor TTreeNode<T>.Create(AParent: TTreeNode<T>);
begin
  Create(AParent, Default(T));
end;

{*
  Create a node without parent and without label
*}
constructor TTreeNode<T>.Create;
begin
  Create(nil, Default(T));
end;

In the case of initializing an object field, this is not, strictly speaking, necessary, because instanciation of an object already initializes all its fields to their respective default value. But I could not find a better place to introduce you with this pseudo-routine.

III-D. Routine references with tree walks

In order to illustrate routine references, from the other side of the mirror, let us discuss the implementation of tree walks.

Both overloads of the walk takes as parameter a call-back routine reference. Notice that, also here, we have used a const parameter. Indeed, the attentive reader will remeber that routine references are actually interfaces. Now, an interface is a heavy type. One should then use const when possible.

Except this little consideration, there is nothing special to say on the first version, the one on nodes:


{*
  Preorder walk on the nodes of the tree
  @param Action   Action to execute on each node
*}
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;

To call the call-back, we have written exactly the same piece of code as with procedural types, i.e. the same form as a routine call, but with the routine reference variable instead of the routine name.

When implementing the second overload, we use the first one, giving for Action... a anonymous routine!


{*
  Preorder walk on the values of the tree
  @param Action   Action to execute on each value
*}
procedure TTreeNode<T>.PreOrderWalk(const Action: TValueCallBack<T>);
begin
  PreOrderWalk(
    procedure(const Node: TTreeNode<T>)
    begin
      Action(Node.Value);
    end);
end;

Isn't it a nice piece of code?

You will say I ramble on const parameters, yet: the Node parameter of the anonymous routine has been declared const, yet it is clearly a class type. The reason is: one should nertheless be compatible with the signature of the TValueCallBack<TTreeNode<T>> type, which demands a const parameter ;-).

III-D-1. Other methods using anonymous routines?

Yes, two others. DoAncestorChanged, which has to undertake a preorder walk on the method AncestorChanged. And BeforeDestruction, which has to do a preorder walk on the Destroying method of all the children. It is always the same:


{*
  Call the AncestorChanged procedure on every descendant (preorder)
*}
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. And the rest

The rest, well ... That is pretty classic ;-) Nothing new. I will not extend on this, but the complete source is available for download, as all the others, at the end of the tutorial.

III-F. How to use TTreeNode<T> ?

That is certainly nice to write a generic tree class, but can we use it?

After a description in every detail of the TList<T> class, there is not much to say left. I am only going to give you the code of a small test program.


procedure TestGenericTree;
const
  NodeCount = 20;
var
  Tree, Node: TTreeNode<Integer>;
  I, J, MaxDepth, Depth: Integer;
begin
  Tree := TTreeNode<Integer>.Create(0);
  try
    // Build the tree
    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;

    // Show the tree with a preorder walk
    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édent Sommaire Suivant

Version PDF (Miroir) Version hors-ligne (Miroir)

Warning: include(): http:// wrapper is disabled in the server configuration by allow_url_include=0 in /home/developpez/www/developpez-com/upload/sjrd/delphi/tutoriel/generics/index.php on line 41

Warning: include(http://sjrd.developpez.com/references.inc): failed to open stream: no suitable wrapper could be found in /home/developpez/www/developpez-com/upload/sjrd/delphi/tutoriel/generics/index.php on line 41

Warning: include(): Failed opening 'http://sjrd.developpez.com/references.inc' for inclusion (include_path='.:/opt/php56/lib/php') in /home/developpez/www/developpez-com/upload/sjrd/delphi/tutoriel/generics/index.php on line 41

Copyright © 2008-2009 Sébastien Doeraene. Aucune reproduction, même partielle, ne peut être faite de ce site ni 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.