;;; code for city navigation project

;;; constructors for data abstractions


(define make-segment          ; string, point, point -> segment
  (lambda (name start finish) (list name start finish)))

(define make-point            ; number,number -> Point
  (lambda (x y)             (list x y)))


(define make-atlas list)     ; segment, ... -> list<segment>

(define make-trip list)      ; segment, ... -> list<segment>


;; match data abstraction

(define make-match list)                 ; X, Y -> match<X,Y>
(define first-of-match car)              ; match<X,Y> -> X
(define second-of-match cadr)            ; match<X,Y> -> Y


;;; utility functions

(define print-correspondence-list
  (lambda (corresps)
     (if (null? corresps)
         '()
         (begin
           (newline)
           (newline)
           (print "Next correspondence")
           (print-correspondence (car corresps))
           (print-correspondence-list (cdr corresps))))))

(define print-correspondence
  (lambda (corr)
    ;;; note that this will only be useful to you after you have completed 
    ;;; problem 8, otherwise comment out the part that uses lengths
    (if (null? corr) '()
      (begin (newline)
             (display "Trip segment name = ")
             (let ((tripseg (first-of-match (car corr))))
               (if (unnamed-segment? tripseg)
                   (display "UNKNOWN")
                   (display (segment-name tripseg))))
             (display " Atlas segment name = ")
             (let ((atlasseg (second-of-match (car corr))))
               (if (unnamed-segment? atlasseg)
                   (display "UNKNOWN")
                   (display (segment-name atlasseg))))
             (display " Trip segment length = ")
             (display (segment-length (first-of-match (car corr))))
             (display " Atlas segment length = ")
             (display (segment-length (second-of-match (car corr))))
             (print-correspondence (cdr corr))))))

;;; extended segment data abstraction for name matching

(define make-unnamed-segment      ; point, point -> segment
  (lambda (start finish) 
    (list internal-name-for-unnamed-segment start finish)))

(define unnamed-segment?          ; segment -> boolean
  (lambda (segment) 
    (string=? (car segment) internal-name-for-unnamed-segment)))

(define internal-name-for-unnamed-segment "###")

;;; some trial data

(define atlasseg-1 (make-segment "beacon"  (make-point 0 6) (make-point 3 7)))
(define atlasseg-2 (make-segment "beacon"  (make-point 3 7) (make-point 6 8)))
(define atlasseg-3 (make-segment "beacon"  (make-point 6 8) (make-point 9 9)))
(define atlasseg-4 (make-segment "beacon"  (make-point 9 9) (make-point 12 10)))

(define atlasseg-5 (make-segment "massachusetts"  (make-point 0 6) (make-point 1 4)))
(define atlasseg-6 (make-segment "massachusetts"  (make-point 1 4) (make-point 2 2)))

(define atlasseg-7 (make-segment "masspike"  (make-point 1 4) (make-point 5 3)))
(define atlasseg-8 (make-segment "masspike"  (make-point 5 3) (make-point 9 2)))

(define atlasseg-9 (make-segment "essex"  (make-point 2 2) (make-point 5 3)))
(define atlasseg-10 (make-segment "essex"  (make-point 5 3) (make-point 8 4)))
(define atlasseg-11 (make-segment "essex"  (make-point 8 4) (make-point 11 5)))
(define atlasseg-12 (make-segment "essex"  (make-point 11 5) (make-point 12 6)))

(define atlasseg-13 (make-segment "clarendon" (make-point 9 2) (make-point 8 4)))
(define atlasseg-14 (make-segment "clarendon" (make-point 8 4) (make-point 7 7)))
(define atlasseg-15 (make-segment "clarendon" (make-point 7 7) (make-point 6 8)))

(define atlasseg-16 (make-segment "arlington" (make-point 9 9) (make-point 11 5)))
(define atlasseg-17 (make-segment "arlington"  (make-point 11 5) (make-point 12 3)))

(define atlasseg-18 (make-segment "park"  (make-point 12 12) (make-point 12 10)))
(define atlasseg-19 (make-segment "park"  (make-point 12 10) (make-point 13 9)))

(define atlasseg-20 (make-segment "cambridge"  (make-point 12 12) (make-point 13 12)))

(define atlasseg-21 (make-segment "tremont"  (make-point 13 12) (make-point 14 11)))
(define atlasseg-22 (make-segment "tremont"  (make-point 14 11) (make-point 14 10)))
(define atlasseg-23 (make-segment "tremont" (make-point 14 10) (make-point 13 9)))

(define atlasseg-24 (make-segment "mason"  (make-point 12 6) (make-point 12 7)))
(define atlasseg-25 (make-segment "mason"  (make-point 12 7) (make-point 13 9)))

