Thursday, July 05, 2007

Implementing a sortable TCollection in Delphi

Delphi's TCollection class is very useful, but out of the box it lacks the ability to sort the items in the list.  Fortunately, this is easily addressable accessing some private properties of the TCollection class.  Internally, the items in a TCollection are stored in a private TList named FList. 

The trick is to get access to a private property.  The way to do this is by creating a shadow class.  A shadow class is a class that matches the private declaration of the class that you need to access.  The shadow needs to have the same field types in the same order, up to and including the field that you need access to.  This is the risky part, and cover that risk later.  The definition of the TCollection class starts out with:

TCollection = class(TPersistent)
private
FItemClass: TCollectionItemClass;
FItems: TList;
FUpdateCount: Integer;
FNextID: Integer;
FPropName: string;


To get at FItems, we need to shadow the top two members of the class.  Which provides this shadow class:



TShadowedCollection = class(TPersistent)
private
FItemClass: TCollectionItemClass;
FItems: TList;
end;


With access to the internal list, it becomes a simple task to provide the ability to the sort the list.  A public Sort method will call an internal method that runs a Quicksort across the list.  The Quicksort code will process the list obtained by casting itself as TShadowedCollection, allowing access to FItems and then call a Compare() function to compare items in the FItems list.  The collection will provide a "do nothing" Compare() function.  It will be up to the descendant class to override that function and implement the actual comparision code.  The full source code for the class would look something like this:


unit SortCollections;

interface

uses classes;

type
TSortableCollection
= class(TCollection)
protected
function Compare(Item1, Item2 : TCollectionItem) : integer; virtual;
procedure QuickSort(L, R: Integer);
public
procedure Sort;
end;

implementation

type
// Helper class to allow sorting of a TCollection
{$HINTS OFF}
TShadowedCollection
= class(TPersistent)
private
FItemClass: TCollectionItemClass;
FItems: TList;
end;
{$HINTS ON}


{ TSortableCollection }

function TSortableCollection.Compare(Item1, Item2: TCollectionItem): integer;
begin
(*

Descendant classes would override this method and cast Item1 and Item2 to the
decendant class's collection item type perform the field comparisions

if item1.MyField < item2.MyField
return -1
else if item1.MyField > item2.MyField
return 1
else return 0

*)
result :
= 0;
end;

procedure TSortableCollection.QuickSort(L, R: Integer);
var
I, J, p: Integer;
Save: TCollectionItem;
SortList: TList;
begin
//This cast allows us to get at the private elements in the base class
SortList := TShadowedCollection(Self).FItems;

repeat
I :
= L;
J :
= R;
P :
= (L + R) shr 1;
repeat
while Compare(Items[I], Items[P]) < 0 do
Inc(I);
while Compare(Items[J], Items[P]) > 0 do
Dec(J);
if I <= J then begin
Save :
= SortList.Items[I];
SortList.Items[I] :
= SortList.Items[J];
SortList.Items[J] :
= Save;
if P = I then
P :
= J
else if P = J then
P :
= I;
Inc(I);
Dec(J);
end;
until I > J;
if L < J then
QuickSort(L, J);
L :
= I;
until I >= R;
end;

procedure TSortableCollection.Sort;
begin
if Count > 1 then
QuickSort(
0, pred(Count));
end;

end.

Tech Tags:

3 comments:

  1. excellent. thank you.

    ReplyDelete
  2. Why you need use access to private field for sort, if you implement quick sort in you code? This bad approach in the OOP!
    In this case you can use TShadowedCollection(Self).FItems.Sort() method or not use hack method for access private field or use you Sort procedure with Items property w/o use FItems list.

    ReplyDelete

Note: Only a member of this blog may post a comment.