unit graphunit;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  tKnotens = class;
  tKnoten = class
  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(bm: tKnotens; i: string);
  end;

  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;

// tKnoten *********************************************************************

constructor tKnoten.create(i: string);
begin
  inherited create;
  _idStr:=i;
  _id:=strtoint('$'+i);
  sigs:=tKnotens.create;
end;

destructor tKnoten.destroy;
begin
  sigs.free;
end;

procedure tKnoten.addSig(bm: tKnotens; i: string);
begin
  sigs.findeKnoten(bm.findeKnoten(i));
end;

// tKnotens ********************************************************************

constructor tKnotens.create;
begin
  inherited create;
  _inhalt:=tList.create;;
end;

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(kn);
  if result<>kn then
    kn.free;
end;

function tKnotens.findeKnoten(kn: tKnoten): tKnoten; overload;
var
  mi,ma,i: longint;
begin
  mi:=0;
  ma:=count-1;
  while mi<=ma do begin
    i:=(mi+ma) div 2;
    if items[i].id<kn.id then begin
      mi:=i+1;
      continue;
    end;
    if items[i].id>kn.id then begin
      ma:=i-1;
      continue;
    end;
    if items[i].id=kn.id then begin
      result:=items[i];
      exit;
    end;
  end;
  if (mi>=0) and (mi<count) and (items[mi].id=kn.id) then begin
    result:=items[mi];
    exit;
  end;
  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;
  _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.