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: Delphi TCollection Sort