;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; This file is part of "NOVA":  NOVA = search + COCOMO tools
; Copyright, 2008, Tim Menzies tim@menzies.us
;
; NOVA is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; NOVA is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
; You should have received a copy of the GNU General Public License
; a long with NOVA.  If not, see <http://www.gnu.org/licenses/>.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defsearch beam ((beam-width 10))
  (save-state)
  (push path paths)
  (let ((best path))
    (loop
     (if (null paths) (return))
     (switch-path (pop paths))

     ;; if the solution is not fully constrained, generate successors
     (unless (= (constrained% (first-state? path)) 1)

       ;; pick a random feature
       (let* ((treatment (?elt (coalesce-treatments (non-singletons? open))))
	      (feature   (car treatment))
	      (range     (cdr treatment)))

	 ;; discard ranges one at a time, storing each new path as a successor
	 (dolist (value range)
	   (with-new-path
	     (move-elt (list feature value) open closed)
	     (save-state)
	     (push path paths)))))
     (when paths

       ;; sort paths by least energy
       (setf paths (sort paths #'< :key #'(lambda (path) (energy? (first-state? path)))))

       ;; trim to beam-width paths
       (if (> (length paths) beam-width)
	   (setf paths (subseq paths 0 beam-width)))
       (if *debug-search* (print-paths (subseq paths 0 (min 5 (length paths))) :which :first)))
     (if (< (energy? (first-state? path)) (energy? (first-state? best)))
	 (setf best path)))

    ;; switch to the best path
    (switch-path best)))