;; 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-intermediate-reader.ss" "lang")((modname 17.8.1) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp")))))
;A list-of-numbers is either
;1. empty or
;2. (cons n lon)
;where n is a number and lon is a list-of-numbers.
;
;list=?-1 and list=?-2 : list-of-numbers list-of-numbers -> boolean
;Given lon1 and lon2, return true if the two lists are equal, false otherwise.

;(define (list=?-1 lon1 lon2)
;  (cond
;    [(and (empty? lon1)
;          (empty? lon2)) true]
;    [(and (cons? lon1)
;          (empty? lon2)) false]
;    [(and (empty? lon1)
;          (cons? lon2)) false]
;    [(and (cons? lon1)
;          (cons? lon2)) (and (= (first lon1) (first lon2))
;                             (list=?-1 (rest lon1) (rest lon2)))]))

(define (list=?-1 lon1 lon2)
  (cond
    [(and (empty? lon1)
          (empty? lon2)) true]
    [(and (cons? lon1)
          (cons? lon2)) (and (= (first lon1) (first lon2))
                             (list=?-1 (rest lon1) (rest lon2)))]
    [else false]))


(define (list=?-2 lon1 lon2)
  (cond
    [(empty? lon1) (empty? lon2)]
    [(cons? lon1) (and (cons? lon2)
                       (= (first lon1) (first lon2))
                       (list=?-2 (rest lon1) (rest lon2)))]))
   
