unit graphunit;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  tKnoten = class
    id:   int64;
    sigs: tList;
    constructor create(i: int64);
    destructor destroy; override;
    procedure addSig(var bm: tList; i: int64);
  end;

function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;

implementation

uses
  lowlevelunit;

constructor tKnoten.create(i: int64);
begin
  inherited create;
  id:=i;
  sigs:=tList.create;
end;

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

procedure tKnoten.addSig(var bm: tList; i: int64);
begin
  findeKnoten(sigs,findeKnoten(bm,i));
end;

function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
var
  kn: tKnoten;
begin
  kn:=tKnoten.create(id);
  result:=findeKnoten(bm,kn);
  if result<>kn then
    kn.free;
end;

function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
var
  mi,ma,i: longint;
begin
  mi:=0;
  ma:=bm.count-1;
  while mi<=ma do begin
    i:=(mi+ma) div 2;
    if tKnoten(bm[i]).id<kn.id then begin
      mi:=i+1;
      continue;
    end;
    if tKnoten(bm[i]).id>kn.id then begin
      ma:=i-1;
      continue;
    end;
    if tKnoten(bm[i]).id=kn.id then begin
      result:=tKnoten(bm[i]);
      exit;
    end;
  end;
  if (mi>=0) and (mi<bm.count) and (tKnoten(bm[mi]).id=kn.id) then begin
    result:=tKnoten(bm[mi]);
    exit;
  end;
  if (ma>=0) and (ma<bm.count) and (tKnoten(bm[ma]).id=kn.id) then begin
    result:=tKnoten(bm[ma]);
    exit;
  end;
  if mi<>ma+1 then
    fehler('Bisektionsfehler: mi<>ma+1!');
  result:=kn;
  bm.insert(mi,kn);
end;

end.