BEGIN # sort-tree merging,
   L. Allison 7/4/86 Dept. Computer Science, Monash University, Australia
   see: L. Allison. Some Applications of Continuations.
                    The Computer Journal 31(1) pp9-16, 1988 #

   MODE TREE = REF NODE;
   MODE NODE = STRUCT(INT e, TREE l, r);

   PROC insert = (INT e, REF TREE t)VOID:
      # NB inserts in t as a side effect #
      IF TREE(t) IS NIL THEN t := HEAP NODE := (e, TREE(NIL), TREE(NIL))
      ELIF e < e OF t THEN insert(e, l OF t)
      ELIF e > e OF t THEN insert(e, r OF t)
      FI;

   PROC show = (TREE t)VOID:
      IF t ISNT NIL THEN print("("); show(l OF t); print(e OF t);
			 show(r OF t); print(")")
      FI;

   PROC merge = (TREE s, t)VOID:
   BEGIN
      MODE SCANNER = PROC(INT, SCANNER)VOID;

      PROC traverse = (INT switch, TREE t, SCANNER continue, alternative)VOID:
	 IF t IS NIL THEN continue(switch, alternative)
	 ELSE PROC goright = (INT sw, SCANNER alt)VOID:
		    trav(sw, t, continue, alt);

	      traverse(switch, l OF t, goright, alternative)
	 FI;

      PROC trav = (INT switch, TREE t, SCANNER continue, alternative)VOID:
	 # traverse the root node and right sub-tree of t  only. #
	 IF t IS NIL THEN continue(switch, alternative)
	 ELIF e OF t  <=  switch THEN
	       print(e OF t);
	       traverse( switch, r OF t, continue, alternative)
	 ELSE  # e OF t > switch #
	       PROC defer = (INT sw, SCANNER alt)VOID:
		     trav(sw, t, continue, alt);

	       alternative(e OF t, defer)
	 FI;

      PROC m =  (TREE s, t, SCANNER scans, scant)VOID:
	 IF TREE(l OF s) ISNT NIL THEN
	    PROC travright = (INT sw, SCANNER alt)VOID:
		  trav(sw, s, scans, alt);

	    m(l OF s, t, travright, scant)
         ELIF TREE(l OF t) ISNT NIL THEN
	    m(t, s, scant, scans)
	 ELSE # l OF s  IS  l OF t  IS  NIL, so now have their smallest elts  #
            PROC scanstree = (INT sw, SCANNER alt)VOID:
	          trav( sw, s, scans, alt);
	    PROC scanttree = (INT sw, SCANNER alt)VOID:
	          trav( sw, t, scant, alt);

	    IF (e OF s) <= (e OF t) THEN scanstree( e OF t, scanttree)
				    ELSE scanttree( e OF s, scanstree)
	 FI FI;

      SCANNER halt = (INT sw, SCANNER a)VOID: print((" the end", newline));
      SCANNER fin  = (INT sw, SCANNER a)VOID:
	 (print( " finish: "); a(max int, halt));

      IF   s IS NIL THEN traverse( max int, t, halt, halt)
      ELIF t IS NIL THEN traverse( max int, s, halt, halt)
      ELSE m(s, t, fin, fin)
      FI
   END #merge#;

   LOC TREE s:=TREE(NIL), t:=TREE(NIL);
   LOC INT n;

   WHILE read(n); n>=0 DO insert(n, s) OD;
   show(s); print(newline);
   WHILE read(n); n>=0 DO insert(n, t) OD;
   show(t); print(newline);

   merge(s, t)
END