home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
modu1096.zip
/
sample
/
traverse.mod
< prev
Wrap
Text File
|
1995-03-29
|
4KB
|
162 lines
(****************************************************************)
(* *)
(* (c) copyright 1990 Faculty of Information Technology *)
(* Queensland University of Technology *)
(* *)
(* Permission is granted to use, copy and change this *)
(* program as long as the copyright message is left intact *)
(* *)
(****************************************************************)
(*
* This program demonstrates the use of a coroutine to
* hold the frozen state of a data structure traversal
* A conventional recursive tree-walk has TRANSFERs
* added so that after finding each new element the
* caller is resumed, leaving the traversal information
* frozen on the stack of the suspended coroutine.
* Insertions and traversals may be interleaved arbitrarily.
*)
MODULE Traverse;
IMPORT Storage, Coroutines;
FROM Storage IMPORT ALLOCATE;
FROM CharInfo IMPORT IsDigit;
FROM Terminal IMPORT
GetKeyStroke, Read, Write, WriteCard, WriteLn, WriteString;
TYPE TreePtr = POINTER TO TreeNode;
TreeNode = RECORD
key : CARDINAL;
left, right : TreePtr;
END;
VAR root : TreePtr;
(* ============================================== *)
MODULE FrozenTraversals;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
FROM Coroutines IMPORT Coroutine, NEWPROCESS, TRANSFER;
IMPORT WriteString, WriteCard, WriteLn, root, TreePtr, TreeNode;
EXPORT InitTraversal, Next;
VAR this : Coroutine;
ended : BOOLEAN;
globalNext : CARDINAL;
CONST size = 10000; (* stack ~ 6000 bytes *)
VAR main : Coroutine;
work : Coroutine;
PROCEDURE Frozen;
(* $S+ *)
PROCEDURE Recurse(tree : TreePtr);
BEGIN
IF tree <> NIL THEN
Recurse(tree^.left);
globalNext := tree^.key;
TRANSFER(this,main);
Recurse(tree^.right);
END;
END Recurse;
(* $S= *)
BEGIN
Recurse(root);
ended := TRUE;
TRANSFER(this,main);
END Frozen;
PROCEDURE InitTraversal;
BEGIN
IF this = NIL THEN
ALLOCATE(work,size);
END;
NEWPROCESS(Frozen,work,size,this);
ended := root = NIL;
END InitTraversal;
PROCEDURE Next(VAR val : CARDINAL;
VAR ok : BOOLEAN);
BEGIN
ok := FALSE;
IF this = NIL THEN
WriteString("Traversal not initialized"); WriteLn;
ELSIF ended THEN
WriteString("Traversal has ended"); WriteLn;
ELSE
(*
* get next value, if there is one
*)
TRANSFER(main,this);
IF NOT ended THEN
val := globalNext;
ok := TRUE;
ELSE WriteString("Traversal has ended"); WriteLn;
END;
END;
END Next;
BEGIN
this := NIL;
END FrozenTraversals;
(* ============================================== *)
PROCEDURE Insert(val : CARDINAL);
PROCEDURE Add(VAR t : TreePtr);
BEGIN
IF t = NIL THEN
NEW(t);
WITH t^ DO
left := NIL; right := NIL; key := val;
END;
ELSE
WITH t^ DO
IF val < key THEN Add(left);
ELSIF val > key THEN Add(right);
ELSE (* skip *)
END;
END;
END;
END Add;
BEGIN
Add(root);
END Insert;
VAR value : CARDINAL;
ok : BOOLEAN;
ch : CHAR;
BEGIN
WriteString("Frozen traversal demo:"); WriteLn;
WriteString("'i' to Insert, ");
WriteString("'b' to Begin traversal, ");
WriteString("'n' for Next, ");
WriteString("'x' to eXit,"); WriteLn;
LOOP
GetKeyStroke(ch);
IF CAP(ch) = "I" THEN
WriteString("Value: ");
value := 0;
Read(ch);
WHILE IsDigit(ch) DO
value := value * 10 + ORD(ch) - ORD("0");
Read(ch);
END;
Insert(value);
ELSIF CAP(ch) = "B" THEN
InitTraversal();
ELSIF CAP(ch) = "N" THEN
Next(value,ok);
IF ok THEN
WriteCard(value,0); WriteLn;
END;
ELSIF CAP(ch) = "X" THEN EXIT;
END;
END;
END Traverse.