1 files changed, 135 insertions, 24 deletions

diff --git a/graphunit.pas b/graphunit.pas
index ca8c58d..af85c17 100644
--- a/graphunit.pas
+++ b/graphunit.pas
@@ -8,27 +8,56 @@ uses
   Classes, SysUtils;
 
 type
+  tKnotens = class;
   tKnoten = class
-    id:   int64;
-    sigs: tList;
-    constructor create(i: int64);
+  private
+    _tag1,_tag2: longint;
+    _idStr:      string;
+    _id:         int64;
+  public
+    sigs: tKnotens;
+    property id: int64
+      read _id;
+    property idStr: string
+      read _idStr;
+    constructor create(i: string);
     destructor destroy; override;
-    procedure addSig(var bm: tList; i: int64);
+    procedure addSig(bm: tKnotens; i: string);
   end;
 
-function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
-function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
+  tKnotens = class
+  private
+    _inhalt: tList;
+    function rItem(idx: longint): tKnoten;
+    procedure wItem(idx: longint; itm: tKnoten);
+  public
+    property items[idx: longint]: tKnoten
+      read rItem
+      write wItem; default;
+
+    constructor create;
+    destructor destroy; override;
+    function findeKnoten(id: string): tKnoten; overload;
+    function findeKnoten(kn: tKnoten): tKnoten; overload;
+    function wasLiegtZwischen(wurzel,spitze: tKnoten; toleranz: longint; ausgabe: tStringList): longint;
+    procedure gibAlles(ausgabe: tStringList);
+    // Funktionen von tList
+    function count: longint;
+  end;
 
 implementation
 
 uses
   lowlevelunit;
 
-constructor tKnoten.create(i: int64);
+// tKnoten *********************************************************************
+
+constructor tKnoten.create(i: string);
 begin
   inherited create;
-  id:=i;
-  sigs:=tList.create;
+  _idStr:=i;
+  _id:=strtoint('$'+i);
+  sigs:=tKnotens.create;
 end;
 
 destructor tKnoten.destroy;
@@ -36,54 +65,136 @@ begin
   sigs.free;
 end;
 
-procedure tKnoten.addSig(var bm: tList; i: int64);
+procedure tKnoten.addSig(bm: tKnotens; i: string);
 begin
-  findeKnoten(sigs,findeKnoten(bm,i));
+  sigs.findeKnoten(bm.findeKnoten(i));
+end;
+
+// tKnotens ********************************************************************
+
+constructor tKnotens.create;
+begin
+  inherited create;
+  _inhalt:=tList.create;;
 end;
 
-function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
+destructor tKnotens.destroy;
+begin
+  _inhalt.free;
+  inherited destroy;
+end;
+
+function tKnotens.rItem(idx: longint): tKnoten;
+begin
+  result:=tKnoten(_inhalt[idx]);
+end;
+
+procedure tKnotens.wItem(idx: longint; itm: tKnoten);
+begin
+  _inhalt[idx]:=itm;
+end;
+
+function tKnotens.findeKnoten(id: string): tKnoten; overload;
 var
   kn: tKnoten;
 begin
   kn:=tKnoten.create(id);
-  result:=findeKnoten(bm,kn);
+  result:=findeKnoten(kn);
   if result<>kn then
     kn.free;
 end;
 
-function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
+function tKnotens.findeKnoten(kn: tKnoten): tKnoten; overload;
 var
   mi,ma,i: longint;
 begin
   mi:=0;
-  ma:=bm.count-1;
+  ma:=count-1;
   while mi<=ma do begin
     i:=(mi+ma) div 2;
-    if tKnoten(bm[i]).id<kn.id then begin
+    if items[i].id<kn.id then begin
       mi:=i+1;
       continue;
     end;
-    if tKnoten(bm[i]).id>kn.id then begin
+    if items[i].id>kn.id then begin
       ma:=i-1;
       continue;
     end;
-    if tKnoten(bm[i]).id=kn.id then begin
-      result:=tKnoten(bm[i]);
+    if items[i].id=kn.id then begin
+      result:=items[i];
       exit;
     end;
   end;
-  if (mi>=0) and (mi<bm.count) and (tKnoten(bm[mi]).id=kn.id) then begin
-    result:=tKnoten(bm[mi]);
+  if (mi>=0) and (mi<count) and (items[mi].id=kn.id) then begin
+    result:=items[mi];
     exit;
   end;
-  if (ma>=0) and (ma<bm.count) and (tKnoten(bm[ma]).id=kn.id) then begin
-    result:=tKnoten(bm[ma]);
+  if (ma>=0) and (ma<count) and (items[ma].id=kn.id) then begin
+    result:=items[ma];
     exit;
   end;
   if mi<>ma+1 then
     fehler('Bisektionsfehler: mi<>ma+1!');
   result:=kn;
-  bm.insert(mi,kn);
+  _inhalt.insert(mi,kn);
+end;
+
+function tKnotens.wasLiegtZwischen(wurzel,spitze: tKnoten; toleranz: longint; ausgabe: tStringList): longint;
+var
+  i,j:   longint;
+  neues: boolean;
+begin
+  wurzel:=findeKnoten(wurzel);
+  spitze:=findeKnoten(spitze);
+  for i:=0 to count-1 do begin
+    items[i]._tag1:=-1;
+    items[i]._tag2:=-1;
+  end;
+  wurzel._tag1:=0;
+  spitze._tag2:=0;
+  repeat
+    neues:=false;
+    for i:=0 to count-1 do begin
+      if items[i]._tag1>=0 then // von Wurzel erreichbar
+        for j:=0 to items[i].sigs.count-1 do
+          if (items[i].sigs[j]._tag1<0) or (items[i].sigs[j]._tag1 > items[i]._tag1+1) then begin
+            neues:=true;
+            items[i].sigs[j]._tag1:=items[i]._tag1+1;
+          end;
+      for j:=0 to items[i].sigs.count-1 do
+        if (items[i].sigs[j]._tag2>=0) and ((items[i]._tag2<0) or (items[i]._tag2 > items[i].sigs[j]._tag2+1)) then begin
+          neues:=true;
+          items[i]._tag2:=items[i].sigs[j]._tag2+1;
+        end;
+    end;
+  until not neues;
+
+  result:=-1;
+  for i:=0 to count-1 do begin
+    if (items[i]._tag1>=0) and
+       (items[i]._tag2>=0) and
+       ((result<0) or
+        (result>items[i]._tag1+items[i]._tag2)) then
+      result:=items[i]._tag1+items[i]._tag2;
+  end;
+  for i:=0 to count-1 do
+    if (items[i]._tag1>=0) and
+       (items[i]._tag2>=0) and
+       (result+toleranz>=items[i]._tag1+items[i]._tag2) then
+      ausgabe.add(inttostr(items[i]._tag1)+': '+items[i].idStr);
+end;
+
+procedure tKnotens.gibAlles(ausgabe: tStringList);
+var
+  i: longint;
+begin
+  for i:=0 to count-1 do
+    ausgabe.add('0x'+self[i].idStr);
+end;
+
+function tKnotens.count: longint;
+begin
+  result:=_inhalt.count;
 end;
 
 end.