Generic ObjectList und Suchen - Wie am besten ?

[OlafSt]

Hallo Freunde,

heute mal was für Generic-Anfänger, wie ich es bin. Bisher hab ich die Dinger immer nur benutzt - das soll sich nun ändern.

Ich habe immer wieder das Problem, das ich Objekte en masse in ObjectLists speichern und immer wieder das eine oder andere Objekt in dieser Liste suchen muß. Generics waren eine - wenn auch sehr codeaufblähende - prima Lösung. Nur das Gesuche ist noch immer "doof".

Ich habe nun vor, mich dem Problem schrittweise zu nähern. Meine erste Idee:

Delphi-Quellcode:

type
   TMyObjectList<T> = class(TObjectList<T>);

Das funktioniert offenbar, weil es ohne Error compiliert :D Okay.

Delphi-Quellcode:

type
   TMyObjectList<T> = class(TObjectList<T>);
   public
      function Search(ASearchCrit: integer): T;
   end;
[...]
function TMyObjectList<T>.Search(ASearchCrit: integer): T;
begin
   for Result in Self do
   begin
      if Result.  //<--- Äh... Das funktioniert nicht. Gar nicht
   end;
end;

Wie man sieht, ist mein Ansatz eine direkte Fahrt gegen die Wand. Zwei Fragen:

1. Wie löst man sowas ?
2. Da in TMyObjectList irgendwas gestopft werden kann - bin ich gezwungen, alle möglichen Typen zuerst abzutesten oder gibt es da auch eine clever Lösung ?

Delphi-Quellcode:

Result:=true;
if T is TDriver then exit;
if T is TSpecialDriver then exit;
if T is TExtraSpecialDriver then exit;
Result:=false;

Thanks für die Schubser,

Olaf

[mkinzler]

Haben die Typen eine gemeinsamen Vorfahren? Soll einer davon ausgeschlossen werden? Wenn Ja, kannst du die Anweisungen zusammenfassen:

Delphi-Quellcode:

if T in [ TDriver, TSpecialDriver, TExtraSpecialDriver, ...] then Result := True else Result := False;

Wenn es für alle Nachfahren einer Klasse gelten soll prüfe gegen diese.

[OlafSt]

Ah, eine gute Idee !

Die Klassen haben einen gemeinsamen Vorfahren und es reicht, gegen den zu testen:

Delphi-Quellcode:

Result:=(T is TDriverBase);

Damit sind alle Nachfahren erfaßt und zulässig, alle anderen Klassen wie z.B. TComponent oder TWorkTime (völlig andere Unit) eliminiert.

Bleibt Problem 1.

[mjustin]

Ist ASearchCrit: Integer für alle zu unterstützenden Klassen in gleicher Weise die Suchbedingung?

Falls ja, könnte man entweder alle Klassen von einer ableiten die eine ID Property hat, und in der Schleife dann diese ID mit ASearchCrit vergleichen.

Alternativ könnte man ein Interface benutzen, das alle Klassen unterstützen und das diese ID Property definiert, auch dann kann ASearchCrit mit der ID verglichen werden.

Schliesslich gibt es noch die Möglichkeit Equals zu überschreiben. Doch das hat Risiken und Nebenwirkungen.

[mkinzler]

Warum erzeugst du dann nicht eine typisierte generische Objektliste?

Delphi-Quellcode:

  TMyObjectList<T> = class(System.Generics.Collections.TObjectList<TDriverBase>)
   public
      function Search(ASearchCrit: integer): T;
   end;

Problem 1 versteht ich nicht. Was willst Du machen?

[Puke]

Soweit ich verstanden habe, wird die List sehr groß. Wenn sowas passiert und man will darin suchen ... normalerweise sortiert man das Ding. Ansonsten kannst du nur eine Lineare Suche machen (Kann ziemlich lange dauern).

Pseudo Lineare Suche:

Delphi-Quellcode:

for AnfangListe to EndeListe do
begin
  if Element=Gesucht then
  begin
    Result = ElementIndex // Oder was auch immer
    Break;                
  end;
end;

Wird das Ding aber immer schön sortiert kannst du eine Binäre Suche machen. Diese ist wesentlich schneller als die Lineare Suche. Da es ne Liste ist, gibt es soweit ich weiß keine andern Suchmöglichkeiten mehr. Der Algorithmus ist ein wenig schwieriger, aber immernoch ziemlich einfach, wenn man es Rekursiv macht.

Gruß
Puke

[Stevie]

Delphi-Quellcode:

type
  TMyObjectList<T> = class(TObjectList<T>);
  public
    function Search(const predicate: TPredicate<T>): T;
  end;

Einsatz:

Delphi-Quellcode:

