### -*-icon-*-
###
### An Icon implementation of a `same-fringe' solver.

###--------------------------------------------------------------------------
### Utilities.

procedure bail(msg)
  ## Report MSG as an error, and quit.

  write(&errout, &progname, ": ", msg)
  flush(&errout)
  exit(1)
end

procedure same_sequence_p(test, aseq, bseq)
  ## Succeed if the sequences generated by coexpressions ASEQ and BSEQ equal,
  ## in the sense that TEST succeeds when applied to corresponding elements,
  ## and the sequences have the same length.

  local a, b

  while a := @aseq do
    if not (b := @bseq) | not test(a, b) then fail
  if @bseq then fail
  return
end

procedure print_sequence(aseq)
  ## Write the elements of the sequence generated by coexpression ASEQ
  ## followed by a newline.

  every writes(|@aseq)
  write()
end

procedure string_equal_p(a, b)
  ## Succeed if strings A and B are equal.  Useful as a TEST for
  ## `print_sequence'.

  return a == b
end

###--------------------------------------------------------------------------
### Node structure.

record node(left, data, right)
## A simple binary tree structure.

procedure fringe(node)
  ## Generate the elements of the tree headed by NODE inorder.

  if /node then fail
  suspend fringe(node.left) | node.data | fringe(node.right)
end

procedure scan_tree()
  ## Scan a tree from the current subject, advancing the position over it.
  ## See `parse_tree' for the syntax.

  local data, left, right

  if ="(" then {
    left := scan_tree()
    data := move(1) | bail("no data")
    right := scan_tree()
    =")" | bail("missing )")
    return node(left, data, right)
  } else
    return &null
end

procedure parse_tree(string)
  ## Parse a tree from STRING and return its root.
  ##
  ## The syntax is as follows.
  ##
  ##	tree ::= empty | `(' tree char tree `)'
  ##
  ## Ambiguity is resolved by treating a `(' as starting a tree when a tree
  ## is expected.

  local t

  return string ? {
    t := scan_tree()
    if not pos(0) then bail("trailing junk")
    t
  }
end

###--------------------------------------------------------------------------
### Main program.

procedure main(argv)
  local trees

  if *argv = 1 then
    print_sequence(create fringe(parse_tree(argv[1])))
  else if *argv = 2 then
    if same_sequence_p(string_equal_p,
		       create fringe(parse_tree(argv[1])),
		       create fringe(parse_tree(argv[2]))) then
      write("match")
    else
      write("no match")
  else
    bail("bad args")
end

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