;;; ======================================================================
;;; Code that implements search examples following presentation in Norvig
;;; section 6.4.  2/95  Paul McNamee

(in-package :user)

;;; ======================================================================
;;; A general tree searching tool.

(defun tree-search (states goal-p successor-fn combiner-fn)
  "Find a state that statisfies goal-p.  General tool that can implement
   different types of searches by changing the combination rules."
  (format t "~&;; Search: ~S" states)
  (cond ((null states) (format t "Failed to find a solution.~%"))
	((funcall goal-p (first states)) (first states))
	(t (tree-search (funcall combiner-fn
				 (funcall successor-fn (first states))
				 (rest states))
			goal-p successor-fn combiner-fn))
))

;;; ======================================================================
;;; Depth-First-Search based on tree-search

(defun depth-first-search (start goal-p successor-fn)
  "DFS using general tree searching utility"
  (tree-search (list start) goal-p successor-fn #'append)
)

;;; ======================================================================
;;; Breadth-First-Search based on tree-search.  The difference here is we
;;; want to examine the rest of the states first, then the children of the
;;; first state.  This is the opposite of append.

(defun prepend (a b)
  "Opposite of (append a b)"
  (append b a))

(defun breadth-first-search (start goal-p successor-fn)
  "BFS using general tree searching utility"
  (tree-search (list start) goal-p successor-fn #'prepend)
)

;;; ======================================================================
(defun Print-Book (book stream k)
  (declare (ignore k))
  "I can't remember what k is for, but print function should have 3 args. cf Steele pg 480"
  (format stream "<Book: '~a' by ~a>" (node-title book) (node-author book))
)

(defstruct (Node (:print-function print-book))
  (author "" :type 'string) (title "" :type 'string) (left-child nil) (right-child nil))

(defparameter *Library* (make-node :author "Norvig" :title "PAIP")
  "A tree containing some of Paul's favorite books sorted by author name")


(defun Add-Book (author title &key (node *Library*))
  (cond ((string< author (node-author node))
	          (if (null (node-left-child node))
		      (setf (node-left-child node)
			    (make-node :author author :title title))
		      (Add-Book author title :node (node-left-child node))) )
	(t  (if (null (node-right-child node))
		(setf (node-right-child node) (make-node :author author :title title))
		(Add-Book author title :node (node-right-child node))) )
))

(defun Create-Tree ()
  (Add-Book "Weiss" "The Swiss Family Robinson")
  (Add-Book "Steele" "CLTL2")
  (Add-Book "Conan Doyle" "Adventures of Sherlock Holmes")
  (Add-Book "Kernighan & Ritchie" "The C Programming Language 2nd edition")
  (Add-Book "Clocksin & Mellish" "Programming in Prolog")
  (Add-Book "Verne" "Journey to the Center of the Earth")
  (Add-Book "Tolkien" "The Hobbit")
)  

(defun Print-Library (&optional (node *library*))
  "In Order Traversal"
  (cond ((null node) (values))
	(t (Print-Library (node-left-child node))
	   (format t "~S~%" (node-author node))
	   (Print-Library (node-right-child node)) )
))	

(defun Author-Equal-Fn (x)
  "Returns a function of one argument that checks to see if a book author field contains x.
   Note that search is used to check for subsequences"
  #'(lambda (y) (search x (node-author y) :test #'string-equal))
)

(defun Title-Equal-Fn (x)
  "Returns a function of one argument that checks to see if a book author field contains x.
   Note that search is used to check for subsequences"
  #'(lambda (y) (search x (node-title y) :test #'string-equal))
)

(defun Children-of-Book (node)
  (remove-if #'null (list (node-left-child node) (node-right-child node)))
)


;;; ======================================================================
;;; Okay this was a nice example of searching trees.  The tree structure here
;;; gave us Logrithmic time instead of linear which we would have in a list.
;;;
;;; Another application of search is State Space Search.  In this case we are
;;; concerned with searching a universe of possible solutions and finding
;;; a solution. (Sometimes we want the _best_ solution).  Common examples of
;;; State Space Search are:
;;;   - path planning
;;;   - game playing (eg. chess)
;;;   - TSP / network problems. (goals could be shortest distance, max throughput, ...)
;;; ======================================================================