myDriver := driverList.Search(
  function(d: TDriver): Boolean
  begin 
    Result := d.Id = 1234 
  end);

Vorteil: Du schränkst deine generische Listenklasse nicht auf bestimmte Suchkriterien ein, die nur für bestimmte Arten von T gelten.

Wenn dir das Schreiben der anonymen Methode zu unhandlich ist, kannst du das auch noch auslagern:

Delphi-Quellcode:

function DriverById(i: Integer): TPredicate<TDriver>;
begin
  Result := 
    function(d: TDriver): Boolean
    begin 
      Result := d.Id = i;
    end;
end;

Einsatz:

Delphi-Quellcode:

myDriver := driverList.Search(DriverById(1234));

Eventuell kannst du dir auch Spring4D anschauen, die Listen dort unterstützen alle Arten von Suchen, Filtern, etc

[mkinzler]

Er will ja aber nur Nachfahren einer bestimmte Klasse aufnehmen, deshalb erschien mir die Einschränkung sinnvoll.

[schöni]

Zitat:

Delphi-Quellcode:

type  
  TMyObjectList<T> = class(TObjectList<T>);

Ab welcher Delphi Version funktioniert das?

[mkinzler]

Generics wurden in D2009 eingeführt

[Sir Rufo]

Zitat:

Zitat von mkinzler (Beitrag 1267636)

Warum erzeugst du dann nicht eine typisierte generische Objektliste?

Delphi-Quellcode:

  TMyObjectList<T> = class(System.Generics.Collections.TObjectList<TDriverBase>)
   public
      function Search(ASearchCrit: integer): T;
   end;

Und wie bekommst du jetzt die Einschränkung hin? Denn das geht ja jetzt auch:

Delphi-Quellcode:

var
  List : TMyObjectList<Integer>;

Oder wolltest du eher so etwas schreiben:

Delphi-Quellcode:

  TMyObjectList<T:TDriverBase> = class(System.Generics.Collections.TObjectList<T>)
   public
      function Search(ASearchCrit: integer): T;
   end;

Allerdings ist die Variante von Stevie doch genau richtig. Die kann ich für alle Varianten benutzen. Und wenn ich eine Liste benötige, in der sich nur Elemente vom Typ

Delphi-Quellcode:

TDriverBase

und davon abgeleitete Klassen, dann

Delphi-Quellcode:

var
  List : TMyObjectList<TDriverBase>;

[OlafSt]

Wie praktisch, das einem der Kaffee ausgeht und man schnell mal losmuß, neuen zu besorgen. Sind ja tolle Ideen hier aufgeführt, danke schonmal dafür.

Delphi-Quellcode:

TMyObjectList<T:TDriverBase> = class(System.Generics.Collections.TObjectList<T>)

ist eigentlich das, was mir vorschwebt. Dann sorgt doch schon der Compiler dafür, das ich da keinen Integer oder TWorkTime (der nichts mit TDriverBase zu tun hat) versuche einzufügen. Ain't I right ?

Die Datenmengen halten sich da in engen Grenzen, ein paar hundert Items, schlimmstenfalls. Da geht ein linear search allemal, wirds zu dolle, weiche ich dann schon von selbst auf ein binary search aus. Das Risiko ist aber gering. Mir geht es eigentlich darum, das ich immer wieder und wieder dieselben Routinen bastele:

Delphi-Quellcode:

//Suche Fahrer (Basisklasse)
function FindDriverByID(AID: integer): TDriverBase;
begin
   for Result in self do
      if Result.ID = AID then exit;
   Result:=nil;
end;

function FindDriverByName(AName: string): TDriverBase;
begin
...
end;

//Suche Fahrer (SpezialKlasse)
function FindSpecialDriverByID(AID: integer): TSpecialDriver;
begin
   for Result in self do
      if Result.ID = AID then exit;
   Result:=nil;
end;

function FindSpecialDriverByName(AName: string): TSpecialDriver;
begin
...
end;

//Suche Arbeitszeiten
function FindWorkTimeByID(AID: integer): TWorkTime;
begin
   //Benutzt natürlich eine andere Collection mit Worktimes drin
   for Result in self do
      if Result.ID = AID then exit;
   Result:=nil;
end;

function FindWorkTimeByDate(ADate: TDateTime): TWorkTime;
begin
   for Result in self do
      if Result.WorkDate = ADate then exit;
   Result:=nil;
end;

//und so weiter und so fort...

