;; countup function: old code  that uses helper function
; (define (countup n) 
;   (cond
;    [(= n 1) (cons 1 empty)]
;    [else
; 	(countup-helper 1 n)]))

; (define (countup-helper start end)
;   (cond
;    [(= start end) (cons end empty)]
;    [else
;      (cons start
; 		   (countup-helper (add1 start) end))]))

;; new countup - uses local definition of helper

(define (countup n)
  (local
    ((define (countup-helper start end)
	   (cond
		[(= start end) (cons end empty)]
		[else
		 (cons start
			   (countup-helper (add1 start) end))])))
	(countup-helper 1 n)))


;; (countup 20)

;; simple minded findmax of a list of numbers
;;  very inefficient - roughly n*(n+1)/2 comparisons
;;  where we only need n.
;;
(define (findmax alon) 
  (cond
   [(empty? (rest alon)) (first alon)]
   [(> (first alon) (findmax (rest alon))) (first alon)]
   [ else (findmax (rest alon))]))

;; here is a better (more efficient) definition
;;
;; the advantage is that each time findmax2 is called,
;; it computes (findmax2 (rest alon)) at most once.
;; (sets a variable to the value returned by findmax2).
(define (findmax2 alon)
  (cond 
   [(empty? (rest alon)) (first alon)]
   [ else
     (local
       ((define restmax (findmax2 (rest alon))))
       (cond
         [(> (first alon) restmax) (first alon)]
		 [ else restmax]))]))

(findmax '(3 12 7 4 1 ))
(findmax2 '(3 12 7 4 1 ))

;;
;; sort consumes a list and produces a list
;;
;; (sort alon) will create a list with the same elements
;;   as alon, but in ascending order.
;;
;; usage: (sort '(1 3 12 4 8))
;;
;; uses local definitions for a findmin function,
;;   a function that removes a value from a list,
;;   and uses a variable to record the smallest
;;   value on the list (instead of finding this
;;   out twice

(define (sort alon)
  (cond 
   ;; base cases
   [(empty? alon) empty]
   [(empty? (rest alon)) alon]
   [else
	;; we have at least two numbers in the list.
    (local
	 ;; findmin finds the minimum number in a list of numbers
      ((define (findmin alon)
		 (cond 
		  [(empty? (rest alon)) (first alon)]
		  [ else
			(local
			 ((define restmin (findmin (rest alon))))
			 (cond
			  [(< (first alon) restmin) (first alon)]
			  [ else restmin]))]))

	   ;; remove-element consumes a number and a list and returns a list.
	   ;;  creates a list with all the elements in alon, except that 
	   ;;  a single instance of x is removed. Order is preserved.
       (define (remove-element x alon)
		 (cond
		  [(= x (first alon)) (rest alon)]
		  [else
           (cons (first alon) (remove-element x (rest alon)))]))

	   ;; find the smallest element in the list
	   (define smallest (findmin alon)))

	  ;; simply put the smallest at the beginning, and
	  ;; sort the remaining element.
	  (cons smallest (sort (remove-element smallest alon))))]))

(sort '(1 3 12 7 6 2 4))


;; tree building
;;
;;  want to create a binary search tree from a list of numbers
;;  (in any order?)

;;

;; binary search tree node:
;;
;; a bst node is either empty, or a bsnode
;;
;; a bsnode is a structure with num, left and right,
;;  where num is a number, left and right are bsnodes.
;;
(define-struct bsnode (num left right))



;;      
;; make-bst creates a binary search tree from a list of numbers.
;;
;; make-bst consumes a list and produces a binary search tree.
;;
;; (make-bst alon) creates a binary search tree using bsnode
;;   structures. The search tree holds the elements of the list
;;   of numbers alon.
;;
;;  general strategy:
;;     1. sort the list
;;     2. pick middle element of sorted list
;;        for the root of the tree
;;     3. build a bsnode with num from step 2.
;;         left node being a binary search tree
;;         made from all elements less than num,
;;         and right being a binary search tree made
;;        from all elements greater than num.


(define (make-bst alon)
  (local

   (
	;; select an item from a list given it's position in the list.
	(define (select-elem-at-pos pos alist)
	  (cond 
	   [(= 0 pos) (first alist)]
	   [else (select-elem-at-pos (sub1 pos) (rest alist))]))

	;; pick middle element from ordered list - just uses
	;; length/2 as index of the element we want.
	(define (pick-middle olon)
	  (select-elem-at-pos (floor (/ (length olon) 2)) olon))
	
	;; sublist consumes a value, a relational operator and a list
	;;  and produces a list.
	;;
	;; (sublist val op alist) uses the relation operator
	;;  op to filter the elements in alist according to thier
	;;  relationship with val.
	;;
	;;  if (op element val) is true, then element is one of the
	;;    items in the list produced. 
	;;  
	;;  For example, if alist is a list of numbers, op is <
	;;  and val is 7, sublist will return all the elements of
	;;    alist that are less than 7.
	;;
	;; usage: (sublist 7 < '(4 8 3 9 12))
	(define (sublist val op alist)
	  (cond
	   [(empty? alist) empty]
	   [(op (first alist) val) 
		(cons (first alist) (sublist val op (rest alist)))]
	   [ else
		 (sublist val op (rest alist))]))

	;; uses sublist to get a list of all elements in alist
	;; that are less than val
	(define (sublist-lessthan val alist)
	  (sublist val < alist))

	;; uses sublist to get a list of all elements in alist
	;; that are less than val
	(define (sublist-greaterthan val alist)
	  (sublist val > alist))
	)

   ;; beginning of the body of the local
   (cond 
	[(empty? alon) empty ]     ;; no elements - no tree
	[ else
	  (local
	   ((define sorted (sort alon))            ;; sort the list
		(define middle (pick-middle sorted)))  ;; pick middle element
	   ;; make a bst 
	   (make-bsnode
		middle
		;; left is a bst containing all elements less than middle
		(make-bst (sublist-lessthan middle sorted))
		;; right is a bst containing all elements greater than middle
		(make-bst (sublist-greaterthan middle sorted))))])))


;; test code
;;(make-bst '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15))