(* Cross reference as above, but using a hash table instead
  of a binary tree to store the words encountered. *)

(***************************************************************************************)
(* MODULE crossref--This module is a cross reference generator.  A file which is       *)
(* specified by the user is read and a cross reference table of all the words is built.*)
(* A word consists of a letter and any combination of letters and digits thereafter    *)
(* until a separator, i.e. blanks, ends of lines, special characters, is read.  Quotes *)
(* and comments are ignored.  The cross reference table is a hash table which stores   *)
(* the words and the number of the line on which the word appeared.  When the table    *)
(* is generated, its contents are printed on the screen.  This program is the MODULA-2 *)
(* translation of the PASCAL program 11.2.                                             *)



MODULE crossref;

FROM InOut IMPORT                              (* get necessary i/o files             *)
    Read, WriteString, Write, WriteLn, WriteCard, OpenInput, CloseInput, Done;
FROM Storage IMPORT                            (* get NEW procedure                   *)
    ALLOCATE;

CONST  ff         = 14c;                       (* clear the screen constant           *)
      eol        = 36c;                       (* end of line constant                *)
      quote      = 42c;                       (* double quote mark                   *)
      wordlen    = 10;                        (* maximum word length                 *)
      numperline = 8;                         (* no of line numbers per display line *)
      digpernum  = 6;                         (* maximum number of digits per number *)
      maxline    = 9999;                      (* maximum number of lines in file     *)
      prime      = 997;                       (* number of hash table entries        *)
      blank      = " ";                       (* blank character constant            *)
      filetype   = "TEXT";                    (* default filename extension          *)

TYPE   index    = [0..prime];                  (* range of hash table                 *)
      alfa     = ARRAY[1..wordlen] OF CHAR;   (* word string                         *)
      relation = (equal,less,greater);        (* used for string comparisons         *)
      itemref  = POINTER TO item;
      word     = RECORD                       (* hash table entries                  *)
                   key        : alfa;         (* word found in text                  *)
                   first, last: itemref;      (* pointer to cross reference list     *)
                   follow     : index         (* hash number of next entry           *)
                 END;
      item     = RECORD                       (* cross reference list                *)
                   lineno: [0..maxline];      (* line number word occurred on        *)
                   next  : itemref            (* pointer to next item in list        *)
                 END;

VAR    i        : index;                       (* index to hash table                 *)
      top      : index;                       (* current hash table entry            *)
      idcntr   : INTEGER;                     (* index to id array                   *)
      id       : alfa;                        (* contains the current word           *)
      free     : alfa;                        (* blank word                          *)
      table    : ARRAY [0..prime] OF word;    (* hash table                          *)
      current  : CARDINAL;                    (* current line number                 *)
      ch       : CHAR;                        (* current character                   *)
      tablefull: BOOLEAN;                     (* flags if table gets full            *)


PROCEDURE compare(j,k:alfa):relation;
(**************************************************************************************)
(* This function compares the two strings j and k to see how they compare.  If j = k  *)
(* then the value of equal is returned.  If j < k then the value is less is returned  *)
(* and if j > k tthen the value greater is returned.                                  *)
(**************************************************************************************)


VAR compvalue : relation;                     (* function value                       *)
   through   : BOOLEAN;                      (* flags when through with loop         *)
   i         : INTEGER;                      (* array index                          *)

BEGIN
 compvalue := equal;                         (* initializations                      *)
 i         := 1;
 through   := FALSE;
 WHILE (NOT through) & (i <= 10) DO          (* compare the two strings              *)
   IF CAP(j[i]) = CAP(k[i]) THEN
     INC(i)
   ELSE
     through := TRUE;
     IF CAP(j[i]) < CAP(k[i]) THEN
       compvalue := less
     ELSE
       compvalue := greater
     END
   END
 END;
 RETURN compvalue
END compare;



PROCEDURE search():BOOLEAN;
(**************************************************************************************)
(* This function searches the hash table to see if an entry for the current word      *)
(* already exists.  This is done by calculating the hash value of the current word.   *)
(* If no entry exists at the hash value slot in the table, then an entry is created   *)
(* for that word and an item list created.  If the entry already exists, then only a  *)
(* new item node is created and added to the item list.  If the hash slot is already  *)
(* occupied by a different word, then the hash table is searched for an empty slot.   *)
(* If one is found, then it is filled in with the current word, etc.  If no empty     *)
(* slot can be found, then a message is printed indicating table overflow and the     *)
(* procedure quits, returning the value of FALSE.                                     *)
(**************************************************************************************)

VAR  hash         : CARDINAL;                   (* contains hash value                *)
    addvalue     : index;                      (* contains search increment value    *)
    done         : BOOLEAN;                    (* flags when finished                *)
    full         : BOOLEAN;                    (* flags if table is full             *)
    x            : itemref;                    (* pointer to current item list       *)
    compvalue    : relation;                   (* contains result of compare         *)


