IMPLEMENTATION MODULE TableHandler;
 FROM InOut IMPORT Write,WriteLn,WriteInt;
 FROM Storage IMPORT ALLOCATE;

 CONST TableLength = 3000;

 TYPE
  TreePtr = POINTER TO Word;
  ListPtr = POINTER TO Item;
  Item = RECORD
          num: INTEGER;
          next: ListPtr
         END;
  Word = RECORD
          key: CARDINAL; (*table index*)
          first: ListPtr; (*list head*)
          left,right: TreePtr
         END;
  Table = TreePtr;

 VAR
  id: ARRAY [0..WordLength] OF CHAR;
  ascinx: CARDINAL;
  asc: ARRAY [0..TableLength-1] OF CHAR;

 PROCEDURE InitTable(VAR t: Table);
 BEGIN
  NEW(t); t^.right := NIL
 END InitTable;

 PROCEDURE Search(p: TreePtr): TreePtr;
  (*search node with name equal to id*)
  TYPE Relation = (less,equal,greater);
  VAR q: TreePtr;
   r: Relation; i: CARDINAL;

  PROCEDURE rel(k: CARDINAL): Relation;
  (*compare id with asc[k]*)
   VAR i: CARDINAL;
    R: Relation; x,y: CHAR;
   BEGIN
    i := 0; R := equal;
    LOOP
     x := id[i]; y := asc[k];
     IF CAP(x) # CAP(y) THEN EXIT END;
     IF x <= " " THEN RETURN R END;
     IF x < y THEN R := less ELSIF x > y THEN R := greater
     END;
     i := i+1; k := k+1;
    END;
    IF CAP(x) > CAP(y) THEN RETURN greater ELSE RETURN less
    END
   END rel;

  BEGIN
   q := p^.right; r := greater;
   WHILE q # NIL DO
    p := q; r := rel(p^.key);
    IF r=equal THEN RETURN p
    ELSIF r=less THEN q := p^.left
    ELSE q := p^.right
    END
   END;
   NEW(q); (*not found, hence insert*)
   IF q # NIL THEN
    WITH q^ DO
     key := ascinx; first := NIL; left := NIL; right := NIL;
    END;
    IF r=less THEN p^.left := q ELSE p^.right := q END;
    i := 0; (*copy identifier into asc table*)
    WHILE id[i] > " " DO
     IF ascinx = TableLength THEN
      asc[ascinx] := " "; id[i] := " "; overflow := 1;
     ELSE asc[ascinx] := id[i]; ascinx := ascinx+1; i := i+1;
     END
    END;
    asc[ascinx] := " "; ascinx := ascinx+1;
   END;
   RETURN q
  END Search;

  PROCEDURE Record(t: Table; VAR x: ARRAY OF CHAR; n: INTEGER);
   VAR p: TreePtr; q: ListPtr; i: CARDINAL;
  BEGIN
   i := 0;

   REPEAT
     id[i] := x[i]; 

      i := i+1;
   UNTIL (id[i-1] = " ") OR (i = WordLength);
   p := Search(t);
   IF p = NIL THEN
     overflow := 2;
   ELSE 
     NEW(q);
     IF q = NIL THEN
       overflow := 3;
     ELSE
       q^.num := n; q^.next := p^.first; p^.first := q;
     END
   END
  END Record;

  PROCEDURE Tabulate(t: Table);

   PROCEDURE PrintItem(p: TreePtr);
    CONST L = 6;
     N = (LineWidth-WordLength) DIV L;
    VAR ch: CHAR;
     i,k: CARDINAL; q: ListPtr;
    BEGIN
     i := WordLength+1; k := p^.key;
     REPEAT ch := asc[k];
      i := i-1; k := k+1; Write(ch);
     UNTIL ch <= " ";
     WHILE i > 0 DO
      Write (" "); i := i-1;
     END;
     q := p^.first; i := N;
     WHILE q # NIL DO
      IF i = 0 THEN
       WriteLn; i := WordLength+1;
       REPEAT Write(" "); i := i-1;
       UNTIL i = 0;
       i := N;
      END;
      WriteInt(q^.num,L); q := q^.next; i := i-1;
     END;
    WriteLn;
   END PrintItem;

   PROCEDURE TraverseTree(p: TreePtr);
   BEGIN
    IF p # NIL THEN
     TraverseTree(p^.left);
     PrintItem(p);
     TraverseTree(p^.right);
    END
   END TraverseTree;

  BEGIN
   WriteLn; TraverseTree(t^.right);
  END Tabulate;

 BEGIN
  ascinx := 0; id[WordLength] := " "; overflow := 0;
 END TableHandler.