;;; -*-lisp-*-
;;;
;;; Lisp implementation of a `same-fringe' solver.

;;;--------------------------------------------------------------------------
;;; Iteration utilities.

;; The iteration protocol is as follows.  An iterator is simply a function
;; invoked with no arguments.  It returns two values: the next item, and a
;; new iterator function to produce the remaining items; if there are no more
;; items, then it returns NIL twice.

(defun list-iterator (iter)
  "Collect the items from ITER into a list and return it."
  (labels ((recur (iter list)
	     (multiple-value-bind (data iter) (funcall iter)
	       (if iter
		   (recur iter (cons data list))
		   (nreverse list)))))
    (recur iter nil)))

(defun same-iterators-p (iter-a iter-b &key (test #'eql))
  "Return whether ITER-A and ITER-B produce the same items."
  (labels ((recur (iter-a iter-b)
	     (multiple-value-bind (data-a iter-a) (funcall iter-a)
	       (multiple-value-bind (data-b iter-b) (funcall iter-b)
		 (cond ((null iter-a) (null iter-b))
		       ((or (null iter-b)
			    (not (funcall test data-a data-b)))
			nil)
		       (t (recur iter-a iter-b)))))))
    (recur iter-a iter-b)))

;;;--------------------------------------------------------------------------
;;; Nodes and trees.

(defstruct node
  "A simple node in a binary tree.  Empty subtrees are denoted by NIL."
  left data right)

(defun iterate-fringe (node)
  "Inorder iterator for the tree headed by NODE."
  (labels ((recur (node cont)
	     (cond (node (recur (node-left node)
				(lambda ()
				  (values (node-data node)
					  (lambda ()
					    (recur (node-right node)
						   cont))))))
		   (cont (funcall cont))
		   (t (values nil nil)))))
    (lambda () (recur node nil))))

(defun parse-tree (string)
  "Parse STRING, and return the tree described.

   The syntax is simple:

	tree ::= empty | `(' tree char tree `)'

   The ambiguity is resolved by always treating `(' as a tree when a tree is
   expected."

  (let ((len (length string)))
    (labels ((parse (i)
	       (cond ((>= i len)
		      (values nil i))
		     ((char= (char string i) #\()
		      (multiple-value-bind (left i) (parse (1+ i))
			(unless (< i len) (error "no data"))
			(let ((data (char string i)))
			  (multiple-value-bind (right i) (parse (1+ i))
			    (unless (and (< i len)
					 (char= (char string i) #\)))
			      (error "missing )"))
			    (values
			     (make-node :left left :data data :right right)
			     (1+ i))))))
		     (t (values nil i)))))
      (multiple-value-bind (tree i) (parse 0)
	(unless (= i len) (error "trailing junk"))
	tree))))

;;;--------------------------------------------------------------------------
;;; Main program.

(defun main (args)
  "Main program: process ARGS."
  (destructuring-bind (&optional a b &rest junk) args
    (cond ((or (null a) junk) (error "bad args"))
	  ((null b) (format t "~{~C~}~%"
			    (list-iterator (iterate-fringe (parse-tree a)))))
	  (t (format t "~:[no match~;match~]~%"
		     (same-iterators-p (iterate-fringe (parse-tree a))
				       (iterate-fringe (parse-tree b))))))))

#+cl-launch
(defun launch ()
  (flet ((bail (format args)
	   (format *error-output* "~A: ~?~%"
		   (cl-launch:getenv "CL_LAUNCH_FILE") format args)
	   (cl-launch:quit 1)))
    (handler-case
	(main cl-launch:*arguments*)
      (simple-error (err)
	(bail (simple-condition-format-control err)
	      (simple-condition-format-arguments err)))
      (error (err)
	(bail "~A" err)))))

;;;----- That's all, folks --------------------------------------------------