Power-Programmierung/CD1.mdf/magazine/drdobbs/1986/02/walker.feb

Text File | 1986-02-27 | 5KB | 246 lines

Listing One


MODULE Sorter;

(* Sorter utilizes modules RandomNumbers and Queues to demonstrate *)
(* the utility of data abstraction.                                *)

FROM InOut IMPORT
                ClearScreen,
                WriteInt,
                WriteLn,
                WriteString;

FROM RandomNumbers IMPORT
        (* PROC *)     randu;

FROM Queues IMPORT
        (* PROC *)     InitPriorityQueue,
                       QueueEmpty,
                Add,
                Fetch,
        (* TYPE *)     PriorityQueue;

VAR Count : CARDINAL;
    x     : INTEGER;
    Q     : PriorityQueue;

BEGIN (* MAIN *)

    ClearScreen;

    InitPriorityQueue(Q); (* Initialize the Priority Queue Q *)

    (* Add 100 pseudo-random numbers to the Priority Queue Q *)
    FOR Count := 1 TO 100 DO
        Add(Q, randu());
    END;

    (* Empty the Priority Queue Q and display each removed element *)
    WriteLn;
    WriteLn;
    WriteString("Sorted Pseudo-Random Numbers.....");
    WriteLn;
    WHILE NOT QueueEmpty(Q) DO
        x := Fetch(Q);
        WriteInt(x, 10);
        WriteLn
    END;

END Sorter.



Listing Two

The DEFINITION MODULEs Queues and RandomNumbers

DEFINITION MODULE Queues;

EXPORT QUALIFIED
        (* TYPE *)    PriorityQueue,
        (* PROC *)     InitPriorityQueue,
                Add,
                Fetch,
                QueueEmpty;

TYPE PriorityQueue;  (* Opaque Type *)

PROCEDURE InitPriorityQueue(VAR Q : PriorityQueue);
(* Initializes the Priority Queue Q *)

PROCEDURE Add(VAR Q : PriorityQueue; datum : INTEGER);
(* Adds the data item to the Priority Queue Q *)

PROCEDURE Fetch(VAR Q : PriorityQueue ) : INTEGER;
(* Fetches the smallest element from the Priority Queue Q *)

PROCEDURE QueueEmpty( Q : PriorityQueue) : BOOLEAN;
(* QueueEmpty RETURNs TRUE if PriorityQueue Q is empty; FALSE otherwise *)

END Queues.

DEFINITION MODULE RandomNumbers;

EXPORT QUALIFIED
    (* PROC *) randu;

PROCEDURE randu() : INTEGER;
(* randu RETURNs a pseudo-random INTEGER *)

END RandomNumbers.


Listing Three

IMPLEMENTATION MODULE of Queues incorporating an Add procedure
that uses a recursively defined algorithm; IMPLEMENTATION
MODULE of RandomNumbers that uses poorly chosen coefficients
for the recurrence relation.


IMPLEMENTATION MODULE Queues;

FROM Storage IMPORT ALLOCATE, DEALLOCATE;

TYPE PriorityQueue = POINTER TO PriNode;
     PriNode       = RECORD
             data : INTEGER;
            link : PriorityQueue;
         END;

PROCEDURE InitPriorityQueue(VAR Q : PriorityQueue);
BEGIN
    Q := NIL
END InitPriorityQueue;

PROCEDURE Add(VAR Q : PriorityQueue; datum : INTEGER);
VAR T : PriorityQueue;
BEGIN
    IF QueueEmpty(Q) THEN
        NEW(Q);
        Q^.link := NIL;
        Q^.data := datum;
    ELSIF datum < Q^.data THEN
        NEW(T);
        T^.link := Q;
        T^.data := datum;
        Q := T
    ELSE
        Add(Q^.link, datum)
    END;
END Add;

PROCEDURE Fetch(VAR Q : PriorityQueue) : INTEGER;
VAR tempInt : INTEGER;
    tempQ   : PriorityQueue;
BEGIN
    tempQ := Q;
    tempInt := Q^.data;
    Q := Q^.link;
    DISPOSE(tempQ);
    RETURN tempInt
END Fetch;

PROCEDURE QueueEmpty(Q : PriorityQueue) : BOOLEAN;
BEGIN
    RETURN Q = NIL
END QueueEmpty;

END Queues.




Listing Four

IMPLEMENTATION MODULE of Queues incorporating an Add procedure
that uses a non-recursive algorithm; IMPLEMENTATION MODULE of
RandomNumbers with better coefficients for the recurrence
relation. These improved versions of the implementation modules
can be compiled and substituted for the original Queues and
RandomNumbers without the definition module or any client
modules having to be recompiled.

IMPLEMENTATION MODULE Queues;

FROM Storage IMPORT ALLOCATE, DEALLOCATE;

TYPE PriorityQueue = POINTER TO PriNode;
     PriNode       = RECORD
             data : INTEGER;
            link : PriorityQueue;
         END;

PROCEDURE InitPriorityQueue(VAR Q : PriorityQueue);
BEGIN
    Q := NIL
END InitPriorityQueue;

PROCEDURE Add(VAR Q : PriorityQueue; datum : INTEGER);
VAR T, T1, NewNode : PriorityQueue;
BEGIN
    IF QueueEmpty(Q) THEN
        NEW(Q);
        Q^.link := NIL;
        Q^.data := datum;
    ELSIF datum < Q^.data THEN
        NEW(T);
        T^.link := Q;
        T^.data := datum;
        Q := T
    ELSE
        T := Q;
        WHILE (T # NIL) & (datum >= T^.data) DO
            T1 := T;
            T := T^.link;
        END;
        NEW(NewNode);
        NewNode^.link := T;
        NewNode^.data := datum;
        T1^.link := NewNode;
    END;

END Add;

PROCEDURE Fetch(VAR Q : PriorityQueue) : INTEGER;
VAR tempInt : INTEGER;
    tempQ   : PriorityQueue;
BEGIN
    tempQ := Q;
    tempInt := Q^.data;
    Q := Q^.link;
    DISPOSE(tempQ);
    RETURN tempInt
END Fetch;

PROCEDURE QueueEmpty(Q : PriorityQueue) : BOOLEAN;
BEGIN
    RETURN Q = NIL
END QueueEmpty;

END Queues.


IMPLEMENTATION MODULE RandomNumbers;

VAR x : INTEGER;

PROCEDURE randu() : INTEGER;
BEGIN
    x := (5 * x + 31) MOD 4096;
    RETURN x
END randu;

BEGIN
    x := 7;

END RandomNumbers.;
    RETURN x
END randu;

BEGIN
    x := 7;

END RandomNumbers.