BEGIN
 full     := FALSE;                            (* initialize                         *)
 hash     := 0;
 done     := FALSE;
 addvalue := 1;
 NEW(x);                                       (* get a new item list node           *)
 x^.lineno  := current;                        (* fill in current line number        *)
 x^.next := NIL;                               (* set next link to nil               *)
 FOR i := 1 TO wordlen                         (* calculate hash value               *)
   DO
    hash := (hash + ORD(id[i])) MOD prime
   END;
 REPEAT                                        (* continue searching until done      *)
   compvalue := compare(id, table[hash].key);  (* compare id to key to see if equal  *)
   IF compvalue = equal THEN                   (* if word entry already exists       *)
     done := TRUE;                             (* flag to end loop                   *)
     table[hash].last^.next := x;              (* link last item node to new node    *)
     table[hash].last := x                     (* link table pointer to new last node*)
   ELSE
     compvalue := compare(free,table[hash].key);
     IF compvalue = equal THEN                 (* if no entry exists                 *)
       WITH table[hash] DO
         key := id;                            (* fill in current word               *)
         first := x;                           (* link to item node                  *)
         last  := x;
         follow := top                         (* fill in last hash table entry      *)
       END;
       top  := hash;                           (* set to current hash table entry    *)
       done := TRUE
     ELSE                                      (* collision occurred                 *)
       hash := hash + addvalue;                (* incrmt hash to check next entry    *)
       addvalue := addvalue + 2;               (* increment displacement             *)
       IF  hash >= prime THEN                  (* if hash value greater than length  *)
       hash := hash - prime                    (* reset hash value                   *)
       END;
       IF addvalue = prime THEN                (* if table is full                   *)
         done := TRUE;                         (* flag that search is through        *)
         full := TRUE;                         (* flag that table is full            *)
         WriteString("Table Overflow");
         WriteLn
       END
     END
   END
 UNTIL done;
 RETURN full
END search;


PROCEDURE printtable;
(**************************************************************************************)
(* This procedure prints out the cross reference table.  It lists each word and the    *)
(* line numbers on which that word occurred.  Printtable has an internal procedure    *)
(* printword that handles printing the word and its line references.  The cross      *)
(* reference table is printed out in alphabetical order.                              *)
(**************************************************************************************)

VAR  hold      : index;                          (* contains the current entry index  *)
    least     : index;                          (* contains index to least word      *)
    move      : index;                          (* used to search for least word     *)
    compvalue : relation;                       (* contains compare result           *)

PROCEDURE printword(w: word);


 VAR numcnt: INTEGER;                           (* keeps track line nos on screen    *)
     x     : itemref;                           (* pointer to current item node      *)

 BEGIN
   Write(blank);
   WriteString(w.key);
   x := w.first;
   numcnt := 0;
   REPEAT                                       (* do until all line numbers printed *)
     IF numcnt = numperline THEN                (* if need a new line for line nos   *)
       numcnt := 0;                             (* reset counter                     *)
       WriteLn;
       Write(blank);
       WriteString(free)
     END;
     INC(numcnt);
     WriteCard(x^.lineno,digpernum);            (* write the line number             *)
     Write(blank);                              (* move to next item node            *)
     x := x^.next
   UNTIL x = NIL;
   WriteLn;
 END printword;

BEGIN
 hold := top;                                   (* start at last entry to be added   *)
 WHILE hold <> prime                            (* do for all of the table           *)
   DO
     least := hold;                             (* initialize for alphabetic search  *)
     move  := table[hold].follow;
     WHILE move <> prime                        (* search table for least entry      *)
       DO
         compvalue := compare(table[move].key,table[least].key);
         IF compvalue = less THEN
           least := move
         END;
         move := table[move].follow
       END;
     printword(table[least]);                    (* print the word and its line nos  *)
     IF least <> hold THEN                       (* make sure entry won't get printed*)
       table[least].key   := table[hold].key;
       table[least].first := table[hold].first;
       table[least].last  := table[hold].last
     END;
     hold := table[hold].follow                  (* move to the next entry           *)
    END
END printtable;


BEGIN                                              (* ***MAIN PROCEDURE***            *)

 current   := 0;                                  (* initialize                      *)
 top       := prime;
 tablefull := FALSE;
 FOR i := 1 TO wordlen DO
   free[i] := blank
 END;
 OpenInput(filetype);                             (* request filename and open file  *)
 IF NOT Done THEN                                 (* if file does not exist quit     *)
   WriteString("Error--file DK.file.TEXT does not exist")
 ELSE                                             (* otherwise continue              *)
   FOR i := 1 TO prime DO                         (* more initialization             *)
     table[i].key := free
   END;
   Read(ch);                                      (* get the first character         *)
   WHILE NOT tablefull DO                         (* do while table is not full      *)
     WHILE Done DO                                (* do while end of file not reached*)
       IF current = maxline THEN                  (* counter exceeds allowed line no *)
         current := 0                             (* reset counter                   *)
       END;
       INC(current);
       WriteCard(current,digpernum);              (* write current line no to screen *)
       Write(blank);
       WHILE (ch <> eol) & (Done) DO              (* while not at end of file line   *)             id := free;
         IF (CAP(ch)>= "A") & (CAP(ch)<="Z") THEN (* see if alphabetic               *)
           idcntr    := 0;
           REPEAT                                 (* get the word and put in id      *)
             IF idcntr < wordlen THEN
               INC(idcntr);
               id[idcntr] := ch;
             END;
             Write(ch);
             Read(ch);
            UNTIL ((CAP(ch)<"A") OR (CAP(ch)>"Z")) & ((ch<"0") OR (ch>"9"));
           tablefull := search()                  (* call search to add to table     *)
         ELSE                                     (* if not a word                   *)
           IF ch = quote THEN                     (* if a quote ignore between quotes*)
             REPEAT
               Write(ch);
               Read(ch)
             UNTIL ch = quote
           ELSIF ch = "{" THEN                    (* if a brace ignore between braces*)
             REPEAT
               Write(ch);
               Read(ch)
             UNTIL ch = "}"
           END;
         Write(ch);
         Read(ch);
       END;                                       (* end if alphabetic statement     *)
     END;                                         (* end while not eol loop          *)
     WriteLn;
     Read(ch);
   END;                                           (* end while not eof loop          *)
   tablefull := TRUE;                             (* exit outer loop so can print tab*)
 END;
 CloseInput;                                      (* close the input file            *)
 (* Write(ff) *)
 printtable;                                      (* print the table                 *)
 END
END crossref.

You are viewing proxied material from gopher.floodgap.com. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.