COMMENT -*-a68-*-

	Algol 68 implementation of a `same-fringe' solver.

COMMENT
BEGIN

###--------------------------------------------------------------------------
# # Reporting errors.
# #
# # This stuff is specific to Algol 68 Genie.
###

[] CHAR program name =
  BEGIN [] CHAR prog = argv(3);
  INT i := UPB prog;
  WHILE (i >= LWB prog | prog[i] /= "/" | FALSE) DO i -:= 1 OD;
  prog[i + 1:]
  END;

PROC fail = ([] CHAR message) VOID:
  ### Mournfully announce an error and quit.
  #
  BEGIN put(stand error, (program name, ": ", message, new line));
    execve("/bin/false", "false", "die=now")	# Can this be any worse? #
  END;

###--------------------------------------------------------------------------
# # Nodes and trees.
###

MODE NODE = STRUCT (REF NODE left, right, CHAR data);

PROC tree is not empty = (REF NODE node) BOOL: node :/=: NIL;

PROC parse tree = ([] CHAR string) REF NODE:
  ### Parse STRING, and return the tree described.
  ##
  ## The syntax is simple:
  ##
  ##	  tree ::= empty | `(' tree char tree `)'
  ##
  ## The amiguity is resolved by always treating `(' as a tree when a tree
  ## is expected.
  #
  BEGIN INT i := LWB string;
  PROC parse = REF NODE:
    BEGIN IF i > UPB string THEN NIL
      ELIF string[i] /= "(" THEN NIL
      ELSE i +:= 1;
        REF NODE left = parse;
	IF i > UPB string THEN fail("no data") FI;
	CHAR data = string[i]; i +:= 1;
	REF NODE right = parse;
	IF (i > UPB string | TRUE | string[i] /= ")")
 	  THEN fail("missing )") FI;
	i +:= 1;
	HEAP NODE := (left, right, data)
      FI
    END;
    REF NODE tree = parse;
    IF i <= UPB string THEN fail("trailing junk") FI;
    tree
  END;

###--------------------------------------------------------------------------
# # Iteration.
###

MODE NODEITER = STRUCT (REF [] REF NODE stack, INT sp);

PROC push nodes = (REF NODEITER iter, REF NODE node) VOID:
  ### Helper function for iteration.
  ##
  ## If NODE is not null, push it onto ITER's stack, and then do the same
  ## for NODE's left child.
  #
  BEGIN REF NODE n := node;
  WHILE tree is not empty(n)
    DO IF sp OF iter > UPB (stack OF iter)
      THEN INT max = UPB (stack OF iter);
	HEAP [2 * max] REF NODE new stack;
	FOR i FROM 1 TO max DO new stack[i] := (stack OF iter)[i] OD;
	stack OF iter := new stack
      FI;
      (stack OF iter)[sp OF iter] := n;
      n := left OF n;
      sp OF iter +:= 1
    OD
  END;

PROC next node = (REF NODEITER iter) REF NODE:
  ### Return the next node in order for the tree being traversed by ITER.
  ##
  ## Returns NIL if the iteration is complete.
  #
  IF sp OF iter = 1 THEN NIL
  ELSE sp OF iter -:= 1;
    REF NODE node = (stack OF iter)[sp OF iter];
    push nodes(iter, right OF node);
    node
  FI;

PROC node iterator = (REF NODE node) REF NODEITER:
  ### Return a new iterator traversing the tree rooted at NODE.
  #
  BEGIN REF NODEITER iter = HEAP NODEITER := (HEAP [1] REF NODE, 1);
  push nodes(iter, node);
  iter
  END;

###--------------------------------------------------------------------------
# # Fringe operations.
###

PROC print fringe = (REF NODE tree) VOID:
  ### Print the characters stored in the tree headed by TREE in order.
  #
  BEGIN REF NODEITER iter = node iterator(tree);
    WHILE REF NODE n = next node(iter); tree is not empty(n)
    DO print(data OF n) OD;
    print(new line)
  END;

PROC same fringes = (REF NODE n, REF NODE nn) BOOL:
  ### Answer whether traversing the trees rooted at N and NN yields the same
  ##  items in the same order.
  #
  BEGIN REF NODEITER i = node iterator(n), ii = node iterator(nn);
    BOOL win := FALSE;
    DO REF NODE n = next node(i), nn = next node(ii);
      IF tree is not empty(n)
      THEN IF tree is not empty(nn)
        THEN IF data OF n = data OF nn THEN SKIP ELSE done FI
        ELSE done
	FI
      ELIF tree is not empty(nn) THEN done
      ELSE win := TRUE; done
      FI
    OD;
  done: win
  END;

###--------------------------------------------------------------------------
# # Main program.
# #
# # Argument fetching is specific to Algol 68 Genie.
###

CASE argc - 3 IN
  BEGIN REF NODE tree = parse tree(argv(4));
    print fringe(tree)
  END,
  BEGIN REF NODE t = parse tree(argv(4)), tt = parse tree(argv(5));
    print(((same fringes(t, tt) | "match" | "no match"), new line))
  END
OUT fail("bad args")
ESAC
END

###----- That's all, folks -------------------------------------------------#