;----------------------------------------------------------------------------
;	dfs example code by Yoonsuck Choe
;
;	run as
;
;		(dfs '((2 20) (1 3) 5))
;		(dfs '((2 (10 (7 11))) (2 8) (9 (20 1))))
;
;	the goal is to find a leaf node > 10 in the given tree.
;
;----------------------------------------------------------------------------

(defvar *example1* '((2 20) (1 3) 5))
(defvar *example2* '((2 (10 (7 11))) (2 8) (9 (20 1))))

; dfs wrapper interface
(defun dfs (initial-state)
	(dfs-core (make-node-list initial-state))
)

; dfs-core: search for a leaf node and return the value
; try this with different trees.
(defun dfs-core (node-list)
	(let (cur-node tmp-node-list) 
	    (if (null node-list)
		NIL
		(progn
		    (setq cur-node (car node-list))
		    (setq tmp-node-list (cdr node-list))
		    (if (goalp cur-node) 
		        cur-node
		        (dfs-core (append (expand cur-node) tmp-node-list))
			; try the following instead of the above for BFS
		        ; (dfs-core (append tmp-node-list (expand cur-node)))
		    )
	  	)
	    )
	)
)

; dfs-iter: iterative version of dfs
(defun dfs-iter (start-state)
  (let (cur-node node-list (goal-found NIL))
        (setq node-list (make-node-list start-state))
        (loop (unless (equal goal-found T))
        	(if (< (length node-list) 1) (return-from dfs-iter nil))
                (setq cur-node (car node-list))
                (setq node-list (cdr node-list))
                (if (goalp cur-node)
                        (return-from dfs-iter cur-node)
                        (setq node-list (append (expand cur-node) node-list))
                )
        )
  )
)

; goal check
(defun goalp (node)
	(and (atom node) (> node 10))
)

; make a node list 
(defun make-node-list (state)
	(list state)
)
	
; expand a node and return the list of expanded nodes
(defun expand (node)
	(if (atom node) 
	    NIL
	    node ; this is basically the list of subtrees, and subtrees
		 ; represent the expanded nodes.
	)
)