StringListe mit Custom-Sortierung

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Antworten
braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

StringListe mit Custom-Sortierung

Beitrag von braunbär »

Mir ist nicht ganz klar, wie das funktioniert.
Wenn ich es richtig verstanden habe, kann ich nur der CustomSort-Routine eine Callback-Funktion zum Vergleichen von zwei Elementen übergeben.
Bedeutet das, dass erstens eine solche Stringliste nach dem Einfügen eines neuen Strings komplett neu sortiert werden muss, und dass zweitens das find in so einer Stringliste nicht binär suchen kann? Oder merkt sich die Stringliste irgendwo, welche Vergleichsroutine sie verwenden muss?

Ich verstehe nicht recht, warum man den Callback zum Vergleichen nicht als Property der Stringliste ablegt statt als Parameter einer Customsort-Funktion, das wäre doch in jeder Hinsicht logischer und einfacher?

Benutzeravatar
Ally
Beiträge: 262
Registriert: Do 11. Jun 2009, 09:25
OS, Lazarus, FPC: Win und Lazarus Stable release
CPU-Target: x64

Re: StringListe mit Custom-Sortierung

Beitrag von Ally »

Hallo braunbär,

mit einer ListView sieht das etwa so aus:

Code: Alles auswählen

 
function CustomSortProc(I1, I2: TListItem; Spalte: integer): integer; stdcall;
begin
  Result := 1;
 
  if Spalte = 2 then // Datum
    Result := CompareValue(StrToDateTime(I1.subitems[2]), StrToDateTime(I2.subitems[2]));
  end;
 
//  if Spalte = 3 then
//    .............
//    .........
//  if Spalte = 4 then
//    ............
//    .........
end;
 
// Aufruf 
SortSpalte := 2;
ListView1.CustomSort(@CustomSortProc, SortSpalte);
 


anschließend ist die Liste komplett umsortiert und kann ganz normal weiterverwendet werden.

Gruß Roland

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: StringListe mit Custom-Sortierung

Beitrag von braunbär »

:?:
Ich verstehe nicht recht, was du damit sagen willst.
Sicher kannst du eine Listview genauso wie eine Stringliste per Customsort sortieren, in der Listview steckt ja auch nur eine Stringliste.

Im Gegensatz zu einer "normal" sortierten Liste werden aber Elemente, die neu dazu kommen, offenbar nicht richtig einsortiert, du kannst diese Listview also eben nicht "normal" weiterverwenden, sondern musst dich bei jedem neuen Element selbst darum kümmern, dass die Sortierreihenfolge erhalten bleibt. Wenn der Customsort Callback bei der Stringliste fix hinterlegt wäre, müsstest du das nicht.

wp_xyz
Beiträge: 4864
Registriert: Fr 8. Apr 2011, 09:01

Re: StringListe mit Custom-Sortierung

Beitrag von wp_xyz »

Ich denke, das Standard-Sortierverfahren, das bei "Sorted = true" für die laufende Einsortierung neuer Einträge verwendet wird, ist in TStringList fest vorgegeben, wie folgende Code-Auszüge zeigen:

Code: Alles auswählen

function TStringList.Add(const S: string): Integer;
begin
  If Not (SortStyle=sslAuto) then
    Result:=FCount
  else
    If Find (S,Result) then  // --> weiter bei "Find"
 
...
 
function TStringList.Find(const S: string; out Index: Integer): Boolean;
var
  L, R, I: Integer;
  CompareRes: PtrInt;
begin
  Result := false;
  Index:=-1;
  if Not Sorted then
    Raise EListError.Create(SErrFindNeedsSortedList);
  // Use binary search.
  L := 0;
  R := Count - 1;
  while (L<=R) do
  begin
    I := L + (R - L) div 2;
    CompareRes := DoCompareText(S, Flist^[I].FString);   // ---> weiter bei DoCompareText
 
...
 
function TStringList.DoCompareText(const s1, s2: string): PtrInt;
begin
  if FCaseSensitive then
    result:=AnsiCompareStr(s1,s2)
  else
    result:=AnsiCompareText(s1,s2);
end;

Zum Glück ist DoCompareText virtuell. Das bedeutet, du kannst deine Sonder-Sortier-Routine fest einbauen, indem du DoCompareText überschreibst.

Dass das ganze funktioniert, sieht man an dem folgenden Beispiel (Form mit Memo und Button): Hier werden zufällige Zahlen bis 20 erzeugt. Die Sortierung von TStringList sortiert den String '2' hinter allen '10'er Strings ein. Ableitung einer modifizierten StringList, die zum Vergleichen die Strings in Zahlen konvertiert, dagegen sortiert die '2' nach '1' und vor den '10'ern ein.

