_ALGORITHM ALLEY_
by Tom Swan

[LISTING ONE]

{ sqrroot.pas -- Algorithm #0: Square Root by Tom Swan }

program SquareRoot;
var 
  e, x, y, z: Real;
begin
  Write('Value? ');
  Readln(x);
  if (x <= 0) then
  begin
    Writeln('Error: Value <= 0');
    Exit
  end;
  y := 1.0;
  e := 5E-5;
  z := y * y;
  while abs(z - x) >= e do
  begin
    y := ((x / y) + y) / 2;
    z := y * y
  end;
  Write('The square root of ', x, ' = ', y)
end.


[LISTING TWO]

{ topsort.pas -- Algorithm #1: Topological Sort by Tom Swan }

program TopSort;

type
  PLeader = ^Leader;      { Pointer to Leader records }
  PFollower = ^Follower;  { Pointer to Follower records }
  TKey = String[40];      { Item keys read from file }

  Leader = record         { Leader record }
    key: TKey;            { Data in this record }
    count: Integer;       { Count of key's predecessors }
    next: PLeader;        { Next Leader record in list }
    chain: PFollower;     { Pointer to first Follower in chain }
  end;

  Follower = record       { Follower record }
    id: PLeader;          { Pointer to following Leader }
    next: PFollower;      { Pointer to next Follower in chain }
  end;

var
  head, tail: PLeader;    { Leader list head and tail pointers }
  itemCount: Integer;     { Total number of items in list }

{ Search list for item. Return pointer to its Leader record }
function Search(item: TKey): PLeader;
var
  h: PLeader;  { Pointer to head of list }
begin
  h := head; 
  tail^.key := item;  { Create sentinel at dummy record }
  while h^.key <> item do
    h := h^.next;
  if h = tail then
  begin  { Insert new item at head of list }
    new(tail);
    itemCount := itemCount + 1;
    h^.count := 0;     { No predecessors for new item yet }
    h^.chain := nil;   { No follower chain }
    h^.next := tail    { Link new record into list }
  end;
  Search := h          { Return pointer to item's record }
end; { Search }

{ Read data into list and construct follower chains }
procedure InputData;
var 
  pitem, item: TKey;  { Predecessor and item }
  a, b: PLeader;      { Leader record pointers}
  f: PFollower;       { Pointer to Follower record }
begin
  Writeln('Input data:');
  Readln(pitem);
  while not eof(input) do
  begin
    Readln(item);
    if not eof(input) then
    begin
      Writeln(pitem, ' << ', item);
      { Find or insert predecessor and item into list }
      a := Search(pitem);
      b := Search(item);
      { Construct follower and link into chain }
      New(f);
      f^.id := b;           { Address following item in chain }
      f^.next := a^.chain;  { Link new follower into chain }
      a^.chain := f;
      b^.count := b^.count + 1;  { Increment predecessor count }
      Readln;       { Read blank line between item pairs }
      Readln(pitem) { Read next item if any }
    end
  end
end; { InputData }

{ Find leader records with no predecessors }
procedure FindLeaders;
var
  a, b: PLeader;      { Leader record pointers}
begin
  a := head;
  head := nil;
  while a <> tail do
  begin
    b := a;
    a := a^.next;
    if b^.count = 0 then
    begin
      b^.next := head;
      head := b
    end
  end
end;

{ Sort and output records }
procedure OutputData;
var
  a, b : PLeader;
  c : PFollower;
begin
  Writeln; Writeln('Output data:');
  b := head;
  while b <> nil do
  begin
    Writeln(b^.key);
    itemCount := itemCount - 1;
    c := b^.chain;
    b := b^.next;
    while c <> nil do
    begin
      a := c^.id;
      a^.count := a^.count - 1;
      if a^.count = 0 then
      begin  { Insert a^ in b-list }
        a^.next := b;
        b := a
      end;
      c := c^.next
    end
  end
end; { OutputData }

begin { TopSort }
  New(head);
  tail := head;
  itemCount := 0;
  InputData;
  FindLeaders;
  OutputData;
  if itemCount <> 0 then
    Writeln('Error in data set: not partially ordered')
end.



Example 1

begin
  y <- 1; e <- 5E-5;
  z <- y * y;
  while |(z - x)| >= e do
  begin
    y <- ((x / y) + y) / 2;
    z <- y * y;
  end;
  write("The square root of ", x, " = ", y);
end.


Example 2

{ Initialize }
New(head);
tail <- head;

{ Input data }
Read(pitem);
while not Eof(input) do
begin
  Read(item);
  a <- Search(pitem);
  b <- Search(item);
  Create new follower record f;
  Identify f as item at b
  Link f into chain at a
  Read(pitem);
end;

{ Find leaders }
a <- head;
head <- nil;
while a <> tail do
begin { Search list }
  b <- a; a <- a^.next;
  if b has no predecessors then
  begin { Link b into list at head }
    b^.next <- head;
    head <- b;
  end;
end;

{ Sort and output }
b <- head;
while b <> nil do
begin { Search list }
  c <- b^.chain;
  b <- b^.next;
  while c <> nil do
  begin { Output item }
    Write(b);
    a <- c^.id;
    if a has no predecessors then
    begin { Link a into leader list at b }
      a^.next <- b;
      b <- a;
    end;
    c <- c^.next;
  end;
end;