by Peter Davies

Most of the work for this is already done by TList, which as you may recall, is a standard class in Delphi. In fact, TList comes with a method to allow you to sort the list of objects, by calling the sort method with and passing a compare function as a parameter. The compare function that is required must not be a method of any class - it must be a normal Pascal function. This gets away from 'Object Oriented' programming and also, the list is only sorted when the Sort method is called.

A better way would be to have the compare function within the class, and the best way to accomplish this is to write a TListSorted class which inherits the TList class. In the TListSorted class, we add an abstract compare method. The Add method of the TList class should be overridden to place the new entry into its correctly sorted position, using the Insert and Compare methods of TList.

unit ListSort;
interface
uses Classes;
type
   TListSorted = class(TList)
    public
      // Allow duplicate objects in the
      // list of objects based on
      // compare(item1,item2) = 0
      // Default to dupIgnore (dupes ok)
      Duplicates : TDuplicates;

      constructor Create;

      // an abstract compare function
      // this should be overridden by an inheriting class
      // it should return   -1 if item1 < item2
      //                    0 if item1 = item2
      //                    1 if item1 > item2
      function Compare(Item1, Item2: Pointer): Integer; virtual; abstract;

      function Add(Item: Pointer): Integer;

      // returns the index of Item using the compare method to find
      // the object
      // note: if more than one object matches using the compare method,
      //       this does not look for the same memory address by
      //       matching the pointers, it looks for the same value
      //       ie compare method returns 0
      // then any one of those matching could be returned
      // The index returned, ranges from 0 to Count-1
      // A value of -1 indicates that no Item was found
      function FindObject(Item : Pointer) : Integer;
   end;

implementation

constructor TListSorted.Create;

begin
   Duplicates := dupIgnore;
   inherited Create;
end;

function TListSorted.Add(Item : Pointer) : Integer;

var
   nCount  : Integer;
   bFound  : Boolean;
   nResult : Integer;

begin
   nCount := 0;
   bFound := False;
   // search the list of objects until we find the
   // correct position for the new object we are adding
   while (not bFound) and (nCount < Count) do begin
      if (Compare(Items[nCount],Item) >= 0) then
         bFound := True
      else
         inc(nCount);
   end;
   if (bFound) then begin
      if (Duplicates = dupIgnore) or (Compare(Items[nCount],Item) <> 0) then begin
         Insert(nCount,Item);
         nResult := nCount;
      end else
         nResult := -1;
   end else
      nResult := inherited Add(Item);
   Add := nResult;
end;

function TListSorted.FindObject(Item : Pointer) : Integer;
// Find the object using the compare method and
// a binary chop search

var
   nResult   : Integer;
   nLow      : Integer;
   nHigh     : Integer;
   nCompare  : Integer;
   nCheckPos : Integer;

begin
   nLow := 0;
   nHigh := Count-1;
   nResult := -1;
   // keep searching until found or
   // no more items to search
   while (nResult = -1) and (nLow <= nHigh) do begin
      nCheckPos := (nLow + nHigh) div 2;
      nCompare := Compare(Item,Items[nCheckPos]);
      if (nCompare = -1) then                // less than
         nHigh := nCheckPos - 1
      else if (nCompare = 1) then            // greater than
         nLow := nCheckPos + 1
       else                                  // equal to
         nResult := nCheckPos;
   end;
   FindObject := nResult;
end;

end.

Whenever you wish to actually use a sorted list of objects, a new class should be written that inherits TListSorted, and it should implement its own compare method that is appropriate to the objects that are being sorted.

Now that we have a sorted list of objects, we can quickly search the list of objects using the Compare method. Using a binary chop search, a FindObject method can be written using the compare method, that will find any object in the list, in a fraction of the time normally required to search through the list. If the comparison required is not catered for in the Compare method, then unfortunately a linear search must still be used.

Here is the code. Going back to my previous article on TList, I had included a TArchive class. This has been modified to make use of the new TListSorted Class. Enjoy.

---

[HOME] [TABLE OF CONTENTS] [SEARCH]