How do I search a generic TList<T> collection?

Question

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

I have a collection of

TList<TActivityCategory>

TActivityCategory has a Name property of type string and I want to search the TList using the Name property.

I see BinarySearch in the TList<> but that would require an instance of TActivityCategory. I just want to pass the string for a name.

How would I go about doing this?

Solution 1

When you create the list you can pass in a comparer. There are some comparer classes in the Generics.Defaults unit where you can pass in some anonymous method to compare two elements. They are used for several methods like IndexOf, Contains or Sort.

Example:

uses
  Generics.Defaults,
  Generics.Collections;

type
  TActivityCategory = class
  private
    FName: string;
  public
    constructor Create(const Name: string);
    property Name: string read FName write FName;
  end;

constructor TActivityCategory.Create(const Name: string);
begin
  FName := Name;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  activities: TList<TActivityCategory>;
  search: TActivityCategory;
begin
  activities := TObjectList<TActivityCategory>.Create(
    TDelegatedComparer<TActivityCategory>.Create(
      function(const Left, Right: TActivityCategory): Integer
      begin
        Result := CompareText(Left.Name, Right.Name);
      end));

  activities.Add(TActivityCategory.Create('Category B'));
  activities.Add(TActivityCategory.Create('Category C'));
  activities.Add(TActivityCategory.Create('Category A'));

  search := TActivityCategory.Create('Category C');
  if activities.Contains(search) then
    ShowMessage('found');

  ShowMessageFmt('Index: %d', [activities.IndexOf(search)]);
  activities.Sort;
  ShowMessageFmt('Index: %d', [activities.IndexOf(search)]);


  search.Name := 'Category D';
  if not activities.Contains(search) then
    ShowMessage('not found');

  search.Free;
  activities.Free;
end;

Solution 2

To be perfectly frank, and considering all the boiler plate required for a comparer based approach, it may just be simplest to write your own search routine:

type
  TActivityCategoryList = class(TList<TActivityCategory>)
  public
    function Find(const Name: string): Integer;
  end;

function TActivityCategoryList.Find(const Name: string): Integer;
begin
  for Result := 0 to Count-1 do
    if Self[Result].Name=Name then
      exit;
  Result := -1;
end;

Solution 3

If you don't have an instance to search for, you have to do your own search. There are three basic ways to do this:

• Binary search: Implement your own binary search. This will only work if the list is sorted.
• Linear search: Implement your own linear search. This will always work, but on large lists it's significantly slower than a binary search.
• Dictionary lookup: Maintain a TDictionary<string, TActivityCategory> alongside the list. No searching required, though you need to write some code to keep the two in sync.

Comments

[David Heffernan]

TList<T> can do this fine with a custom comparer

[Thomas Jaeger]

I like the Dictionary lookup idea but it seems that there must be a more elegant solution.

[Conrad Hildebrand]

If you don't have an instance, you can just create one. You only have to set the fields you actually use in your provided comparer.

[Thomas Jaeger]

Would you mind showing an example?

[Sam]

You can pass in your comparer but IComparer requires that both sides of the comparison must be instances of the specialized type. If I understood it correctly, the OP wants to avoid creating an instance for the purpose of searching; here's my attempt (as an answer to a similar question).

[Stefan Glienke]

@TOndrej: My answer is considering the comments to Masons answer

[Stefan Glienke]

Yeah, and when you are done someone thinks it would be a nice idea to have that list sorted by category name... whoops

[David Heffernan]

@Stefan I suppose my answer is born of frustration from known what the solution would be in C#. Delphi and its library just aren't composable enough. The fact that the comparer has to be assigned at list creation time is a killer. How do you use that approach to search the same list by name and category? Is there a library function that we have missed?

[Stefan Glienke]

No and that is why everyone that is seriously working with lists and doing more than storing things in it like searching by different criteria should forget about the built-in generic lists and look at Collections or Spring. They both have things similar to the IEnumerable<T> extension methods in C#.

[David Heffernan]

@Stefan Thanks a lot for the tip. I will take a look at those libraries.