;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname 24bst-balance) (read-case-sensitive #t) (teachpacks ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp")))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; DEMO: balancing binary search trees
#|
DATA DEFINITION

A (bst X) is either:

  - false

  - (make-node left key value right)
    where `key` is a string, `value` is an X, `left` is a
    (bst X) in which all `key`s are *less than* this key,
    and `right` is a (bst X) in which all `key`s are
    *greater than* this key.
|#
(require "bst.rkt")

(define et false) ; empty tree
(define t1  ;; an example of (bst number)
  (make-node
     (make-node false "Guyer" 5 false)
     "Hescott" 7
     (make-node false "Ramsey" 8 false)))
(define t2  ;; an example of (bst symbol)
  (make-node
     false
     "Guyer" 'ast
     (make-node false
                "Hescott" 'lec
                (make-node false
                           "Ramsey" 'asc
                           false))))

(define t6 (make-node
            (make-node
             (make-node false "Brodley" 'learning false)
             "Couch" 'os
             (make-node false "Cowen" 'bio false))
            "Hescott" 'complexity 
            (make-node
             (make-node false "Mendelsohn" 'www false)
             "Ramsey" 'languages
             false)))
    ;; longest path to leaf = 3
    ;; shortest path to leaf = 2
    ;; Ratio = 3/2

; path-ratio : (bst X) -> number
; to return the ratio of the longest path to the shortest path in the given tree
(define (path-ratio tree)
  (cond [(false? tree) 1]
        [(node? tree) (/ (longest-path tree) (shortest-path tree))]))

;; longest-path : (number number -> number) (bst X) -> number
;; to combine the lengths of all paths in the tree, using combine,
;;   whihc should be associative
(define (combine-paths combine tree)
  (cond [(false? tree) 0]
        [(node? tree) 
         (add1
          (combine (combine-paths combine (node-left tree)) 
                   (combine-paths combine (node-right tree))))]))
(check-expect (longest-path t6) 3)
 
(define (longest-path t)
  (combine-paths max t))
(define (shortest-path t)
  (combine-paths min t))

(check-expect (path-ratio false) 1)
(check-expect (path-ratio t6) 3/2)
(check-expect (path-ratio t1) 1)

;(check-expect (path-ratio (treeify (inorder-list t6))) 6)


(require comp50/files)
(define-struct model (name ndistinct observations tree))

;; restore-models : string -> (listof model)
;; return models written by `save-models` to the given file
(define (restore-models filename)
  (map sx->model (read-file-sexp filename)))

;; sx->model : model-sx -> model
;; convert the given model-sx to a model
(define (sx->model sx)
  (make-model (first sx)
              (second sx)
              (third sx)
              (treeify (fourth sx))))

;; DATA DEFN
;; A (pair X Y) is (cons x (cons y empty)) where x is an X and y is a Y

;; to show the path ratio of each trigram model
;; model-ratio : model -> (pair name number)
(define (model-ratio m)
  (list (model-name m) (path-ratio (model-tree m))))