Code: Alles auswählen

unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls;
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    List: TStringList;
 
  public
 
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.lfm}
 
uses
  Math;
 
{ TForm1 }
 
function RandomNumberAsStr(Max: Integer): String;
begin
  Result := IntToStr(Random(Max + 1));
end;
 
type
  TMyStringList = class(TStringList)
  protected
    function DoCompareText(const s1, s2: string): PtrInt; override;
  end;
 
function TMystringList.DoCompareText(const s1, s2: String): PtrInt;
var
  n1, n2: Integer;
begin
  n1 := StrToInt(s1);
  n2 := StrToInt(s2);
  Result := CompareValue(n1, n2);
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
  List.Add(RandomNumberAsStr(20));
  Memo1.Lines.Assign(List);
end;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  List := TMyStringList.Create;   // neues Sortierverhalten
//  List := TStringList.Create;  // Standard-Sortierung
  List.Sorted := true;
end;
 
end.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: StringListe mit Custom-Sortierung

Beitrag von braunbär »

Ok, d.h. wenn man eine stabile custom Sortierung will, muss man eine neue Klasse von TStringList ableiten, und die Customsort Routine ist mehr oder weniger für die Würst :D

Eigentlich schade, weil es wäre mit einer Callback-Property für die Sortierung viel einfacher, und dazu sogar im Standardfall (geringfügig) schneller, weil der Overhead für den Zugriff auf die virtual Methode wegfallen würde - bei virtual Methoden muss ja zur Laufzeit bei jedem Aufruf erneut die richtige Methode an Hand der aktuellen Klasse ausgewählt werden.

Dazu kommt, dass man Komponenten, die auf TStringlist aufbauen, nicht so leicht statt TStringList eine andere, von TStringList abgeleitete Klasse unterjubeln kann. Bei denen muss man also immer bei jeder Datenänderung neu sortieren.

wp_xyz
Beiträge: 4864
Registriert: Fr 8. Apr 2011, 09:01

Re: StringListe mit Custom-Sortierung

Beitrag von wp_xyz »

braunbär hat geschrieben:Ok, d.h. wenn man eine stabile custom Sortierung will, muss man eine neue Klasse von TStringList ableiten, und die Customsort Routine ist mehr oder weniger für die Würst :D

Eigentlich schade, weil es wäre mit einer Callback-Property für die Sortierung viel einfacher, und dazu sogar im Standardfall (geringfügig) schneller, weil der Overhead für den Zugriff auf die virtual Methode wegfallen würde - bei virtual Methoden muss ja zur Laufzeit bei jedem Aufruf erneut die richtige Methode an Hand der aktuellen Klasse ausgewählt werden.

Dazu kommt, dass man Komponenten, die auf TStringlist aufbauen, nicht so leicht statt TStringList eine andere, von TStringList abgeleitete Klasse unterjubeln kann. Bei denen muss man also immer bei jeder Datenänderung neu sortieren.

Mache einen Feature Request im BugTracker und hänge einen Patch an. Achte darauf, dass das bisherige Verhalten im Default-Fall beibehalten bleibt. Dann sehe ich durchaus Chancen, dass sowas angenommen wird.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: StringListe mit Custom-Sortierung

Beitrag von braunbär »

Werde ich machen, auch wenn das wieder eine neue Herausforderung ist, bisher habe ich mich um die Verwendung von Repositories wie GIT herumgeschummelt - aber irgendwann wird es doch Zeit :D

Einen Patch erstellen muss ich prinzipiell mit Lazarus Trunc, wenn ich das richtig verstanden habe. Ich werde das einmal programmieren und testen, wahrscheinlich tauchen dann noch Fragen auf, wenn ich so weit bin, den Patch hochzuladen.

wp_xyz
Beiträge: 4864
Registriert: Fr 8. Apr 2011, 09:01

Re: StringListe mit Custom-Sortierung

Beitrag von wp_xyz »

Noch ein bisschen komplizierter, denn TStringList ist in Classes und das gehört zu FPC - das heißt, du brauchst auch FPC-trunk.Wenn's gar nicht anders geht, dann poste den neuen TStringList-Code hier, und ich erzeugt das patch-File für dich.

P.S. Ich sehe gerade, in classesh.inc gibt es einen per IFDEF ausgeklammerten Teil, in dem eine TStringList-Variante eingeführt wird, mit property OnCompareText. Der Teil ist nur aktiv wenn das Define FPC_TESTGENERICS gesetzt ist.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: StringListe mit Custom-Sortierung

Beitrag von braunbär »