Ich suche nun einen Weg, sowas eben nur ein einziges Mal machen zu müssen und ich dachte, Generics sind ein idealer Weg dafür. Während der Fahrt nachgedacht bin ich dann auf folgende - beinahe ideale - Lösung gekommen: Da meine Fahrer alle ein paar Gemeinsamkeitein haben (eine eindeutige ID, Namen etc) und eigentlich nur über diese Felder gesucht wird, stopfen wir das in die TDriverBase-Klasse. Anschließend nehmen wir die oben genannte Deklaration und basteln die Suchroutinen - und schon kann ich prima Listen für meine verschiedenen Fahrertypen erzeugen, in die ich nix "unsinniges" stecken kann und doch ohne duplizierten Code suchen und ggf. noch andere lustige Dinge anstellen:

Delphi-Quellcode:

TMyObjectList<T:TDriverBase> = class(System.Generics.Collections.TObjectList<T>)
public
  function FindByID(AID: integer): T;
  function FindByName(AName: string): T;
end;

var
  TDriverList: TMyObjectList<TDriver>;
  TSpecialDriverList: TMyObjectList<TSpecialDriver>;
  //15 Bier später...
  TWorkTimeList: TMyObjectList<TWorkTime>; //funzt nicht, gibt sofort Haue vom Compiler

Damit bin ich einen gewaltigen Haufen Suchroutinen schon mal los. Genial, danke für den Schubser an euch alle.

[Stevie]

Zitat:

Zitat von OlafSt (Beitrag 1267700)

Ich suche nun einen Weg, sowas eben nur ein einziges Mal machen zu müssen und ich dachte, Generics sind ein idealer Weg dafür.

Die Ideallösung habe ich oben bereits geschrieben. Wenn du dir nämlich anschaust, wo sich deine ganzen Funktionen unterscheiden, siehst du, dass es immer das Suchkriterium ist. Und genau das kannst du mit einer Predicate lösen, du gibst nämlich dann in die Search Methode die anonyme Methode hinein, die das Kriterium auf dein Item anwendet und dir sagt, obs passt oder nicht.

[OlafSt]

Okay, schlagendes Argument. Doch wo ist die Schleife, die durch alle Items iteriert ? Ich sehe da nur eine Vergleichsfunction - oder krieg ich da was nicht mit ?

[Edit]Ich bin ein Depp. Die Schleife mache ich selbst, ich Hirni :D
[Edit2] Sorry, ich kapiers doch nicht :-(
[Edit3] Etwa so:

Delphi-Quellcode:

function TMyObjectList<T>.Find(const Predicate: TPredicate<T>): T;
begin
     for Result in self do
          if Predicate(T) then
             exit;
     Result:=nil;
end;

function TMyObjectList<T>.FindByID(AID: integer): T;
begin
     self.Find(function(Obj: TDriverBase): boolean begin Result:=Obj.DriverID = AID; end);
end;

Na, ob das wirklich funktioniert :-~

[Stevie]

Delphi-Quellcode:

function TMyObjectList<T>.Search(const predicate: TPredicate<T>): T;
begin
  for Result in Self do
    if predicate(Result) then
      Exit;
end;

Delphi-Quellcode:

TPredicate<T>

ist in SysUtils definitiert.

[Mikkey]

Wenn Du die Arbeit nur einmal machen willst, dann mache doch eine Anleihe bei den .NET-Klassen, bzw. bei der Art, wie solche Dinge dort geregelt werden.

Wenn Du eine Searchable-List erzeugen willst, dann nimmst Du nur Mitgliederklassen an, die ein Interface "IComparable" implementieren. So kannst Du ohne Wissen um die konkrete Klasse die Objekte in Deiner Klasse sortieren. Hast Du Deine Liste in sortierter Form, dann ist auch eine binäre Suche leicht zu implementieren.

[OlafSt]

Oh mann, wie genial ist das denn.

[Union]

Zitat:

Zitat von Stevie (Beitrag 1267710)

Delphi-Quellcode:

function TMyObjectList<T>.Search(const predicate: TPredicate<T>): T;
begin
  for Result in Self do
    if predicate(Result) then
      Exit;
end;

Delphi-Quellcode:

TPredicate<T>

ist in SysUtils definitiert.

In der Funktion fehlt noch eine Zeile:

Delphi-Quellcode:

function TMyObjectList<T>.Search(const predicate: TPredicate<T>): T;
begin
  for Result in Self do
    if predicate(Result) then
      Exit;
  Result := nil // <<< Das muß rein sonst ist jede Suche erfolgreich mit dem letzten Element!
end;

[Stevie]

Zitat:

Zitat von Union (Beitrag 1267720)

Zitat:

Zitat von Stevie (Beitrag 1267710)

Delphi-Quellcode:

function TMyObjectList<T>.Search(const predicate: TPredicate<T>): T;
begin
  for Result in Self do
    if predicate(Result) then
      Exit;
end;

Delphi-Quellcode:

TPredicate<T>

ist in SysUtils definitiert.

In der Funktion fehlt noch eine Zeile:

Delphi-Quellcode:

function TMyObjectList<T>.Search(const predicate: TPredicate<T>): T;
begin
  for Result in Self do
    if predicate(Result) then
      Exit;
  Result := nil // <<< Das muß rein sonst ist jede Suche erfolgreich mit dem letzten Element!
end;

Hasse recht, sofern kein constraint auf T liegt, muss es allerdings

Delphi-Quellcode:

Result := Default(T);

heißen.

[OlafSt]

WTF ist ein constraint ? Irgendwie hab ich was verpaßt, glaub ich ;)

