2011. június 4., szombat

List Template In Delphi


Problem/Question/Abstract:

How to create a type specific list in Delphi without reimplementing the entired list for each type ?

Answer:

The C++ language has a nice feature, that's called Templates. It allowes the programer to define a class (or a method) that acts with a none-specific type. At complie time, the programer describes for which type the class will be defined. That is, you can define a general list (list template) and define all of it's methods to work on type A (where 'A' is not defined). For example, the method GetItem will look as follows :

function GetItem(Index: Integer): A;

Then, at compile type you tell the complier that 'A' is actually an Integer, and the complier replaces all of the accurances of 'A' with 'Integer'. That way, you can write one list (for type 'A'), and each time you wan a list (of Strings, Integers, Boolean, Soubles, etc.) you just need to tell the complier to replace 'A' with the type you want.

All of that is very nice, but has nothing to do with Delphi. It's relevent only to C++ programers. So what do Delphi programers do ?

There are 3 majore options. First, write a list of pointers once, and then use it many times by passing to it a pointer to the datatype you are interested in. For Example :
  
TList = class
  ...
  public
  procedure Add(Value: Pointer);

  function GetItem(Index: Integer): Pointer;
  procedure SetItem(Index: Integer; Value: Pointer);

  property Items[Index: Integer]: Pointer read GetItem write SetItem;
  
end;

Here is the code to use this :

// For Integer;
type
  PInteger = ^Integer;
var
  Item: PInteger;
  List: TList;
begin
  List := TList.Create;
  GetMem(Item, SizeOf(Item));
  Item^ := 1023; // Or what ever value you wish
  List.Add(Item);
  ShowMessage(IntToStr(PInteger(List.Items[0])^));
end;

// For Double;
type
  PDouble = ^Double;
var
  Item: PDouble;
  List: TList;
begin
  List := TList.Create;
  GetMem(Item, SizeOf(Item));
  Item^ := 3.14.15926; // Or what ever value you wish
  List.Add(Item);
  ShowMessage(FloatToStr(PDouble(List.Items[0])^));
end;

As you've probably noticed there are a few drawbacks to this solution. The most obvious one is that you need to typecast the value returned by the List each time you want to use it. That might seem as a mere inconvinouce, but if you plan to uses lists intensivly, you'll get REALY tired of typecasting all the time. The second problem to consider with this design is memory concerns. In the example above, I've allocated memory to Item, but never free it. That's because the TList class I've used doesn't allocate memory by itself. But then arisses the question, how will free the memory ? Probably the TList itself (since the item is now 'owned' by it), but that is a bit unconventional, because usually the object (or method) that allocates the memory is responsibly to freeing it. You can solve this by writing the TList class so it allocates it's own memory and only COPIES the value pointed to by Item. But then there are two other problem.

You need to free the memory of Item after adding it to the List (since the List isn't going to free it - it only copied the Items contents).
You need to find a way of telling TList how many byte to copy. Since TList gets a pointer and doesn't know what it points to (a string ? an integer ? a double ?), it has no way of knowing how many bytes to copy.

Those are all very good reasons why NOT to use this solution. Lets have a look at the second solution out of the three.

The second solution is very simple. Write a new list for each type. That is, write a TIntergerList, TStringList, TDoubleList, TWhatEverList. Example :
  
TIntegerList = class
  ...
  public
  procedure Add(Value: Integer);

  function GetItem(Index: Integer): Integer;
  procedure SetItem(Index: Integer; Value: Integer);

  proepry Items[Idnex: Integer]: Integer read GetItem write SetItem;
end;

TDoubleList = class
  ...
  public
  procedure Add(Value: Double);

  function GetItem(Index: Integer): Double;
  procedure SetItem(Index: Integer; Value: Double);

  property Items[Index: Integer]: Double read GetItem write SetItem;
end;

The benefits are obvious. You can use a list and have no memory problems and you need not typecast ! Implementing these lists could be a little time consuming, but if you work a lot with the same types of lists it might be worth while. The only draw back of this design (except for a one time developing cost) is it's not extendable (at least not easly). That is, if you want to add a new function to your List (for example : SaveToFile), you'll have to add the same code for each list you implement. That vrings us to the third and final solution.

This solution is a combination of the first and second solutions. It tries to take the best of each. The first solution was very general (worked for every type without adding code), but you couldn't make it specific (you have to use typecasting inorder to use an Item). The second solution was very specific (no typecasting needed) but you had to write a bunch of code for each new list you wanted to implement.

And here is the third solution : Define a base class that is the same as the TList in the first solution. Then, for each new list you want (for example : TIntegerList) smiply inherite from the base class and add the type specific methods (for example : procedure Add(Value : Integer)). There are a few problems with this design as well, but I'll discuss them later. For now, lets see why this design helps as more than the other two.

First, it allows you to use type specific lists (no need for typecasting). Second it doesn't require you to write a lot of code (five mintues will do) for each new List because most of the methods are already implemented and the new methods that need to be implemented are very short.

Lets look closly at the last suggestion. First we need to define a base class :

TBaseList = class
protected
  procedure AddData(Value: Pointer);
  class function ItemSize: Integer; virtual; abstract;
end;

procedure TBaseLink.AddData(Value: Pointer);
var
  P: Pointer;
begin
  GetMem(P, ItemSize);
  Move(P^, Value^, ItemSize);
  // Here you need to add P to your list.
  // The way that is done may vary by the way you decide
  // to save your data. You may want to save it as an Array
  // or as a linked list, or as a tree, or into a stream, etc.
end;

Now, lets create a TIntegerList :

TIntegerList = class
protected
  class function ItemSize: Integer; override;
public
  procedure Add(Value: Integer);
end;

class fucntion TIntegerList.ItemSize: Integer;
  begin
    Result := SizeOf(Integer);
  end;

procedure TIntegerList.Add(Value: Integer);
var
  P: ^Integer;
  begin
    GetMem(P, SizeOf(Integer));
    try
      P^ := Value;
      AddData(P);
    finally
      FreeMem(P, SizeOf(Integer));
  end;
end;

This example is simplefied. In a real list (with full capabilitys) most of the coding is in the base class, and only a few methods are need to be implemented in the derived classes.

I've attached a full implementation of this concept for TIntegerList and TStringList. Notice a few things about the attached file : a) The IBooleanList is defined but not implemented. b) The marked out methods at the begining of the file are not implemented yet. c) Objects aren't suported yet.

When I finish coding these lists, I'll write another article describing my specific implementation of this idea.

Component Download: http://www.kastu.lt/dkb/downfile/download.php?id=100

Nincsenek megjegyzések:

Megjegyzés küldése