;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-abbr-reader.ss" "lang")((modname 05trees-templates) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
#|
;; DEMO: templates for functions on railways (1D-trees)
DATA DESCRIPTION
A *station* is a structure:

> `(make-station name distance)`

where `name` is a string and `distance` is a number representing the
distance in miles from Boston.

A *railway* is either:
  - A station
  - A structure (representing a boundary point on the line)
    > `(make-boundary distance south north)`
    where
      - `distance` is the distance of the boundary point from Boston
      - `south` is a 1D-tree of stations, all of which are south of the
        boundary (that is, they are further away from Boston)
      - `north` is a 1D-tree of stations, all of which are north of the
        boundary (that is, they are closer to Boston than the given `distance`)
|#
(define-struct station (name distance))
(define-struct boundary (distance south north))

;DATA EXAMPLES
(define bos (make-station "South Station" 0))
(define bby (make-station "Back Bay" 1.1))
(define pvd (make-station "Providence" 42.6))
(define nhv (make-station "New Haven" 156.4))
(define nro (make-station "New Rochelle" 212.1))
(define nyp (make-station "NY Penn Station" 228.7))

(define northeast
  (make-boundary 114
              (make-boundary 178 (make-boundary 220 nyp nro) nhv)
              (make-boundary  20 pvd (make-boundary 0.5 bby bos))))

(define (railway-template rail)
  (cond [(station? rail)
             (... (station-name rail) ... (station-distance rail) ...)]
        [(boundary? rail)
             (... (boundary-distance rail) ...
                  (railway-template (boundary-south rail)) ...
                  (railway-template (boundary-north rail)) ...
                  (boundary-south rail) ...
                  (boundary-north rail) ...)]))

; northmost : railway -> station
; to return the northernmost station on the railway
(define (northmost rail)
  ...)
(check-expect (northmost northeast) ...)

; rail-length : railway -> number
; to return the length of the railway in miles
(define (rail-length rail)
  ...)
(check-expect (rail-length northeast) ...)

; stations-on : railway -> list-of-stations
; to return an ordered list of all stations on the railway, southernmost first
(define (stations-on rail)
  ...)
(check-expect (stations-on northeast)
              (list nyp nro nhv pvd bby bos))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; extended list template

(define (list-function xs)
  (cond [(empty? xs) ...]
        [(cons? xs)
            (... (first xs) ... (rest xs) ... (list-function (rest xs)))]))
            ;;;                 ^^^^^^^^^
            ;;;              this bit is new

; decreasing? : list-of-numbers -> boolean
; tells whether given numbers are decreasing from left to right
(define (decreasing? ns)
  ...)
(check-expect (decreasing? '(1 2 3)) false)
(check-expect (decreasing? '(3 2 1)) true)
(check-expect (decreasing? '(3 1 2)) false)
(check-expect (cons 1 empty) ...)
(check-expect empty          ...)


;;DATA DESCRIPTION
;;A list of numbers is one of:
;;  - empty
;;  - (cons n empty),  where n is a number
;;  - (cons n1 (cons n2 ns)),  where n1 and n2 are numbers
;;                             and ns is a list of numbers


; singleton? : list-of-any -> boolean
; to tell whether the given list contains exactly one value
(define (singleton? xs)
  ...)
(check-expect (singleton? empty) false)
(check-expect (singleton? (cons 1 empty)) true)
(check-expect (singleton? (cons "purple" empty)) true)
(check-expect (singleton? (cons "yellow" (cons 9 empty))) false)
(check-expect (singleton? '(1 2)) false)



; south-to-north? : list-of-stations -> boolean
; tells whether given stations are ordered southmost first
(define (south-to-north? stns)
  ...)