;;;;;; 3.3
(define (make-account balance password)
  (define (withdraw amount)
    (if (> amount balance)
	"Insufficient funds"
	(begin (set! balance (- balance amount))
	       balance)))
  (define (deposit amount)
    (begin (set! balance (+ balance amount))
	   balance))
  (define (dispatch pass m)
    (if (eq? pass password)
	(cond ((eq? m 'withdraw) withdraw)
	      ((eq? m 'deposit) deposit)
	      (else (error "Unknown request -- MAKE-ACOUNT"
			   M)))
	(lambda (x) "Wrong Password")))
  dispatch)

(define acc (make-account 100 '12345))

;STk> ((acc '54321 'withdraw) 10)
;"Wrong Password"
;STk> ((acc '12345 'deposit) 30)
;130
;STk> ((acc '12345 'withdraw) 150)
;"Insufficient funds"
;STk> ((acc '12345 'withdraw) 100)
;30
;STk> ((acc '12345 'give-me-coke) 1)
;*** Error:
;    Unknown request -- MAKE-ACOUNTgive-me-coke
;Current eval stack:
;__________________
;  0    (stk-error "~A" (with-output-to-string (lambda () (for-each (lambda (x) (display x)) args))))
;  1    ((acc (quote 12345) (quote give-me-coke)) 1)


;;;;;; 3.4
;change the name to make-safe-account for testing purpose
(define (make-safe-account balance password)
  (define try 0)
  (define (withdraw amount)
    (if (> amount balance)
	"Insufficient funds"
	(begin (set! balance (- balance amount))
	       balance)))
  (define (deposit amount)
    (begin (set! balance (+ balance amount))
	   balance))
  (define (call-the-cops) "Now, the cops are coming for you")
  (define (dispatch pass m)
    (if (eq? pass password)
	(begin (set! try 0)
	       (cond ((eq? m 'withdraw) withdraw)
		     ((eq? m 'deposit) deposit)
		     (else (error "Unknown request -- MAKE-ACOUNT"
				  M))))
	(lambda (x) (begin (set! try (+ 1 try))
			   (if (> try 7)
			       (begin (set! try 0)
				      (call-the-cops))
			       "Wrong Password")))))
  dispatch)

(define safe (make-safe-account 1000 'safesafe))

;notes: after each time (call-the-cops), reset the try to 0
;after each sucessful entry, reset the try to 0 also

;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Now, the cops are coming for you"
;STk> ((safe 'notsafe 'withdraw) 1000)
;"Wrong Password"
;STk> ((safe 'safesafe 'deposit) 100)
;1100
;STk> ((safe 'safesafe 'withdraw) 200)
;900
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"
;STk> ((safe 'safesafe 'withdraw) 100)
;800
;STk> ((safe 'safe 'withdraw) 100)
;"Wrong Password"


;;;;;; 3.7
;using the same make-account in 3.3
(define (make-joint old old-pass new-pass)
  (lambda (pass m)
    (if (eq? pass new-pass)
	(old old-pass m)
	(lambda (x) "Wrong Password"))))

(define x (make-account 1000 '123))
(define y (make-joint x '123 '999))
(define z (make-joint x '333 '777))

;STk> ((x '123 'deposit) 100)
;1100
;STk> ((y '999 'withdraw) 1000)
;100
;STk> ((y 'abcd 'withdraw) 10)
;"Wrong Password"
;STk> ((y '999 'deposit) 200)
;300
;STk> ((x '123 'withdraw) 250)
;50
;STk> ((z '777 'withdraw) 10)
;"Wrong Password"
;STk> ((y '123 'deposit) 100)
;"Wrong Password"

;explaination: x and y are working as one account, notice that y only can use the
;new password, that is 777, not the password for x, which is 123
;z is created, but because of the wrong password it has in the beginning, z can never
;acces the information in x. So, z is not a joint account.


;;;;;; 3.8
(define f
  (let ((i 0))
    (lambda (n)
      (begin (set! i (+ i 1))
	     (if (even? i)
		 n
		 0)))))

;STk> (+ (f 0) (f 1))
;1
;STk> (+ (f 1) (f 0))
;0

;the order of evaluation in schemem is left to right, so if we want to evaluate
;from right to left, just switch the argument.


;;;;;; 3.10
;please refer to the seperate sheet turned in

;;;;;; 3.11
;please refer to the seperate sheet turned in

;;;;;; 3.16
;please refer to the seperate sheet turned in

;;;;;; 3.17
(define (count-pairs x)
  (count x (list nil)))

(define (count tree ref-list)
  (cond ((not (pair? tree)) 0)
	((inside? tree ref-list) 0)
	(else
	 (begin (set-cdr! (findlast ref-list) (cons tree nil))
	   (+ (count (car tree) ref-list)
	      (count (cdr tree) ref-list)
	      1)))))

(define (inside? tree ref-list)
  (cond ((empty? ref-list) #f)
	((eq? tree (car ref-list)) #t)
	(else (inside? tree (cdr ref-list)))))

(define (findlast arg)
  (if (eq? (cdr arg) nil)
      arg
      (findlast (cdr arg))))

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x x))

(define case1 (cons x y))
(define case2 (cons x (cons x 3)))
(define case3 (cons z z))

(define a (cons 'a 'b))
(define b (cons 'c 'd))
(define case4
  (let ((p (cons nil nil)))
    (begin (set-car! p a)
	   (set-cdr! p b)
	   (set-car! a p)
	   (set-cdr! a p)
	   (set-car! b p)
	   (set-cdr! b p)
	   p)))

;testing with case1-4
;STk> case1
;((1 . 2) 3 . 4)
;STk> case2
;(#0=(1 . 2) #0# . 3)
;STk> case3
;(#0=(#1=(1 . 2) . #1#) . #0#)
;STk> case4
;#0=((#0# . #0#) #0# . #0#)
;STk> (count-pairs case1)
;3
;STk> (count-pairs case2)
;3
;STk> (count-pairs case3)
;3
;STk> (count-pairs case4)
;3


;;;;;; 3.21
;define the queue data structure
(define (make-queue) (cons '() '()))

(define (empty-queue? queue) (null? (front-ptr queue)))

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))

(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an empty queue" queue)
      (car (front-ptr queue))))

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
	   (set-front-ptr! queue new-pair)
	   (set-rear-ptr! queue new-pair)
	   queue)
	  (else
	   (set-cdr! (rear-ptr queue) new-pair)
	   (set-rear-ptr! queue new-pair)
	   queue))))

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
	 (error "DELETE! called with an empty queue" queue))
	(else
	 (set-front-ptr! queue (cdr (front-ptr queue)))
	 queue)))

;STk> (define q1 (make-queue))
;q1
;STk> q1
;(())
;STk> (insert-queue! q1 'a)
;((a) a)
;STk> (insert-queue! q1 'b)
;((a b) b)
;STk> (delete-queue! q1)
;((b) b)
;STk> (delete-queue! q1)
;(() b)

;explaination: q1 is not a list by itself, q1 is a list of lists. q1 has two items, as defined
;one is the actual list of data, the other one is the last data of the actual list of data.
;that's why after we insert 'a and 'b inside, we have ((a b) b). This doesn't mean that we have
;three items in the queue, instead, we mean that the datas are 'a and 'b, and the 'b is the last
;data in our queue
;when we delele, we don't care about the rear-ptr, we simply move the front-ptr, (() b) means that
;there is no data in queue, and the rear-ptr is pointing to a list b. This is fine because when we
;insert again, both front-ptr and rear-ptr will be reset.

;here is the code to print the queue
(define (print-queue queue)
  (front-ptr queue))

;STk> (insert-queue! q1 'xyz)
;((xyz) xyz)
;STk> (insert-queue! q1 'fbi)
;((xyz fbi) fbi)
;STk> (insert-queue! q1 'end)
;((xyz fbi end) end)
;STk> (load "home5.scm")
;STk> (print-queue q1)
;(xyz fbi end)
;STk> (delete-queue! q1)
;((fbi end) end)
;STk> (delete-queue! q1)
;((end) end)
;STk> (print-queue q1)
;(end)
;STk> (delete-queue! q1)
;(() end)
;STk> (print-queue q1)
;()

;;;;;; 3.27
;copy the codes for make-table, lookup and insert!
(define (make-table)
  (list '*table*))

(define (lookup key table)
  (let ((record (assoc key (cdr table))))
    (if record
	(cdr record)
	#f)))

(define (insert! key value table)
  (let ((record (assoc key (cdr table))))
    (if record
	(set-cdr! record value)
	(set-cdr! table (cons (cons key value) (cdr table)))))
  'ok)

;copy the code in Exercise 3.27
(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
	(or previously-computed-result
	    (let ((result (f x)))
	      (insert! x result table)
	      result))))))

(define memo-fib
  (memoize (lambda (n)
	      (cond ((= n 0) 0)
		    ((= n 1) 1)
		    (else (+ (memo-fib (- n 1))
			     (memo-fib (- n 2))))))))

(define (fib n)
  (cond ((= n 0) 0)
	((= n 1) 1)
	(else (+ (fib (- n 1))
		 (fib (- n 2))))))

(define memo-fib-2 (memoize fib))

;STk> (fib 20)
;6765
;STk> (memo-fib 20)
;6765
;STk> (memo-fib-2 20)
;6765

;we see that fib, memo-fib, memo-fib-2 all give the exact answer, but comparing the time
;each consumed, fib>memo-fib-2>memo-fib, so we can conclude memo-fib-2 is not the same
;as memo-fib, that is (define memo-fib (memoize fib)) is not the same thing as old memo-fib

;(memo-fib n+1) will invoke (memo-fib n) and (memo-fib n-1). When we compute (memo-fib n), we
;continue to do this process until we down to 0 and 1. Now, we back up, but as we travle alone,
;we put the value of memo-fib of 2, 3, 4 ... n-2, n-1, n to the table, so (memo-fib n-1) will
;be directly output from the table, no need to calculate to the root, so we say that when n
;increased by 1, the number of steps increase by one alson. That is memo-fib computes the nth
;Fibonacci number in a number of steps proportional to n.