home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
magazine
/
drdobbs
/
1986
/
02
/
walker.feb
< prev
Wrap
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.