;Test
;(list=?-2 empty empty)
;(list=?-2 empty '(1))
;(list=?-2 '(1) empty)
;(list=?-2 '(1) '(1))
;(list=?-2 '(1) '(1 2))

;A list-of-symbols is either
;1. empty or
;2. (cons s los)
;where s is a symbol and los is a list-of-symbols.
;
;sym-list=? : list-of-symbols list-of-symbols -> boolean
(define (sym-list=? los1 los2)
  (cond
    [(and (empty? los1)
          (empty? los2)) true]
    [(and (cons? los1)
          (cons? los2)) (and (symbol=? (first los1) (first los2))
                             (sym-list=? (rest los1) (rest los2)))]
    [else false]))

;sort-lon : list-of-numbers -> list-of-numbers
;Given a-lon, sort lon.

(define (sort-lon a-lon)
  (cond
    [(empty? a-lon) empty]
    [(cons? a-lon) (insert-number (first a-lon) (sort-lon (rest a-lon)))]))

;insert-number : number list-of-numbers -> list-of-numbers
;Given a-number and a-lon (sorted in ascending order), insert a-number in the proper position in lon to return the resulting sorted list-of-numbers.

(define (insert-number a-number a-lon)
  (cond
    [(empty? a-lon) (list a-number)]
    [(< a-number (first a-lon)) (append (list a-number)
                                        a-lon)]
    [else (append (list (first a-lon))
                  (insert-number a-number (rest a-lon)))]))

;contains-same-numbers : list-of-numbers list-of-numbers -> boolean
;Given lon1 and lon2, return true if the two lists have the same numbers, regardless of order.

(define (contains-same-numbers lon1 lon2)
  (list=?-1 (sort-lon lon1) (sort-lon lon2)))

;Data Definition
;
;An atom is either
;1. a number,
;2. a symbol, or
;3. a boolean.
;
;A list-of-atoms is either
;1. empty or 
;2. (cons a loa)
;where a is an atom and loa is a list-of-atoms.
;
;list-equal? : list-of-atoms list-of-atoms -> boolean
;Given loa1 and loa2, determine if the two lists are equal (corresponding elements within the list have equivalent atoms).

(define (list-equal? loa1 loa2)
  (cond
    [(and (empty? loa1)
          (empty? loa2)) true]
    [(and (cons? loa1)
          (empty? loa2)) false]
    [(and (empty? loa1)
          (cons? loa2)) false]
    [(and (cons? loa1)
          (cons? loa2)) (and (atoms-equal? (first loa1) (first loa2))
                             (list-equal? (rest loa1) (rest loa2)))]))
    
;atoms-equal? : atom atom -> boolean
;Given atom1 and atom2, determine if the two atoms are equal.

(define (atoms-equal? atom1 atom2)
  (cond
    [(and (number? atom1)
          (number? atom2)) (= atom1 atom2)]
    [(and (boolean? atom1)
          (boolean? atom2)) (boolean=? atom1 atom2)]
    [(and (symbol? atom1)
          (symbol? atom2)) (symbol=? atom1 atom2)]
    [else false]))

;(define atomic1 (list 5 'hi 'joe true false))
;(define atomic2 (list 5 'hi 'joe true false))

;A web-page (wp) is either
;1. empty,
;2. (cons s wp), or
;3. (cons ewp wp)
;where s is a symbol, wp is a web-page (wp), and ewp is a web-page (wp).

;wp=? : wp wp -> boolean
;Given wp1 and wp2, determine if the two web-pages are identical.

(define (wp=? wp1 wp2)
  (cond
    [(empty? wp1) (empty? wp2)]
    [(symbol? (first wp1)) (and (cons? wp2) (symbol? (first wp2))
                                (symbol=? (first wp1) (first wp2))
                                (wp=? (rest wp1) (rest wp2)))]
    [(list? (first wp1)) (and (cons? wp2) (list? (first wp2))
                              (wp=? (first wp1) (first wp2))
                              (wp=? (rest wp1) (rest wp2)))]))

;(define empwp empty)
;(define swpwp (cons 'firstPage (cons 'secondPage empty)))
;(define ewpwp (cons (cons 'firstPage empty) (cons 'secondPage empty)))
;
;(wp=? empwp empwp)
;(not (wp=? swpwp empwp))
;(not (wp=? ewpwp empwp))
;(not (wp=? empwp swpwp))
;(wp=? swpwp swpwp)
;(not (wp=? ewpwp swpwp))
;(not (wp=? empwp ewpwp))
;(not (wp=? swpwp ewpwp))
;(wp=? ewpwp ewpwp)

;posn=? : posn posn -> boolean
;Given posn1 and posn2, determine if they are equal.

(define (posn=? posn1 posn2)
  (and (posn? posn1) (posn? posn2)
       (= (posn-x posn1) (posn-x posn2))
       (= (posn-y posn1) (posn-y posn2))))

(define-struct node (name left right))

;A binary tree (BT) either
;1. empty or
;2. (make-node name left right)
;(make-node name left right)
;where name is a symbol and left, right are binary trees (BT).

;tree=? : BT BT -> boolean
(define (tree=? bt1 bt2)
  (cond
    [(empty? bt1) (empty? bt2)]
    [(node? bt1) (and (node? bt2)
                      (tree=? (node-left bt1) (node-left bt2))
                      (tree=? (node-right bt1) (node-right bt2)))]))
#|
Test
(define five (make-node 'five empty empty))
(define four (make-node 'four empty empty))
(define three (make-node 'three empty empty))
(define two (make-node 'two four five))
(define one (make-node 'one two three))

(tree=? one one)
(not (tree=? one two))
(not (tree=? one three))
(not (tree=? two four))

|#

;An Slist is either
;1. empty or
;2. (cons s sl)
;where s is a Sexpr and sl is a Slist.
;
;An Sexpr is either
;1. a number
;2. a boolean
;3. a symbol
;4. a Slist.
;
;Slist=? Slist Slist -> boolean
;Given Slist1 and Slist2, determines if the two Slists are identical.

(define (Slist=? Slist1 Slist2)
  (cond
    [(empty? Slist1) (empty? Slist2)]
    [(cons? Slist1) (and (cons? Slist2)
                         (Sexpr=? (first Slist1) (first Slist2))
                         (Slist=? (rest Slist1) (rest Slist2)))]))

;Sexpr=? Sexpr Sexpr -> boolean
;Given Sexpr1 and Sexpr2, determines if the two Sexprs are identical.

(define (Sexpr=? Sexpr1 Sexpr2)
  (cond
    [(number? Sexpr1) (and (number? Sexpr2)
                           (= Sexpr1 Sexpr2))]
    [(boolean? Sexpr1) (and (boolean? Sexpr2)
                            (boolean=? Sexpr1 Sexpr2))]
    [(symbol? Sexpr1) (and (symbol? Sexpr2)
                           (symbol=? Sexpr1 Sexpr2))]
    [(cons? Sexpr1) (and (cons? Sexpr2)
                         (Slist=? Sexpr1 Sexpr2))]))

;An Slist is either
;1. empty or
;2. (cons s sl)
;where s is a Sexpr and sl is a Slist.
;
;An Sexpr is either
;1. a number
;2. a boolean
;3. a symbol
;4. a Slist.

;(define Sexpr6 true)
;(define Sexpr5 15)
;(define Slist4 (cons Sexpr5 empty))
;(define Sexpr2 Slist4)
;(define Slist3 (cons Sexpr6 empty))
;(define Slist2 (cons Sexpr2 Slist3))
;(define Sexpr1 'FirstExpr)
;(define Slist1 (cons Sexpr1 Slist2))
;
;(Slist=? empty empty)
;(not (Slist=? empty (cons 15 empty)))
;(not (Slist=? (cons 15 empty) empty))
;(not (Slist=? (cons true empty) (cons false empty)))
;(Slist=? Slist1 Slist1)
;(not (Slist=? Slist2 Slist1))
;(not (Slist=? Slist4 Slist2))

;A list-of-data (lod) is either
;1. empty or
;2. (cons d lod) where d is a Scheme datum and lod is a list-of-data.
;
;replace-eol-with : list-of-data list-of-data -> list-of-data
;Given lod1 and lod2, append lod2 to the end of lod1.

(define (replace-eol-with lod1 lod2)
  (cond
    [(empty? lod1) lod2]
    [(cons? lod1) (cons (first lod1) (replace-eol-with (rest lod1) lod2))]))

;test-replace-eol-with : list-of-data list-of-data list-of-data -> boolean
;Given lod1, lod2, and expected-result, append lod2 to the end of lod1 and see if it matches the expected result.

(define (test-replace-eol-with lod1 lod2 expected-result)
  (equal? (replace-eol-with lod1 lod2) expected-result))

;(test-replace-eol-with '(Hi My Name Is Joe) '(Nice To Meet You Joe) '(Hi My Name Is Joe Nice To Meet You Joe))
;(not (test-replace-eol-with '(Hi My Name Is Joe) '(Nice To Meet You Joe) '(Hi My Name Is Joe Nice To Meet You Joey)))

;list-pick : list-of-symbols N[>=1] -> symbol
;Given a-los and n, find the nth symbol in a-los.  The first symbol in a-los has an index of 1.

(define (list-pick a-los n)
  (cond
    [(and (= n 1)
          (empty? a-los)) (error 'list-pick "list too short")]
    [(and (= n 1)
          (cons? a-los)) (first a-los)]
    [(and (> n 1)
          (empty? a-los)) (error 'list-pick "list too short")]
    [(and (> n 1)
          (cons? a-los)) (list-pick (rest a-los) (sub1 n))]))

(define los '(Fred Ted Bill Bob Joe))

;test-list-pick : list-of-symbols N[>=1] symbol -> boolean

;Given a-los, n, and expected-result, pick the n-th symbol from a-los using list-pick and see if it matches our expected-result.

(define (test-list-pick a-los n expected-result)
  (equal? expected-result (list-pick a-los n)))

;(test-list-pick los 3 'Bill)
;(not (test-list-pick los 4 'Bill))

test-evaluate