Tatsächlich - da haben sie etwas in der Richtung offenbar schon vorbereitet - aber leider auch eher ungeschickt konzipiert (nach dem Prinzip, möglichst nahe am Bestehenden bleiben, was aber hier nicht gut ist), weil zum Vergleichen von zwei Strings brauchst du keine Klassenmethode, sondern nur eine einfache function - und nachdem das letztlich auch dazu dient, dass man eben keine Klasse von TStringList ableiten braucht, sehe ich nicht, in welcher Klasse man diese Vergleichsmethode deklarieren soll (Man kann natürlich irgend eine beliebige Klasse hernehmen, die man gerade zur Hand hat, aber sonderlich sinnvoll ist das nicht).

Und wenn FOnCompareText statt einer Klassenmethode eine einfache Funktion speichert, dann braucht man doCompareText gar nicht, sondern man könnte statt dessen im Setter von FOnComparetext und im Setter von FCasesensitive direkt in einer weiteren private-Variable gleich den Zeiger auf die richtige Vergleichsfunktion eintragen - je nachdem auf FOnCompareText wenn <>nil, und sonst auf AnsiCompareStr oder AnsiCompareText abhängig von FCaseSensitive - und diese Funktion bei jedem Vergleich direkt aufrufen.

Wie ist eigentlich die übliche Vorgangsweise - wie lange dauert es normalerweise, bis so ein als "Test" deklarierter Versionszweig in der Standard-Runtime landet?

wp_xyz
Beiträge: 4864
Registriert: Fr 8. Apr 2011, 09:01

Re: StringListe mit Custom-Sortierung

Beitrag von wp_xyz »

braunbär hat geschrieben:Tatsächlich - da haben sie etwas in der Richtung offenbar schon vorbereitet - aber leider auch eher ungeschickt konzipiert (nach dem Prinzip, möglichst nahe am Bestehenden bleiben, was aber hier nicht gut ist), weil zum Vergleichen von zwei Strings brauchst du keine Klassenmethode, sondern nur eine einfache function - und nachdem das letztlich auch dazu dient, dass man eben keine Klasse von TStringList ableiten braucht, sehe ich nicht, in welcher Klasse man diese Vergleichsmethode deklarieren soll (Man kann natürlich irgend eine beliebige Klasse hernehmen, die man gerade zur Hand hat, aber sonderlich sinnvoll ist das nicht).

Nein, genau das ist es was man braucht. Denn so kannst du die Sortierroutine als Methode deines Formulars implementieren und hast maximale Flexibilität. Genau auf diese Art und Weise sind Events implementiert, und das OnCompareText ist hier nichts anderes als ein Event.

braunbär hat geschrieben:Und wenn FOnCompareText statt einer Klassenmethode eine einfache Funktion speichert, dann braucht man doCompareText gar nicht, sondern man könnte statt dessen im Setter von FOnComparetext und im Setter von FCasesensitive direkt in einer weiteren private-Variable gleich den Zeiger auf die richtige Vergleichsfunktion eintragen - je nachdem auf FOnCompareText wenn <>nil, und sonst auf AnsiCompareStr oder AnsiCompareText abhängig von FCaseSensitive - und diese Funktion bei jedem Vergleich direkt aufrufen.

DoCompareText wird vom Vorfahren TStrings für IndexOf aufgerufen. Daher kann man darauf nicht verzichten.

braunbär hat geschrieben:Wie ist eigentlich die übliche Vorgangsweise - wie lange dauert es normalerweise, bis so ein als "Test" deklarierter Versionszweig in der Standard-Runtime landet?

Darauf würde ich mich nicht verlassen, die älteste Version, die ich mir angesehen habe, ist fpc 2.6.4, und da steht die Generics-Version auch schon drinnen, und in fpc-trunk ist es immer noch so...
Ich würde für einen Feature Request das OnCompareText-Event in die aktuelle Nicht-generics-Version einbauen, du musst eigentlich nur die entsprechenden Code-Stellen aus dem ELSE-Zweig in den IFNDEF-Zweig reinkopieren und entsprechend anpassen.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: StringListe mit Custom-Sortierung

Beitrag von braunbär »

Mal sehen, wie ich dazu komme. Jetzt steht nämlich eine 3wöchige Reise zwecks Totalrenovierung meiner Zähne an (hier in Österreich nicht zu bezahlen, da würde das einen Wagen der gehobenen Mittelklasse kosten).
Ich nehme mir zwar einen Notebook mit allem drum und dran mit, aber wieviel Lust auf Programmieren ich in der Zeit wirklich haben werde, wenn ich jeden zweiten Tag den Zahnarzt genießen darf, weiss ich noch nicht. Es kann also gut sein, dass ihr erst in 3-4 Wochen wieder von mir hört :)

Antworten