Как я могу найти общий TList для записи с определенным значением поля?

Question

Все о родовом TList.У меня есть такая структура:

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

Основной список - TExtrList, и в этом списке у меня есть все даты и на дату все колеса с этой датой.Я хочу искать, если дата существует или нет.Если не существует, я добавляю в подсписок TExtractList Извлечения из TEstr информацию.Когда я ищу из TExtrList, Delphi спрашивает меня о типе TEstr.Мне нужно искать только Date.Так как же я могу найти одно поле в общем TList?

PS: я удалил последнее сообщение, потому что здесь я попытался объяснить лучше.

Answer 1

Здесь мы снова идем.

Вы должны использовать встроенную функцию TList<T>.BinarySearch(), даже если она по праву запрашивает запись TEstr в качестве параметра.Сначала вам нужно будет использовать TList<T>.Sort(), чтобы отсортировать список по тем же критериям, что и при поиске, а затем вызвать BinarySearch(), чтобы найти вашу запись.

Вот функция, которая выполняет оба действия (сортировка и поиск):

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 предполагает, что список отсортирован (в этом суть бинарного поиска!).При первом вызове необходимо установить Sort=True, чтобы список был правильно отсортирован.При последующих вызовах Sort должно быть False.Конечно, при реальном использовании у вас, вероятно, будут отдельные подпрограммы для поиска и сортировки, и вы, вероятно, будете использовать их как методы класса, начинающегося с TList<TEstr> (чтобы упростить задачу).Я помещаю оба в одну и ту же процедуру для целей демонстрации.

Answer 2

Я нашел только один способ поиска в списке с определенным значением.

Я буду использовать пример Cosmin Prund:

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;

Этот подход, однако, действителен только «по реализации», а не «по замыслу» (насколько я знаю). Другими словами, он склонен к разрыву между версиями Delphi. Поэтому этот подход целесообразно использовать только для элементов, создание которых может быть «дорогостоящим». Если вы это сделаете, я настоятельно советую добавить что-то подобное в ваш код.

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

р Таким образом, в следующий раз, когда вы создадите этот код в более новой версии Delphi, вы автоматически получите предупреждение о том, что ваш код будет работать должным образом. Но это все еще может вызвать проблемы, если ваш код должен поддерживать более 1 версии Delphi одновременно.

Answer 3

Вы также можете объявить вспомогательный класс, как этот, чтобы избежать требования IComparer, что левая и правая части сравнения должны быть специализированного типа:

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;

Тогда вы можете использовать это так:

// 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;

Это, конечно, менее типобезопасно (из-за нетипизированного параметра сравнения правой стороны), но оно необходимо для общего сравнения значений различных типов. С некоторой осторожностью это не должно быть проблемой. В противном случае вы также можете написать перегруженные версии для большинства используемых типов, которые вам нужно сравнить.

Answer 4

Я думаю, у вас есть эта функция в TDynArrayHashed , пример в этом Посте

Answer 5

Действительно ли должно быть списком TList? Imo, бинарный поиск слишком сложен для этого. Может быть, вы могли бы просто использовать 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;

Теперь для этого необходимо, чтобы поле даты было уникальным, так как оно является ключом словаря. Также у предметов нет определенного заказа.

Если важен порядок, я бы объединил структуры данных. Например, вы можете иметь TList только для того, чтобы хранить элементы по порядку, плюс TDictionary просто для выполнения поиска, и тому подобное.

Единственное, что records не указатели. Чтобы добавить один и тот же record в две разные структуры данных, вам нужно создать для них указатели

PEstr = ^TEstr

Или просто используйте объекты, так как они уже являются указателями. Вы можете использовать TObjectList и TObjectDictionary, чтобы время жизни элементов автоматически управлялось коллекцией (просто помните, что только одна из коллекций управляет временем жизни объекта, если он находится в нескольких коллекциях).