(eval-when (:execute :load-toplevel :compile-toplevel)
  (defstruct route
    (dest 0 :type fixnum)
    (cost 0 :type fixnum)))

(defun parse-line (line &aux (pos 0) n)
  (declare (ignorable n))
  (loop repeat 3
        collect (multiple-value-setq (n pos)
                    (parse-integer line :start pos :junk-allowed t))))

(defparameter *file* "/Users/joswig/Desktop/graph-bench/agraph.txt")

(defun read-places ()
  (with-open-file (stream *file*)
    (let ((num-lines (parse-integer (read-line stream nil))))
      (values (loop for line = (read-line stream nil nil)
                    while line
                    collect (parse-line line))
              num-lines))))

(defun parse-places ()
  (multiple-value-bind (place-data num-nodes)
      (read-places)
    (let ((nodes (make-array num-nodes :initial-element nil)))
      (loop for (node-id neighbour dist) in place-data
            do (push (make-route :dest neighbour :cost dist)
                     (aref nodes node-id)))
      nodes)))

(defun get-longest-path (nodes node-id visited)
  (declare (optimize (speed 3) (space 0) (debug 0) (safety 0)
                     (compilation-speed 0)
                     #+lispworks (fixnum-safety 0))
           (type fixnum node-id)
	   (type (vector list)    nodes)
	   (type (vector boolean) visited))
  (setf (svref visited node-id) t)
  (let ((max (loop for neighbour of-type route in (svref nodes node-id)
                   unless (svref visited (route-dest neighbour))
                   maximize (the fixnum
                                 (+ (the fixnum (route-cost neighbour))
                                    (the fixnum (get-longest-path nodes (route-dest neighbour) visited)))))))
    (declare (fixnum max))
    (setf (svref visited node-id) nil)
    max))

(defun run ()
  (let* ((nodes    (parse-places))
         (visited  (make-array (length nodes) :element-type 'boolean :initial-element nil))
         (start    (get-internal-real-time))
         (len      (get-longest-path nodes 0 visited))
         (duration (- (get-internal-real-time) start)))
    (format t "~d LANGUAGE Lisp ~d ~%" len duration)))

#+ignore
(sb-ext:save-lisp-and-die "lisp" :toplevel #'run :executable t)