home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / modu1096.zip / sample / traverse.mod < prev   
Text File  |  1995-03-29  |  4KB  |  162 lines
  1. (****************************************************************)
  2. (*                                *)
  3. (*     (c) copyright 1990 Faculty of Information Technology    *)
  4. (*        Queensland University of Technology        *)
  5. (*                                *)
  6. (*     Permission is granted to use, copy and change this    *)
  7. (*     program as long as the copyright message is left intact    *)
  8. (*                                *)
  9. (****************************************************************)
  10.  
  11. (*
  12.  *  This program demonstrates the use of a coroutine to
  13.  *  hold the frozen state of a data structure traversal
  14.  *  A conventional recursive tree-walk has TRANSFERs 
  15.  *  added so that after finding each new element the 
  16.  *  caller is resumed, leaving the traversal information
  17.  *  frozen on the stack of the suspended coroutine.
  18.  *  Insertions and traversals may be interleaved arbitrarily.
  19.  *)
  20.  
  21. MODULE Traverse;
  22.   IMPORT Storage, Coroutines;
  23.   FROM Storage IMPORT ALLOCATE;
  24.   FROM CharInfo IMPORT IsDigit;
  25.   FROM Terminal IMPORT 
  26.        GetKeyStroke, Read, Write, WriteCard, WriteLn, WriteString;
  27.  
  28.   TYPE TreePtr = POINTER TO TreeNode;
  29.        TreeNode = RECORD
  30.             key : CARDINAL;
  31.             left, right : TreePtr;
  32.           END;
  33.  
  34.   VAR  root : TreePtr;
  35.  
  36.   (* ============================================== *)
  37.  
  38.   MODULE FrozenTraversals;
  39.     FROM Storage IMPORT ALLOCATE, DEALLOCATE;
  40.     FROM Coroutines IMPORT Coroutine, NEWPROCESS, TRANSFER;
  41.     IMPORT WriteString, WriteCard, WriteLn, root, TreePtr, TreeNode;
  42.  
  43.     EXPORT InitTraversal, Next;
  44.  
  45.     VAR    this : Coroutine;
  46.     ended : BOOLEAN;
  47.     globalNext : CARDINAL;
  48.  
  49.     CONST size = 10000; (* stack ~ 6000 bytes *)
  50.  
  51.     VAR main : Coroutine;
  52.         work : Coroutine;
  53.  
  54.     PROCEDURE Frozen;
  55.       (* $S+ *)
  56.       PROCEDURE Recurse(tree : TreePtr);
  57.       BEGIN
  58.     IF tree <> NIL THEN
  59.       Recurse(tree^.left);
  60.       globalNext := tree^.key; 
  61.       TRANSFER(this,main);
  62.       Recurse(tree^.right);
  63.     END;
  64.       END Recurse;
  65.       (* $S= *)
  66.     BEGIN
  67.       Recurse(root);
  68.       ended := TRUE;
  69.       TRANSFER(this,main);
  70.     END Frozen;
  71.  
  72.     PROCEDURE InitTraversal;
  73.     BEGIN
  74.       IF this = NIL THEN
  75.         ALLOCATE(work,size);
  76.       END;
  77.       NEWPROCESS(Frozen,work,size,this);
  78.       ended := root = NIL;
  79.     END InitTraversal;
  80.  
  81.     PROCEDURE Next(VAR val : CARDINAL;
  82.            VAR ok  : BOOLEAN);
  83.     BEGIN
  84.       ok := FALSE;
  85.       IF this = NIL THEN
  86.     WriteString("Traversal not initialized"); WriteLn;
  87.       ELSIF ended THEN
  88.     WriteString("Traversal has ended"); WriteLn;
  89.       ELSE
  90.     (*
  91.      *  get next value, if there is one
  92.          *)
  93.     TRANSFER(main,this);
  94.     IF NOT ended THEN
  95.       val := globalNext; 
  96.       ok := TRUE;
  97.     ELSE WriteString("Traversal has ended"); WriteLn;
  98.     END;
  99.       END;
  100.     END Next;
  101.  
  102.   BEGIN
  103.     this := NIL;
  104.   END FrozenTraversals;
  105.  
  106.   (* ============================================== *)
  107.  
  108.   PROCEDURE Insert(val : CARDINAL);
  109.     PROCEDURE Add(VAR t : TreePtr);
  110.     BEGIN
  111.       IF t = NIL THEN
  112.     NEW(t);
  113.     WITH t^ DO
  114.       left := NIL; right := NIL; key := val;
  115.         END;
  116.       ELSE
  117.     WITH t^ DO
  118.       IF val < key THEN Add(left);
  119.       ELSIF val > key THEN Add(right);
  120.       ELSE (* skip *)
  121.       END;
  122.     END;
  123.       END;
  124.     END Add;
  125.   BEGIN
  126.     Add(root);
  127.   END Insert;
  128.  
  129.   VAR  value : CARDINAL;
  130.        ok    : BOOLEAN;
  131.        ch    : CHAR; 
  132.  
  133. BEGIN
  134.   WriteString("Frozen traversal demo:"); WriteLn;
  135.   WriteString("'i' to Insert, ");
  136.   WriteString("'b' to Begin traversal, ");
  137.   WriteString("'n' for Next, ");
  138.   WriteString("'x' to eXit,"); WriteLn;
  139.   LOOP
  140.     GetKeyStroke(ch);
  141.     IF CAP(ch) = "I" THEN
  142.       WriteString("Value: ");
  143.       value := 0;
  144.       Read(ch);
  145.       WHILE IsDigit(ch) DO
  146.     value := value * 10 + ORD(ch) - ORD("0");
  147.     Read(ch);
  148.       END;
  149.       Insert(value);
  150.     ELSIF CAP(ch) = "B" THEN 
  151.       InitTraversal();
  152.     ELSIF CAP(ch) = "N" THEN
  153.       Next(value,ok);
  154.       IF ok THEN 
  155.     WriteCard(value,0); WriteLn;
  156.       END;
  157.     ELSIF CAP(ch) = "X" THEN EXIT;
  158.     END;
  159.   END;
  160. END Traverse.
  161.  
  162.