home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / MODULA2 / TWOTREES.ZIP / TWOTREES.TXT
Encoding:
Text File  |  1986-01-30  |  4.1 KB  |  92 lines
  1. (* TwoTreesRunning  15 Oct 85
  2.  
  3. A few years ago, I offered the conjecture that in Modula-2 one could traverse
  4. two trees simultaneously (eg. merge them) with one procedure but two Modula-2
  5. coroutines.  As an exercise for a course ("Modula-2 for FORTRAN Programmers",
  6. five days) I am giving next month, I had a chance to make good on my specu-
  7. lations and actually write the program.
  8.  
  9. The example is brutal in that it makes no attempt to hide the type of the data
  10. values or other motherhoods.  Though bad practice, I did not want to obscure
  11. the principal goal.
  12.  
  13. Feel free to use it in your own work, but please credit the original author.
  14. Comments, improvements, and abuse should be direct to me.
  15.  
  16. Thank you,
  17.  
  18.   Randy Bush
  19.   Pacific Systems Group
  20.   601 South 12th Court
  21.   Coos Bay, Oregon  97420
  22.   Voice      : (503) 267-6970
  23.   Occasional : (503) 572-5391
  24.   TeleMail   : RBush/PSG
  25.   Telex      : 9103339158  PACIFIC SYS GR
  26.   Fido 122/6 : (503) 269-5202
  27.   CompuServe : 70265,757
  28.   Usenet     : decvax!decwrl!logitech!psg
  29.  
  30. *)
  31.  
  32. MODULE TwoTreesRunning;                (* by RBush.  Copyright 1985, Pacific *)
  33. IMPORT SYSTEM;                         (* Systems Group. All rights reserved.*)
  34. FROM Storage IMPORT ALLOCATE, DEALLOCATE;
  35.  
  36. TYPE
  37.     Node      = POINTER TO NodeRec;    (* one subtree of list elements       *)
  38.     NodeRec   = RECORD                 (* one list element looks like this   *)
  39.         left  : Node;                  (* val of these nodes is less         *)
  40.         right : Node;                  (* val of these nodes is greater      *)
  41.         i     : CARDINAL               (* example, any ordered type will do  *)
  42.         END;
  43. VAR
  44.     t0, t1    : Node;                  (* two trees possibly full of data    *)
  45.     p         : SYSTEM.PROCESS;        (* the non-running process of the two *)
  46.     other     : Node;                  (* non-running process's current node *)
  47.     parm      : Node;                  (* root parameter to DoTree           *)
  48.     minNode   : Node;                  (* fake node with min value for data  *)
  49.     stack     : ARRAY [0..1953] OF     (* stack space for the second process *)
  50.                  SYSTEM.WORD;          (* type arbitrary, size system-dep    *)
  51.  
  52.     PROCEDURE DoTree ();               (* coroutine, so 'parm' in global     *)
  53.  
  54.         PROCEDURE DoSubTree ( n : Node );
  55.         BEGIN
  56.             IF n^.left <> NIL THEN     (* do the left subtree before node    *)
  57.                 DoSubTree ( n^.left )  (* recurse down to lowest in subtree  *)
  58.                 END;
  59.             IF (other <> NIL) AND (n^.i > other^.i) THEN
  60.                 other := n;            (* node(s) in other tree come first   *)
  61.                 SYSTEM.TRANSFER ( p, p )
  62.                 END;
  63.             (* Some.Process (n^) *)    (* actually process the current node  *)
  64.             IF n^.right <> NIL THEN    (* after node do entire right subtree *)
  65.                 DoSubTree ( n^.right )
  66.                 END
  67.             END DoSubTree;
  68.  
  69.     BEGIN
  70.         IF parm <> NIL THEN            (* if the passed tree is not empty    *)
  71.             DoSubTree ( parm )         (*  then processs it as a subtree     *)
  72.             END;
  73.         IF other <> NIL THEN           (* if not finished with other tree    *)
  74.             other := NIL;              (*  then let other coroutine finish   *)
  75.             SYSTEM.TRANSFER ( p, p )
  76.             END
  77.         END DoTree;
  78.  
  79. BEGIN
  80.     (* t0 := SomeHow.MakeTree (); *)
  81.     parm := t0;                        (* couroutine will traverse tree t0   *)
  82.     NEW ( minNode );                   (* create phony t1 starting node      *)
  83.     minNode^.i := 0;                   (*  with the minimum data value in it *)
  84.     other := minNode;                  (*   to force t0 traversal far left   *)
  85.     SYSTEM.NEWPROCESS ( DoTree, SYSTEM.ADR(stack), SYSTEM.SIZE(stack), p );
  86.     SYSTEM.TRANSFER ( p, p );          (* start t0 traversal which           *)
  87.     DISPOSE ( minNode );               (*  xfers back when at far left value *)
  88.     (* t1 := SomeHow.MakeTree (); *)
  89.     parm := t1;                        (* main coroutine does t1 traversal   *)
  90.     DoTree ()
  91.     END TwoTreesRunning.
  92.