;
; Map
; from Lisp in Small Parts, http://lisp.plasticki.com/
; Licensed under CC0 1.0: http://creativecommons.org/publicdomain/zero/1.0/
; 2nd July 2012
;

(defparameter map-data nil)

(defun add-road (from to time &optional road)
  (setq map-data 
        (cons (list from to time road)
              (cons (list to from time road)
                    map-data))))

;
; Returns queue with item added to it in the correct position
;

(defparameter map-queue nil)

(defun add-item (item queue)
  (if (null queue) 
      (cons item queue)
    (if (< (first item) (first (first queue)))
        (cons item queue)
      (cons (first queue) (add-item item (rest queue))))))

;
; Add to queue
;

(defun add-to-queue (time location via)
  (setf map-queue (add-item (list time location via) map-queue)))

;
; For all the roads from a place, add to queue
;

(defun add-roads (location start)
  (dolist (item map-data)
    (let* ((from (first item))
           (to (second item))
           (time (third item)))
      (if (string= from location)
          (add-to-queue (+ start time) to location)))))

(defun grow-search (here to)
   (if (string= here to)
      nil
     (let* ((best (first map-queue))
            (from (second best)))
      (setf map-queue (rest map-queue))
      (add-roads from (first best))
      (cons (list from (third best)) (grow-search from to)))))

(defun find-in-list (item list)
  (if (null list) nil
    (if (string= (first (first list)) item) (first list)
      (find-in-list item (rest list)))))

(defun list-route (from to visited)
  (if (string= from to) (list from)
     (cons to (list-route from (second (find-in-list to visited)) visited))))

(defun find-route (from to)
  (setq map-queue nil)
  (add-to-queue 0 from nil)
  (reverse
   (list-route from to 
               (grow-search from to))))

(defun make-map ()
  (add-road "A" "B" 2)
  (add-road "B" "C" 3)
  (add-road "A" "D" 9)
  (add-road "B" "E" 3)
  (add-road "C" "F" 7)
  (add-road "D" "E" 3)
  (add-road "E" "F" 6)
  (add-road "D" "G" 2)
  (add-road "E" "H" 8)
  (add-road "F" "Z" 6)
  (add-road "G" "H" 2)
  (add-road "H" "Z" 4))

; Prompts to add a road to the map

(defun prompt-add-road ()
  (let ((from (capi:prompt-for-string "From:"))
        (to (capi:prompt-for-string "To:"))
        (time (capi:prompt-for-integer "Time (mins):"))
        (road (capi:prompt-for-string "Road:")))
    (add-road from to time road)))