;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                  Binary Search of a sorted vector
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define *trace* #f)
;;;
;;; Boolean, #t we get trace out of bin-search.
;;; NOTE: old hippy convention of naming global variables in stars
;;;

(define (bin-search e v n p< p=)
  (define (bin-search' e v lwb upb)    	                                 ;(0)
    (cond (*trace* (display (format nil "~S ~S" lwb upb)) (newline)))    ;(1)
    (cond ((< upb lwb) #f)                                               ;(2)
	  (else (let* ((mid (quotient (+ lwb upb) 2))                    ;(3)
		       (e.of.v (vector-ref v mid)))                      ;(4)
		  (cond ((p= e e.of.v) #t)                               ;(5)
			((= lwb upb) #f)                                 ;(6)
			((p< e e.of.v) (bin-search' e v lwb (- mid 1)))  ;(7)
			(else (bin-search' e v (+ mid 1) upb)))))))      ;(8)
  (bin-search' e v 0 (- n 1)))                                           ;(9)
;;;
;;; Binary search ... all the work is done via the inner function bin-search'
;;;
;;; ASSUME THAT: v is a vector sorted with respect to p<, and that
;;;              v runs from (vector-ref v 0) to (vector-ref v (- n 1))
;;;
;;; (0) lwb is "lower bound" and upb is "upper bound", v is vector, e is
;;;     element we are looking for. We expect e to be somewhere in v
;;;     between (vector-ref v lwb) and (vector-ref v upb). 
;;; (1) Give me a trace if *trace* is true. This will just display
;;;     lwb and upb on each call. Turn on by (set! *trace* #t)
;;; (2) If upb is less than lwb, things got crossed, and we are
;;;     no looking in an empty space, and e can't be there!
;;; (3) Get the middle position in the vector, call it mid (why not?)
;;; (4) get the element from the vector at the mid position, call 
;;;     e.of.v (again, why not? It's my function, isn't it?)
;;; (5) If e is equal to the mid element, e.of.v, we've found it.
;;;     Deliver true (#t)
;;; (6) If e is NOT equal to e.of.v and lwb=upb then we have zoomed into
;;;     our last choice and this aint it, so cant be there, so deliver #f
;;; (7) If e is less than e.of.ve then search in the left side of the vector
;;; (8) e is not equal to e.of.v, and is not less than e.of.v, so
;;;     might be in right side of vector, so go search there
;;; (9) Call to inner function, with lwb set to 0, and upb set to n-1
;;;

(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<?
;;;

(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<
;;;



(define (get-random-word dictionary)
  (vector-ref dictionary (random (vector-length dictionary))))

(define (lin-search e v p= p<)
  (let ((found #f) 
	(not.present #f)
	(n (vector-length v)))
    (do ((i 0 (+ i 1)))
	((or found not.present (= i n)) found)
      (set! found (p= e (vector-ref v i)))
      (set! not.present  (p< e (vector-ref v i))))))


(define (linear-search e v p= p<)
  (define (ls e v p= p< i n)
    (cond ((= i n) #f)
	  ((p= e (vector-ref v i)) #t)
	  ((p< e (vector-ref v i)) #f)
	  (#t (ls e v p= p< (+ i 1)))))
  (ls e v p= p< 0 (vector-length v)))