;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                      Exercise 4
;
;                      Compulsory
;
;        Complete by: Friday 21st November at 12 o'clock
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;
;         An experiment in searching, using binary trees. 
;
; It was said in the lecture that if we insert a set of values into a binary 
; tree we might expect that on average the height of that tree will be
; log n (base 2) and that we would then expect good search time
; of order log n. How confident are we in that statement?

; The following exercise carries out a series of experiments to investigate
; just how balanced binary trees are, on average. We will do this by generating
; unordered sets of integers (via function make-unordered-set) and then
; inserting the elements of a set into a binary tree (see function insert!
; in /home/s7/pat/scheme/pub/btree.scm). We must then compute the height
; of the binary tree, where the height is the length of the longest path
; in the tree. We do this for a number of different sets of size n, 
; and then compute statistics on the list of heights that we have collected
; (and you should use the functions from ex1 to do this).
;
; We then repeat the experiments, using different sized sets (for example 
; sets of size 8, 16, 32, 64, 128, 256, 512) with sample sizes of (say) 50?
; We then compute the average height of a binary tree with n nodes,
; for various values of n, assuming that the values are inserted
; into the binary tree in a random order.
;
;
; 1. You will require the following files:
;    /home/s7/pat/scheme/pub/btree.scm ... for binary tree stuff
;    /home/s7/pat/scheme/pub/ex4.scm  ... (this file) for functions below
;    /home/s7/pat/scheme/pub/ans0.scm ... to analyse your data
;
;
; 2. Define the function (height bnode). See below for details
;
; 3. Define the functions (get-heights n m) and (stats-btrees n m). 
;    See below for details
;
; 4. Do a set of experiments (using stats-btrees) to answer the question:
; 
;    "Given an unordered set of n integers, if they are inserted
;     into a binary tree, what will be the height of that tree on average?"
;


(define (make-unordered-set n)
  (do ((i 1 (+ i 1))
       (l '() (cons i l)))
      ((> i n) (randomise l))))
;;;
;;; Deliver the set of numbers, 1 to n, in no specific order
;;;


(define (height bnode)
  (cond ((empty? bnode) 0)
	(#t (+ 1 (max (height (left bnode)) (height (right bnode)))))))
;;;
;;; Compute the height of a binary tree, where
;;; the height is the length of the longest path in
;;; the binary tree with root bnode
;;;
;;; (a) If the bnode is empty its height is 0
;;; (b) otherwise height is the maximum of
;;;     the height of the left branch +1 and
;;;     the height of the right branch +1
;;;
;;; NOTE: test this out on small trees first,
;;;       so that we have a visual check. use function
;;;       height-of n below. Fore example ...
;;;
;;;      (height-of 2), (height-of 3), (height-of 4), ...
;;;

(define (height-of n)
  (let* ((l (make-unordered-set n))
	 (b (insert! (car l) empty <))
	 (e nil))
    (do ((values (cdr l) (cdr values))) ((null? values))
      (set! e (car values))
      (insert! e b <))
    ;(draw-btree b)
    (height b)))
;;;
;;; Generate a random set of size n, using function make-unordered-set, 
;;; and then insert all of the elements of that set into a binary tree.
;;; Draw the binary tree. 
;;; Then measure the height of that binary tree.
;;;

(define (get-heights n m)
  (cond ((= 0 m) '())
	(#t (cons (height-of n) (get-heights n (- m 1))))))
;;;
;;; Generate m binary trees, where each binary tree corresponds to the 
;;; insertion of a uniquely generated set of integers of size n
;;; Get the heights of those binary trees and deliver as a list of 
;;; heights.
;;;
;;; NOTE: use function (height-of n) called in a do loop m times, 
;;;       or do it recursively.
;;;

(define (stats-btrees n m)
  (/ (apply + (get-heights n m)) m))
;;;
;;; What is the average height of a binary tree that contains 
;;; n integers, inserted from an unordered set? Also, maximum, 
;;; minimum, and median.
;;;
;;; We have a sample of size m (typically m should be at least 40
;;; to be significant)
;;;
;;; Do this for various values of n and m, in particular
;;;
;;;            n = 8, 16, 32, 64, 128, 256
;;;            m = 50
;;;

(define (test lo hi inc m fname)
  (let ((fout (open-output-file fname)))
    (do ((i lo (+ i inc))) ((> i hi))
      (display (format nil "~S ~S ~S" 
		      i (stats-btrees i m) (/ (log i) (log 2)))
	       fout)
      (newline fout)
      (print i)
      (force-output fout))
    (close-output-port fout)))