;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; COPY THIS FILE  COPY THIS FILE  COPY THIS FILE  COPY THIS FILE
; THEN LOAD AND EDIT  THEN LOAD AND EDIT IT  THEN LOAD AND EDIT IT
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                        Compulsory Exercise 2.
;
;                  Binary Search of a sorted vector
;
;           Deadline: Friday the 7th of November at 12 o'clock
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;
; In binary search we are given a sorted vector v,  such that 
;
; (or (p< (vector-ref v i) (vector-ref v (+ i 1))) 
;     (p= (vector-ref v i) (vector-ref v (+ i 1))))
;
; is true for all i (i.e. the vector is sorted),
; an integer n, such that the vector runs from zero to n-1,
; and an element e that we are looking for. The binary search function
;
;                  (bin-search e v n p= p<)
;
; delivers #t if e is in v (with respect to predicate p=), otherwise 
; it delivers #f 
;
; bin-search looks at the middle element of the vector and tests
; to see if it is the same as e. If it is we deliver #t.
;
; If e is less than the middle element then e "might" exist in
; the left half of the vector (put another way, e cannot exists
; in the right half of the vector!) and we now perform a binary
; search on the left half of the vector. 
;
; Conversely, if e is greater than the middle element then e "might" 
; exists in the right half  of the vector (again, e cannot be in the left 
; half!) and we now perform a binary search in the right half of the vector.
;
; It could be the case that the vector is in fact empty. That is we are
; searching in a given half of the vector (after a number of recursive calls)
; and that half is essentially non-existant (exhausted). We can then quit 
; because e cannot be in the vector
;
; (0) Implement a linear search (lin-search e v n p< p=). 
;     Use it to debug and verify bin-search. That is, lin-search is easy 
;     to implement, and if lin-search finds e in v then so too should 
;     bin-search!! If it doesn't, then there is a bug!).
;
; (1) Implement a binary search function (bin-search e v n p= p<) as described
;     above (and in the lecture).
;
;     NOTE: the function MUST be polymorphic. The predicate p= will
;           test if e is equal to the element being examined and p<
;           will test if e is less than the element being examined
;           Fill out the skeleton at the end of this file
;
; (2) Test your function!!! Create data sets to test it out for situation
;     where e exists, doesn't exist, or exists in "extreme" positions
;
; (3) Test that your function works on vectors of numbers (see functions
;     file->sorted-vector and dictionary->vector) and on a vector
;     of characters (ie. that it is indeed polymorphic!)
;
;     (a) Function file->sorted-vector takes a filename that contains a 
;         bag of numbers, sorts them, and delivers them as a vector
;         Use this for large scale tests on integer
;
;     (b) Function dictionary->vector delivers as a result a vector of
;         approximately 25,000 words from the English dictionary (WARNING:
;         this is big, so do not dump it to the screen). Use this for
;         tests on character strings
;
; (4) Look at average, best, worst, and median performance of bin-search
;     over the dictionary.
;     (a) Modify bin-search so that it maintains a count of the number
;         of recursive calls made (that is, the number of times we have
;         "probed" the vector looking for e) (maybe use a global variable
;          as a counter)
;     (b) generate a random number i (use function random), and select
;         a word from the vector representing the dictionary at that
;         position (ie. (define rw (vector-ref v (random 25104))))
;     (c) look for that word rw in the vector (it must be there!) and
;         count how many probes were performed.
;     (d) Repeat this (maybe) 1,000 times and compute statistics on 
;         performance (see your first lab).
;
; (5) Answer the following question. 
;      In (4) above you have empirically measured the worst, median, and
;      average number of probes to find a word in a 25,104 word dictionary.
;      Are any of the measures in agreement with what we would expect,
;      knowing the computational complexity of binary search?
;
; (6) Repeat (4) and (5) but this time use the file of 1000 numbers, i.e. 
;     (define *v* (file->sorted-vector "/home/s7/pat/scheme/numbers/1000"))
;     NOTE: you need to change 4(b) accordingly.
;
; (7) Compare the performance of (lin-search e v n p< p=) to 
;     (bin-search e v n p= p<). That is, modify lin-search such that it
;     maintains a count of the number of times it checks to see if the
;     current vector element satisfies (p= (vector-ref v i) e).
;     Repeat (4), (5) and (6) using lin-search.
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                    
;                  Functions (and things) you might need
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (a) to test if two character strings are equal use string=?
;     and to test if one string is less than another use string<?
; (b) quotient, to find index of middle element within range being searched
; (c) vector-length, before calling search functions, to get n.
; (d) (define (log_2 x) (/ (log x) (log 2))) 
; (e) Hint for lin-search:
;      (do ((i 0 (+ i 1))) ((or (= i n) found not.present) found))
; (f) You will need your answer to ex0 for statistical analysis;     
;
;  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                         Functions you will use
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (dictionary->vector v)
  (let ((fin (open-input-file "/home/s7/pat/scheme/pub/dictionary.tex")))
    (do ((w (read fin) (read fin)) (i 0 (+ i 1)))
	((eof-object? w))
      (vector-set! v i (symbol->string w)))))
;;;
;;; Reads into a vector the 25,104 words in the above dictionary.
;;; The dictionary originated from /usr/dict/words but has
;;; all duplicates removed, and all sorted with respect to string<?
;;;
;;; Use as follows:
;;;
;;;          > (define *dict* (make-vector 25104))
;;;          > (dictionary->vector *v*)
;;;

(define (file->sorted-vector fname)
  (list->vector (sort (file->list fname) <)))
;;;
;;; Assume fname is the name of a file of numbers
;;; The function delivers a vector corresponding 
;;; to the numbers in that file sorted in increasing order
;;;
;;; Call it as follows
;;;
;;; > (define v (file->sorted-vector "/home/s7/pat/scheme/numbers/1000"))
;;;
;;; Of course, you could use a smaller set of numbers. See
;;; directory /home/s7/pat/scheme/numbers/
;;;

(define (sorted? v p< n)
  (let ((e1 nil) (e2 nil) (sorted #t))
    (do ((i 0 (+ i 1)))
	((= i (- n 1)) sorted)
      (set! e1 (vector-ref v i)) (set! e2 (vector-ref v (+ i 1)))
      (cond ((not (p< e1 e2))
	     (display (format nil "~S ~S ~S" i e1 e2)) (newline)
	     (set! sorted #f))))))
;;;
;;; Given a vector of n elements, is it sorted with respect to predicate p<
;;; You probably won't use this, but it is a check that a vector
;;; is sorted with respect to the predicate p<
;;; Might be usefull
;;;

(define (bin-search e v n p= p<)
  'define-me-and-test-me-please)

(define (lin-search e v n p< p=)
  'define-me-and-test-me-please)