;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-reader.ss" "lang")((modname 12.3.1) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp")))))
;A mail structure is
;(make-mail f d m) where f and m are strings,
;d is a date.

(define-struct mail (from date message))
;
;A list-of-mail is either
;1. an empty list or
;2. (cons mail lom) where mail is a mail structure
;and lom is a list-of-mail.
;
;sort-mail : list-of-mail -> list-of-mail
;Given alom (a list-of-mail),
;sorts the mail based on name
;by insertion sorting and returns
;the sorted list.

(define (sort-mail alom)
  (cond
    [(empty? alom) empty]
    [(cons? alom) (insert (first alom) (sort-mail (rest alom)))]))

;insert : mail list-of-mail -> list-of-mail
;Given amail and alom, insert amail into the proper
;position in alom and return the new list-of-mail.
;This is done by comparing the name of amail with
;the name of the first mail in alom.
;
;Template
;(define (insert amail alom)
;  (cond
;    [(string<? (mail-from amail) (mail-from (first alom)))
;     ...]
;    [else ...]))

(define (insert amail alom)
  (cond
    [(empty? alom) (cons amail alom)]
    [(string<? (mail-from amail) (mail-from (first alom)))
     (cons amail alom)]
    [else (cons (first alom)
                (insert amail (rest alom)))]))

;Test
;(define POSTMAN (cons (make-mail "Sally" 4561923 "Hi it's me Sally") (cons (make-mail "Jennifer" 9133217 "Sitting at home") (cons (make-mail "Tweety" 1234567 "Add me on Twitter") (cons (make-mail "Aaron" 5939257 "RonRon") (cons (make-mail "Zebrafish" 8888888 "Alphabetical") (cons (make-mail "Jabra" 2950 "Headset") empty)))))))

;; search : number list-of-numbers  ->  boolean
(define (search n alon)
  (cond
    [(empty? alon) false]
    [else (or (= (first alon) n) (search n (rest alon)))]))
;
;search-sorted : number list-of-numbers -> boolean
;Determines if n is in alon and returns true if it is,
;false otherwise. alon is assumed to be sorted
;in descending order. Performs a linear-search.
;
;Template
;(define (search-sorted n alon)
;  (cond
;    [(empty? alon) ...]
;    [(= n (first alon)) ...]
;    [else ... (search-sorted (rest alon))]))

(define (search-sorted n alon)
  (cond
    [(empty? alon) false]
    [(= n (first alon)) true]
    [(> n (first alon)) false]
    [else (search-sorted n (rest alon))]))

;Test
;(define MRLIST (cons 15 (cons 12 (cons 12 (cons 9 (cons 3 (cons 0 empty)))))))