From 5048c595141c06c64557df2bc2c0020d45add346 Mon Sep 17 00:00:00 2001
From: Erich Eckner <git@eckner.net>
Date: Mon, 19 Feb 2018 09:35:42 +0100
Subject: tools.pas: schnelleres Vergleichen

---
 tools.pas | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 55 insertions(+), 14 deletions(-)

diff --git a/tools.pas b/tools.pas
index 627f9c8..d58d6eb 100644
--- a/tools.pas
+++ b/tools.pas
@@ -20,12 +20,14 @@ type
     aktuell: tAktualitaet;
   end;
   tDateienMitDaten = class(tFPList)
+    istSortiert: boolean;
     function rItem(idx: longint): tDateiMitDatum; inline;
     procedure wItem(idx: longint; neu: tDateiMitDatum); inline;
   public
     property items[idx: longint]: tDateiMitDatum
       read rItem
       write wItem; default;
+    constructor create;
     procedure mrProper;
     function add(neu: tDateiMitDatum): longint;
     function last: tDateiMitDatum;
@@ -35,6 +37,7 @@ type
     function toMyStringList: tMyStringList;
     function finde(name: string; wirdAktualitaet: tAktualitaet = aNichtVorhanden): tDateiMitDatum; overload; inline;
     function finde(name: string; out istNeu: boolean; wirdAktualitaet: tAktualitaet = aNichtVorhanden): tDateiMitDatum; overload; inline;
+    procedure sortiereNachNamen;
   end;
 
 function min(a1,a2: tAktualitaet): tAktualitaet; inline; overload;
@@ -49,6 +52,7 @@ function escape(s,toe,es: string): string;
 function escapeStringToRegex(s: string; typ: tRegexTyp; extras: string = ''): string; inline;
 procedure ersetzeAlleVorkommen(var worin: string; was,wodurch: string);
 function unterVerzeichnisRegex(dateien: array of const): string;
+function vergleicheNamenVonDateienMitDaten(item1,item2: pointer): integer;
 
 // Routinen für sha512-Prüfsummen
 
@@ -62,6 +66,12 @@ uses
 
 // tDateienMitDaten ************************************************************
 
+constructor tDateienMitDaten.create;
+begin
+  inherited create;
+  istSortiert:=true;
+end;
+
 function tDateienMitDaten.rItem(idx: longint): tDateiMitDatum;
 begin
   result:=tDateiMitDatum(get(idx));
@@ -70,6 +80,7 @@ end;
 procedure tDateienMitDaten.wItem(idx: longint; neu: tDateiMitDatum);
 begin
   put(idx,neu);
+  istSortiert:=false;
 end;
 
 procedure tDateienMitDaten.mrProper;
@@ -84,6 +95,7 @@ end;
 function tDateienMitDaten.add(neu: tDateiMitDatum): longint;
 begin
   result:=inherited add(neu);
+  istSortiert:=false;
 end;
 
 function tDateienMitDaten.last: tDateiMitDatum;
@@ -93,17 +105,18 @@ end;
 
 function tDateienMitDaten.gleicheNamenWie(dmd: tDateienMitDaten): boolean;
 var
-  i,j: longint;
+  i: longint;
 begin
   result:=count=dmd.count;
   if not result then
     exit;
-  for i:=0 to count-1 do begin
-    result:=false;
-    for j:=0 to dmd.count-1 do
-      result:=result or (items[i].name = dmd[j].name);
-    if not result then exit;
-  end;
+  sortiereNachNamen;
+  dmd.sortiereNachNamen;
+  result:=false;
+  for i:=0 to count-1 do
+    if items[i].name <> dmd[i].name then
+      exit;
+  result:=true;
 end;
 
 function tDateienMitDaten.toString: string;
@@ -147,21 +160,44 @@ end;
 
 function tDateienMitDaten.finde(name: string; out istNeu: boolean; wirdAktualitaet: tAktualitaet = aNichtVorhanden): tDateiMitDatum;
 var
-  i: longint;
+  li,re,i: longint;
 begin
+  sortiereNachNamen;
   istNeu:=false;
-  for i:=0 to count-1 do
-    if items[i].name=name then begin
-      result:=items[i];
-      exit;
-    end;
-  add(tDateiMitDatum.create);
+  li:=0;
+  re:=count-1;
+  while li<=re do begin
+    i:=(li+re) div 2;
+    case vergleicheStrings(items[i].name,name) of
+      -1: li:=i+1;
+      1: re:=i-1;
+      0: begin
+        li:=i;
+        re:=i;
+        break;
+      end;
+    end{of case};
+  end;
+  if li=re then begin
+    assert(items[li].name=name,'Fehler in Bisektion: '''+items[li].name+'''<>'''+name+'''!');
+    result:=items[li];
+    exit;
+  end;
+  assert(li=re+1,'Fehler in Bisektion: '+intToStr(li)+'<>'+intToStr(re)+'+1!');
+  insert(li,tDateiMitDatum.create);
   istNeu:=true;
   result:=last;
   last.name:=name;
   last.aktuell:=wirdAktualitaet;
 end;
 
+procedure tDateienMitDaten.sortiereNachNamen;
+begin
+  if not istSortiert then
+    sort(@vergleicheNamenVonDateienMitDaten);
+  istSortiert:=true;
+end;
+
 // allgemeine Funktionen *******************************************************
 
 function min(a1,a2: tAktualitaet): tAktualitaet;
@@ -482,6 +518,11 @@ begin
   delete(result,1,1);
 end;
 
+function vergleicheNamenVonDateienMitDaten(item1,item2: pointer): integer;
+begin
+  result:=vergleicheStrings(tDateiMitDatum(item1).name,tDateiMitDatum(item2).name);
+end;
+
 // Routinen für sha512-Prüfsummen
 
 var
-- 
cgit v1.2.3-70-g09d2