(define atlasseg-26 (make-segment "beacon"  (make-point 3 7) (make-point 0 6)))
(define atlasseg-27 (make-segment "beacon"  (make-point 6 8) (make-point 3 7)))
(define atlasseg-28 (make-segment "beacon"  (make-point 9 9) (make-point 6 8)))
(define atlasseg-29 (make-segment "beacon"  (make-point 12 10) (make-point 9 9)))

(define atlasseg-30 (make-segment "massachusetts"  (make-point 1 4) (make-point 0 6)))
(define atlasseg-31 (make-segment "massachusetts"  (make-point 2 2) (make-point 1 4)))

(define atlasseg-32 (make-segment "masspike"  (make-point 5 3) (make-point 1 4)))
(define atlasseg-33 (make-segment "masspike"  (make-point 9 2) (make-point 5 3)))

(define atlasseg-34 (make-segment "essex"  (make-point 5 3) (make-point 2 2)))
(define atlasseg-35 (make-segment "essex"  (make-point 8 4) (make-point 5 3)))
(define atlasseg-36 (make-segment "essex"  (make-point 11 5) (make-point 8 4)))
(define atlasseg-37 (make-segment "essex"  (make-point 12 6) (make-point 11 5)))

(define atlasseg-38 (make-segment "clarendon" (make-point 8 4) (make-point 9 2)))
(define atlasseg-39 (make-segment "clarendon" (make-point 7 7) (make-point 8 4)))
(define atlasseg-40 (make-segment "clarendon" (make-point 6 8) (make-point 7 7)))

(define atlasseg-41 (make-segment "arlington" (make-point 11 5) (make-point 9 9)))
(define atlasseg-42 (make-segment "arlington"  (make-point 12 3) (make-point 11 5)))

(define atlasseg-43 (make-segment "park"  (make-point 12 10) (make-point 12 12)))
(define atlasseg-44 (make-segment "park"  (make-point 13 9) (make-point 12 10)))

(define atlasseg-45 (make-segment "cambridge"  (make-point 13 12) (make-point 12 12)))

(define atlasseg-46 (make-segment "tremont"  (make-point 14 11) (make-point 13 12)))
(define atlasseg-47 (make-segment "tremont"  (make-point 14 10) (make-point 14 11)))
(define atlasseg-48 (make-segment "tremont" (make-point 13 9) (make-point 14 10)))

(define atlasseg-49 (make-segment "mason"  (make-point 12 7) (make-point 12 6)))
(define atlasseg-50 (make-segment "mason"  (make-point 13 9) (make-point 12 7)))

(define trial-atlas-1
    (make-atlas atlasseg-1 atlasseg-2 atlasseg-3 atlasseg-4 atlasseg-5 atlasseg-6
              atlasseg-7 atlasseg-8 atlasseg-9 atlasseg-10 atlasseg-11 atlasseg-12
              atlasseg-13 atlasseg-14 atlasseg-15 atlasseg-16 atlasseg-17 atlasseg-18
              atlasseg-19 atlasseg-20 atlasseg-21 atlasseg-22 atlasseg-23 atlasseg-24
	      atlasseg-25
              atlasseg-26 atlasseg-27 atlasseg-28 atlasseg-29 atlasseg-30 atlasseg-31
              atlasseg-32 atlasseg-33 atlasseg-34 atlasseg-35 atlasseg-36 atlasseg-37
              atlasseg-38 atlasseg-39 atlasseg-40 atlasseg-41 atlasseg-42 atlasseg-43           
              atlasseg-44 atlasseg-45 atlasseg-46 atlasseg-47 atlasseg-48 atlasseg-49
              atlasseg-50
))

(define trial-trip-1 
    (make-trip (make-segment "essex" (make-point 0 0) (make-point 1 1))))

(define trial-trip-2
    (make-trip 
               (make-unnamed-segment (make-point 0 0) (make-point 4 2))
               (make-segment "essex" (make-point 4 2) (make-point 5 -1))
               ))

(define trial-trip-3-part
    (make-trip 
               (make-unnamed-segment (make-point 0 3) (make-point 1 3))
               (make-unnamed-segment (make-point 1 3) (make-point 3 2))))

(define trial-trip-3
    (make-trip 
               (make-unnamed-segment (make-point 0 3) (make-point 1 3))
               (make-unnamed-segment (make-point 1 3) (make-point 3 2))
	       (make-segment "tremont" (make-point 3 2) (make-point 4 1))))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; 
;;   below are templates for code you will use in the project
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (make-correspondence trip atlas)
  (if (null? trip)
      empty-correspondence
      (let ((other (select atlas)))
	(add-leg (make-match (car trip) other)
	         (make-correspondence (cdr trip)
                                      (remove-element other atlas))))))