How can I search a generic TList for a record with a certain field value?

Question

Everything about generic TList. I have this structure:

Type
  TExtract = record
    Wheel: string;
    Extract: array [1..5] of Byte;
  end;

  TExtractList = TList<TExtract>

  TEstr = record
    Date: TDate;
    Extract: TExtractList;
  end;

  TEstrList = TList<TEstr>;

The main list is TExtrList and in this list I have all dates and for date all wheel with that date. I want to search if a date exists or not. If not exist I add in sublist TExtractList of Extract from TEstr the info. When I search from TExtrList Delphi asks me about TEstr type. I need to search for Date only. So how can I search for single field in a generic TList?

PS: I have deleted last post because here I have tried to explain better.

Answer 1

Here we go again.

You should use the built-in TList<T>.BinarySearch() function, even if it rightfully asks for a TEstr record as a parameter. You'll first need to use TList<T>.Sort() to sort the list using the same criteria as for the search, then call BinarySearch() to find your record.

Here's a function that does both (sort and search):

uses Generics.Defaults; // this provides TDelegatedComparer
uses Math; // this provides Sign()

function SearchList(Date:TDate; Sort:Boolean; List:TList<TEstr>): Integer;
var Comparer: IComparer<TEstr>;
    Dummy: TEstr;
begin
  // Prepare a custom comparer that'll be used to sort the list
  // based on Date alone, and later to BinarySearch the list using
  // date alone.
  Comparer := TDelegatedComparer<TEstr>.Construct(
    function (const L, R: TEstr): Integer
    begin
      Result := Sign(L.Date - R.Date);
    end
  );

  // If the list is not sorted, sort it. We don't know if it's sorted or not,
  // so we rely on the "Sort" parameter
  if Sort then List.Sort(Comparer);

  // Prepare a Dummy TEstr record we'll use for searching
  Dummy.Date := Date;

  // Call BinarySearch() to look up the record based on Date alone
  if not List.BinarySearch(Dummy, Result, Comparer) then
    Result := -1;
end;

BinarySearch assumes the list is sorted (that's the essence of binary searching!). On your first call you need to set Sort=True so the list is properly sorted. On subsequent calls Sort should be False. Of course, in actual use you'd probably have separate routines for searching and sorting, and you'd probably have them as methods of a class descending from TList<TEstr> (to make things easyer). I places both in the same routine for dempnstration purposes.

Answer 2

You could also declare a helper class like this, to avoid the requirement of IComparer that both left and right side of the comparison must be of the specialized type:

type
  TLeftComparison<T> = reference to function(const Left: T; var Value): Integer;

  TListHelper<T> = class
  public
    class function BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
      Comparison: TLeftComparison<T>; Index, Count: Integer): Boolean; overload;
    class function BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
      Comparison: TLeftComparison<T>): Boolean; overload;
    class function Contains(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Boolean;
    class function IndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
    class function LastIndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
  end;

class function TListHelper<T>.BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
  Comparison: TLeftComparison<T>; Index, Count: Integer): Boolean;
var
  L, H: Integer;
  mid, cmp: Integer;
begin
  Result := False;
  L := Index;
  H := Index + Count - 1;
  while L <= H do
  begin
    mid := L + (H - L) shr 1;
    cmp := Comparison(Instance[mid], Value);
    if cmp < 0 then
      L := mid + 1
    else
    begin
      H := mid - 1;
      if cmp = 0 then
        Result := True;
    end;
  end;
  FoundIndex := L;
end;

class function TListHelper<T>.BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
  Comparison: TLeftComparison<T>): Boolean;
begin
  Result := BinarySearch(Instance, Value, FoundIndex, Comparison, 0, Instance.Count);
end;

class function TListHelper<T>.Contains(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Boolean;
begin
  Result := IndexOf(Instance, Value, Comparison) >= 0;
end;

class function TListHelper<T>.IndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
var
  I: Integer;
begin
  for I := 0 to Instance.Count - 1 do
    if Comparison(Instance[I], Value) = 0 then
      Exit(I);
  Result := -1;
end;

class function TListHelper<T>.LastIndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
var
  I: Integer;
begin
  for I := Instance.Count - 1 downto 0 do
    if Comparison(Instance[I], Value) = 0 then
      Exit(I);
  Result := -1;
end;

Then you could use it like this:

// TComparison (requires instances on both sides)
function CompareEstr(const Left, Right: TEstr): Integer;
begin
  if Left.Date < Right.Date then
    Exit(-1);
  if Left.Date > Right.Date then
    Exit(1);
  Result := 0;
end;

// TLeftComparison: requires instance only on the left side    
function CompareEstr2(const Left: TEstr; var Value): Integer;
begin
  if Left.Date < TDateTime(Value) then
    Exit(-1);
  if Left.Date > TDateTime(Value) then
    Exit(1);
  Result := 0;
end;

procedure Main;
var
  Date: TDate;
  Comparer: IComparer<TEstr>;
  List: TEstrList;
  Item: TEstr;
  Index: Integer;
  I: Integer;
begin
  Comparer := nil;
  List := nil;
  try
    // create a list with a comparer
    Comparer := TComparer<TEstr>.Construct(CompareEstr);
    List := TEstrList.Create(Comparer);
    // fill with some data
    Date := EncodeDate(2011, 1, 1);
    for I := 0 to 35 do
    begin
      Item.Date := IncMonth(Date, I);
      List.Add(Item);
    end;
    // sort (using our comparer)
    List.Sort;

    Date := EncodeDate(2011, 11, 1);
    Item.Date := Date;

    // classic approach, needs Item on both sides   
    Index := List.IndexOf(Item);
    Writeln(Format('TList.IndexOf(%s): %d', [DateToStr(Date), Index]));
    List.BinarySearch(Item, Index);
    Writeln(Format('TList.BinarySearch(%s): %d', [DateToStr(Date), Index]));
    Writeln;

    // here we can pass Date directly
    Index := TListHelper<TEstr>.IndexOf(List, Date, CompareEstr2);
    Writeln(Format('TListHelper.IndexOf(%s): %d', [DateToStr(Date), Index]));
    TListHelper<TEstr>.BinarySearch(List, Date, Index, CompareEstr2);
    Writeln(Format('TListHelper.BinarySearch(%s): %d', [DateToStr(Date), Index]));
    Readln;
  finally
    List.Free;
  end;
end;

This is of course less type-safe (due to the untyped right-side comparison parameter) but needed to allow to generically compare values of different types. With a bit of care this should not be a problem. Otherwise you could also write overloaded versions for most used types you need to compare.