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.|