Unit Voorlopig;
{
  EDGE BASED INSERT AND LOOKUP
  ============================
}
INTERFACE

type
  edge = record
    A,B : integer; { Endpoints }
    g : Longint; { for sorting }
  end;
  edges = array of edge;
{
  o---->----o   Orientation of the edges
  A         B   is essential for further
  o----<----o   processing in Zijdelings
  B         A                 ----------
}
var
  zijde : edges;
  boven : integer;

function invoegen(i,j : integer) : boolean; { insert in sorted array }
function BinZoek(T : edge; var n : integer) : boolean; { binary search }
procedure test; { Just a test }

IMPLEMENTATION

function BinZoek(T : edge; var n : integer) : boolean;
{
  Binary Search (Wikipedia)
  -------------------------
  Edge present (BinZoek) in
  sorted array (zijde) at (n)
}
var
  E,L,R,m : integer;
  OK : boolean;
begin
  L := 0;
  R := boven-1;
  OK := false;
  E := Length(zijde);
  T.g := E*T.A+T.B;
  while L <= R do
  begin
    m := ((L + R) div 2);
    if zijde[m].g < T.g then
      L := m + 1
    else if zijde[m].g > T.g then
      R := m - 1
    else begin
      OK := true; n := m; Break;
    end;
  end;
  BinZoek := OK;
end;

function invoegen(i,j : integer) : boolean;
{
  Sorted edges (i,j) Insert
}
var
  E,k,m,L,nop: integer;
  g,h : Longint;
  z : edge;
begin
  E := Length(zijde);
  z.A := i; z.B := j; z.g := i*E+j;
{ First entry }
  if boven = 0 then
  begin
    zijde[0] := z; boven := 1;
    invoegen := true; Exit;
  end;
  g := E*i + j;
  h := E*zijde[boven-1].A + zijde[boven-1].B;
{ On top is larger }
  if g > h then
  begin
    boven := boven + 1;
    zijde[boven-1] := z;
    invoegen := true; Exit;
  end;
{ Equal entry not done }
  if BinZoek(z,nop) then
  begin
    invoegen := false; Exit;
  end;
{ On top is smaller }
  m := boven; L := 0;
  for k := 1 to m do
  begin
    h := E*zijde[m-k].A + zijde[m-k].B;
    if g < h then
      zijde[m-k+1] := zijde[m-k]
    else Break;
    L := k;
  end;
{ Finishing touches }
  zijde[m-L+1] := zijde[m-L];
  zijde[m-L] := z;
  boven := boven + 1;
  invoegen := true;
end;

procedure test;
{
  Just a Test
}
const
  E : integer = 27;
var
  k,i,j,m : integer;
  ff : edge;
  OK : boolean;
begin
  SetLength(zijde,E);
  for k := 0 to E-1 do
  begin
    zijde[k].A := 0; zijde[k].B := 0;
    zijde[k].g := 0;
  end;
  boven := 0;
  for k := 0 to E-1 do
  begin
    i := Round(10*Random); j := Round(10*Random);
    if i = j then Continue;
    Writeln(i:3,j:3);
    invoegen(i,j);
    for m := 0 to boven-1 do
    begin
      Writeln(zijde[m].A:3,zijde[m].B:3,zijde[m].g:6);
    end;
    Writeln;
  { Readln; }
  end;
  Writeln(boven,' < ',E);
  Writeln;
  ff.A := 7;
  for k := 0 to 9 do
  begin
    ff.B := k;
    Write(ff.A:3,ff.B:3);
    m := -1;
    OK := BinZoek(ff,m);
    Writeln(OK:6,m:3);
  end;
end;

END.