;;
;; myreverse consumes a list and returns a list
;; note that there is a real operation named reverse
;; (which does what we want) so we have to use a different
;;  name here.
;;
;; (myreverse alist) creates a new list that contains the same
;; elements as the list alist, but in reverse order.
;;
;; sample usage: (myreverse '(1 2 3))
;;
(define (myreverse alist)
  (cond 
    [(empty? alist) empty]
    [else
     (addright (first alist) (myreverse (rest alist)))]))

;; addright consumes a value and a list and produces a list.
;;
;;   (addright elem alist) will add elem to the right end of the
;;       list alist - the value of the function is this new list.
;; this is used by myreverse.
(define (addright elem alist)
  (cond
   [ (empty? alist) (cons elem alist) ]
   [ else
         (cons (first alist) (addright elem (rest alist)))]))



;; integer division with natural numbers 
;;
;;
;; divide consumes two numbers and returns a number.
;; also can generate an error (divide by 0)
;;
;; uses the relationship:
;;    x / y  = 1 + (x-y)/y 
;;

(define (divide x y)
  (cond
   [(= y 0) (error 'divide "Division by 0")]
   [(= x 0) 0]
   [(= y 1) x]
   [(< x y) 0]
   [else
	(add1 (divide (subtract x y) y))]))

;;
;; 
;; subtract natural numbers
;; subtract consumes two numbers and returns a number.
;; only handles natural numbers!
;; (subtract x y) produces the value x-y
;;  uses the relationship:
;;     x - y = (x-1) - (y-1)
;;
(define (subtract x y) 
  (cond 
   [(zero? y) x] 
   [ else 
	 (subtract (sub1 x) (sub1 y))]))

;; ========================================================
;;
;; functions that deal with sorted lists of numbers (slons).
;;
;; slons-insert consumes a number and a list and produces a list.
;;
;; (slons-insert x alist) inserts the number x into the 
;;  sorted list of numbers alist and returns the resulting list.
;;
;; sample: (slons-insert 3 '(1 2 4))
;;
(define (slons-insert x alist)
  (cond
   [(empty? alist) (cons x empty)]
   [(< x (first alist))
	(cons x alist)]
   [ else
	 (cons (first alist) (slons-insert x (rest alist)))]))
;;
;; tests
;;
;;(slons-insert 3 '(1 2 4 5 6))
;;(slons-insert 3 '(8 100 200 3000))
;;(slons-insert 3 '(0 1 2))

;;
;; sort-lons consumes a list and produces a list
;;
;; (sort-lons alist) creates a new list of numbers that contains all the
;;   elements of alist (which is a list of numbers), the new list
;;   is sorted in increasing order (smallest number is first).
;;
;; Note that this is not a very efficient way to sort a list of numbers,
;;  but it works...
;;
;; sample: (sort-lons '(3 1 45 99))
;;
(define (sort-lons alist)
  (cond
   [(empty? alist) empty]
   [else
	(slons-insert (first alist)
				  (sort-lons (rest alist)))]))

;;
;; tests
;;
(sort-lons '( 3 5 1 99 120 34 22))
(sort-lons '( 3 5))
(sort-lons '( 9 8 7 6 5 4 3 2  1))
(sort-lons '(1))

;;
;; search-lons consumes a list and a number.
;;
;; (search-lons alist x) searches the sorted list of
;;  numbers alist, looking for an element with the value
;;   x. If it finds x it returns true, otherwise it returns false.
;;
;; sample:
;;  (search-lons '(1 3 6 17 24 88) 3)

(define (search-lons alist x)
  (cond 
   [(empty? alist) false] 
   [(= (first alist) x) true] 
   [(> (first alist) x) false] 
   [ else 
	 (search-lons (rest alist) x)]))
;;
;; tests
;;
(search-lons '(1 2 4 65 199 2929) 2)
(search-lons '(1 2 4 65 199 2929) 2929)
(search-lons '(1 2 4 65 199 2929) 176)