;;; websearch1.lsp
;;; Some helper code for Assignment 5 in CSE 415, Winter 2004.
;;; S. Tanimoto

;;; This file provides an implementation of a depth-first search
;;; method that starts from a given web page and follows links
;;; to try to find a page that contains a given target string.

;;; In this example, the function FETCH-WEB-PAGE is a simple
;;; simulation that does not actually go to the web.

;;; Code for DFS:

(defun dfs (starting-url goal-string)
  (setq open (list starting-url))
  (setq closed ())
  (tagbody
    mainloop
    (if (null open) (return-from dfs 'done))
    (setq s (pop open))
    (if (goalp s goal-string)
      (return-from dfs (list 'answer s)) )
    (setq L (successors s))
    (setq L (remove-all open L))
    (setq L (remove-all closed L))
    (setq open (append L open))
    (push s closed)
    (go mainloop)
 ) )

(defun remove-all (lst1 lst2)
  "Returns a copy of LST2 from which all
   elements of LST1 have been removed."
  (cond ((null lst1) lst2)
        (t (remove-all
             (cdr lst1)
             (remove (car lst1) lst2 :test #'equal) ))
  ) )

(defun goalp (url goal-string)
  (if (not (equal url *current-url*))
    (progn
      (setq *page* (fetch-web-page url))
      (setq *current-url* url) ) )
  (search goal-string *page*) )

;;; The following function is a kind of scaffolding for the
;;; rest of the program.  It simulates fetching web pages,
;;; but it doesn't really go out onto the web.
(defun fetch-web-page (url)
  (cond
   ((equal url "www.site1.com")
    "Page 1: blah blah <a href=\"http://www.site2.com\"
     and <a href=\"http://www.site3.com\" <end of page>")
   ((equal url "www.site2.com")
    "Page 2: blah blah <a href=\"http://www.site1.com\"
     and <a href=\"http://www.site3.com\" <end of page>")
   ((equal url "www.site3.com")
    "Page 3: blah blah Ides of March <a href=\"http://www.site1.com\"
     and <a href=\"http://www.site2.com\" <end of page>")
 ) )

(defun successors (url)
  (if (not (equal url *current-url*))
    (progn (setq *page* (fetch-web-page url))
           (setq *current-url* url) ) )
  (setq *temp* *page*)
  (succ-helper) )

(defun succ-helper ()
  "Uses what's left of the *PAGE* value most recently retrieved."
  (let* ((marker "<a href=\"http://")
         (marker-length (length marker))
         (position1 (search marker *temp*)))
    (if (null position1) nil
      (let* ((position1a (+ position1 marker-length))
             (position2 (search "\"" *temp* :start2 position1a)) )
        (if (null position2) nil
          (let ((successor1 (subseq *temp* position1a position2)))
            (setq *temp* (subseq *temp* (1+ position2)))
            (cons successor1 (succ-helper))
 ) ) ) ) ) )

(defvar *current-url* nil)
(defvar *page*)
(defvar *temp*)

(trace successors)

(defun test ()
  (dfs "www.site1.com" "Ides of March") )