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.

Etana

Yep, you deleted your last post, right after I edited my answer to show you how to use BinarySearch to search for a Date. Not cool. – Parkerparkhurst

How big is your list? The approach to searching will depend on if your talking about a small ist (a few dozens of items) or a large list. If your list is small, a linear search will be the most readable and probably best solution. – Febrifacient

To add to Smasher's comment: If you only search the list a few times, the linear-search approach is the preferred option. Using a smart search (binary search) requires quite a bit of work to sort the list. If on the other hand you'll do thousands of list lookups, BinarySearch will have the edge and sorting would be useful. And if you do even more searches, you might want to use a TDictionary<Date, Integer> to make search even faster. – Parkerparkhurst

@Marcello I tried to improve the question a bit but left the type names untouched. I think you have some confusion with TEstr TExtr TExtrList and TEstrList (they differ in code and explanation). It would be nice if you could edit these. – Region

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.

Parkerparkhurst

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.

Cabasset

I don't like this approach. TCompare<T> = function(const L, R: T): Integer; is more effective. Without any kind of funny interfaces. – Herzegovina

Also using reference to atleast in XE6 is bad for performance. Raw callbacks are the fastest. – Herzegovina

Answer 3

There is only a single way I've found to search through a list with a specific value.

I'll reuse Cosmin Prund example :

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

function SearchList(Date:TDate; Sort:Boolean; List:TList<TEstr>): Integer;
var Dummy : TEstr;
begin
  // 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(TDelegatedComparer<TEstr>.Construct(
    function (const L, R: TEstr): Integer
    begin
      Result := Sign(L.Date - R.Date);
    end
  );

  // Call BinarySearch() to look up the record based on Date alone
  if not List.BinarySearch(Dummy, Result, TDelegatedComparer<TEstr>.Construct(
      function (const L, R: TEstr): Integer
      begin
         //By implementation, the binarySearch Dummy parameter is passed in the "R" parameter of the Comparer function. (In delphi 2010 at least)
        Result := Sign(L.Date - Date); //Use the Date parameter instead of R.Date
      end) then
    Result := -1;
end;

This approach, however, is only valid "by implementation" and not "by design" (as far as I know). In other word, it is prone to break between versions of Delphi. So this is only advisable to use this approach for items that can be "performance expensive" to create. If you do so, I strongly advise to add something like this in your code.

{$IF RTLVersion > *YourCurrentVersion*}
   {$MESSAGE WARNING 'Verify if BinarySearch implementation changed'}    
{$IFEND}

p That way, next time you build this code in a newer version of Delphi, you will automatically get a warning telling you to make sure your code will still work as expected. But this could still causes problems if your code needs to support more than 1 version of Delphi at the same time.

Covey

Answer 4

I think you have this function in TDynArrayHashed , an example in this Post

Jerboa

Answer 5

Does it really needs to be a TList? Imo, binary searches are too complicated for this. Maybe you could simply use a TDictionary:

type
  TEstrCollection = TDictionary<TDate, TEstr>;

var
  EstrCollection: TEstrCollection;
begin
  EstrCollection := TEstrCollection.Create;

  // Add an item
  EstrCollection.Add(Date, TExtractList.Create)

  // Search
  ExtractList := EstrCollection[Date];
end;

Now, this requires the date field to be unique, as it's the key of the dictionary. Also, the items have no specific order.

If order is important, I would combine data structures. For example, you can have a TList just to hold the items in order plus a TDictionary just to perform the search, things like that.

The only thing is that records are not pointers. To add the same record in two distinct data structures you need to create pointers for them

PEstr = ^TEstr

Or just use objects, as they are pointers already. You could use TObjectList and TObjectDictionary to have life time of the items automatically managed by the collection (just remember to have only one of the collections managing the lifetime of the object if it is in more than one collection).

Psychobiology