[Stevie]

Zitat:

Zitat von OlafSt (Beitrag 1267732)

WTF ist ein constraint ? Irgendwie hab ich was verpaßt, glaub ich ;)

Gucksu hier

[OlafSt]

Kapiert. Nun bekomme ich eine Fehlermeldung:

E2010 Inkompatible Typen: 'System.SysUtils.TPredicate<Unit1.TDriverList<T>.T >' und 'Procedure'

Code wie folgt:

Delphi-Quellcode:

   TDriverList<T: TDriverBase> = class(TObjectList<T>)
   private
   protected
   public
      function Find(const Predicate: TPredicate<T>): T;
      function FindByIMEI(AIMEI: string): T;
      function FindByID(AID: string): T;
   end;
[...]
{ TDriverList<T> }

function TDriverList<T>.Find(const Predicate: TPredicate<T>): T;
begin
     for Result in self do
          if Predicate(Result) then
             exit;
     Result:=nil;
end;

function TDriverList<T>.FindByID(AID: string): T;
begin
     Result:=Find(
        function(Obj: TDriverBase): boolean
        begin
             Result:=(Obj.DriverID = AID);
        end); //<- Hier bleibt der Compiler stehen
end;

Ehrlich gesagt sehe ich den Fehler nicht. Find will als Param ein TPredicate und meine anonyme Methode hat doch die passenden Params?

[Stevie]

Die Fehlermeldung gibt dir hier leider nicht den letzlich zielführenden Hinweis, dass eigentlich die Signaturen nicht passen.

Find will TPredicate<T> und du gibst nur eine für TPredicate<TDriverBase> passende Funktion hinein.
Da du bei der Definition ja den Constraint TDriverBase auf T gesetzt hast, kannst kannst du einfach das hier schreiben:

Delphi-Quellcode:

function TDriverList<T>.FindByID(AID: string): T;
begin
     Result:=Find(
        function(Obj: T): boolean
        begin
             Result:=(Obj.DriverID = AID); // durch den Constraint weiß der Compiler, dass Obj von TDriverBase ist und kann auf seine Member zugreifen.
        end);
end;

[Union]

Deine anonyme Funktion muß so aussehen:

Delphi-Quellcode:

function(Obj: T): boolean
        begin
             Result:=(Obj.DriverID = AID);
        end);

[Edit]Kein rotes Fenster?[/EDIT]

[OlafSt]

Dann war meine Vermutung, die ich insgeheim schon hatte, ja korrekt. In C# ist dieses "Mitdenken" des Compilers ja fast schon normal :D, bei Delphi weiß man nie so genau, wie weit Emba da Intelligenz eingebaut hat ;)

[Stevie]

Zitat:

Zitat von OlafSt (Beitrag 1267749)

In C# ist dieses "Mitdenken" des Compilers ja fast schon normal :D, bei Delphi weiß man nie so genau, wie weit Emba da Intelligenz eingebaut hat ;)

So kann man es auch ausdrücken. Aber die Sache ist gerade bei Generics eher die, dass C# Type Variance kann und Delphi nicht. Und dass man dort eher Lambdas benutzt, die sowieso Type Inference können.

[Sir Rufo]

Und dann gibt es noch

Delphi-Quellcode:

TDriverList<T:TDriverBase> = ...
  ...
  function FindById( const AID : string ) : T; overload;
  function FindById<TFind : T>( const AID : string ) : TFind; overload;
end;

function TDriverList<T>.FindById<TFind>( const AID : string ) : TFind;
begin
  Result := Find(
    function( Arg : T ) : Boolean
    begin
      Result := ( Arg is TFind ) and ( Arg.ID = AID );
    end ) as TFind;
end;

und du hast deine Spezialklassen auch typsicher abgebildet ;)

Delphi-Quellcode:

var
  MyDriverList : TDriverList<TDriverBase>;
  MySpecialDriver : TSpecialDriver;

MySpecialDriver := MyDriverList.FindById<TSpecialDriver>( '42' );