;; Sid Stamm
;; C211 lab number 7: Data abstraction & Trees!
;; 10-13-2003


;; REMINDERS:

; Help session
; Sunday 10/19 LH102
; 2-3
; 3-4
; Exam on Tuesday: 7:00pm
; Morrison Hall (Section 1463/1420) (Rick)
; Jordan Hall 124 (1464/1421 1665/1422) (Mihir)
; Jordan Hall A100 (Section 1475) (Ian)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Data Abstraction
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; We have this tool called define-record that lets us
;; construct data types.  This is great, because we don't
;; have to pass lists around without any constraints; the
;; record, when defined, comes with a predicate to check
;; if something is a valid record, as well as accessor
;; methods!

;; What the hell?  Well, the predicate helps you determine
;; whether or not something is of that type.  The accessors
;; let you get pieces of the data.

;; For Example, lets define a record that remembers a range
;; within natural numbers: interval.
(define-record interval (bottom top))

;; The record contains a bottom and top of an interval, and
;; we can make intervals as follows:

(let ([i1 (make-interval 1 12)]
      [i2 (make-interval 5 20)])
  (list i1 i2))
;(#[#{interval |-NyHUfo4XdZ~=\\%|} 1 12]
;  #[#{interval |-NyHUfo4XdZ~=\\%|} 5 20])

;; UGH!  That's hideous.  Those garbage symbols are gensyms.
;; Gensyms are unique identifiers that are never the same.
;; In this way, we can make two intervals with the same
;; value, but they are not =.

;; Lets not look at them again.
(print-gensym #f)

;; Same let-expression ...
;(#[interval 1 12] #[interval 5 20])

;; Aah.  Much better.  Now, check this one out:
(let ([i1 (make-interval 1 2)]
      [i2 (make-interval 1 2)])
  (list (equal? i1 i2) (eqv? i1 i2) (eq? i1 i2)))
;(#f #f #f)

;; Wow, they're the same interval, but scheme can
;; tell them apart.  REMEMBER THIS.  If you want to
;; compare the values of two different records you have
;; to do it manually.

;; Records are cool, because you can extract the fields
;; by name.  Remember the first thing we did?  We defined
;; interval to have a bottom and a top.  It's this
;; easy to get the bottom or top out of any interval:
(let ([i1 (make-interval 12 25)])
  (interval-top i1))
;25

;; Woohoo!  We can also see if something is an interval...
;; Remember map?
(let ([i1 (make-interval 12 25)]
      [i2 'not-an-interval])
  (map interval? (list i1 i2)))
;(#t #f)

;; So by defining interval using define-record, we have been
;; given interval? and interval-top and interval-bottom.
;; In general, if you define:
;;   (define-record x (f1 f2 ...))
;;
;; You get:
;;  x? predicate
;;  x-f1, x-f2, x-... accessor methods
;;
;; Slick!  We can do less caring and cdring. (Caring not to
;; be mistaken for CAREing.)


;; Lets define a predicate overlap? that looks to see if the
;; intervals overlap.  Say we're given two intervals:
(define i1 (make-interval 1 5))
(define i2 (make-interval 4 7))

;; This is what they "look" like:
;;  + 0 1 2 3 4 5 6 7 8 9
;; i1   x-------x
;; i2         x-----x
;;
;; We consider them overlapping if the endpoints (x's)
;; are on top of eachother too.
;;
;; Mathematically: if any number n exists in i1 and i2,
;; they overlap.  Let's construct a helper contains? first
;; to make life easier.
;; n is in an interval if it is GREATER THAN OR EQUAL TO
;; that interval's bottom AND it is LESS THAN OR EQUAL TO
;; that interval's top:
(define contains?
  (lambda (n iv)
    (and (>= n (interval-bottom iv))
	 (<= n (interval-top iv)))))

;; When do two overlap, well if the top or bottom of one
;; exists in the other, they overlap.

;; Here's a procedure definition for overlap?:
(define overlap?
  (lambda (i1 i2)
    (or (contains? (interval-bottom i1) i2)
	(contains? (interval-top i1) i2)
	(contains? (interval-bottom i2) i1)
	(contains? (interval-top i2) i1))))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Trees
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Now, we can define a record type that represents trees!
;; Binary tree nodes have a left node, right node and a value.
;; Each node can be null, too.
;;
;; TREE = () OR (make-tree x TREE TREE)
;; for some datum x (string, literal, number, list...)
;;
;; Visually:
;;       TREE=      (x)
;;                  / \
;;                 T   T
;;
;; This code is taken from the homework:
(define-record tnode (data left right))
(define t0
  (make-tnode 4
	      (make-tnode 2 '() '())
	      (make-tnode 6 '() '())))

;; This looks like:
;; t0 =              (4)
;;                   / \
;;                  /   \
;;                (2)   (6)
;;                / \   / \
;;               () () () ()


;; The provided record predicate tree? only checks
;; if it is the right data type, it doesn't enforce
;; integrity.  What is that?  Well, we said tnodes
;; could only be an empty list or a value and two
;; tnodes.  But we can do this:
(tnode? (make-tnode 15 1 2))
;#t

;; It's a valid tnode, but not really a good binary tree.
;; So we have to write our own.
;; This code, also taken from the homework:
(define tree?
  (lambda (t)
    (or (null? t)
	(and (tnode? t)
	     (tree? (tnode-left t))
	     (tree? (tnode-right t))))))

(tree? (make-tnode 15 1 2))
;#f

;; Cool.  But how about if we ENFORCE the creation of good
;; trees so we don't have to go through the entire tree
;; every time we want to know if it is a good tree?
;; Let's make a procedure that always constructs good trees.
(define tree
  (lambda (data left right) 
    (define tree? (lambda (x) (or (null? x) (tnode? x))))
    (unless (tree? left) (error 'tree "~s is not a tree" left))
    (unless (tree? right) (error 'tree "~s is not a tree" right))
    (make-tnode data left right)))

;; Now we have to quit using make-tnode to construct our trees,
;; and rely only on tree.  This is okay though, because each
;; time we make a node it is checked for integrity.  The trees
;; made with tree will never be bad.
(tree 4 '() '())
;#[tnode 4 () ()]

(tree 4 5 6)
;Error in tree: 5 is not a tree.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; TRAVERSALS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; YAY!  Now lets play with traversals.
;; There are three types of binary tree traversals:
;; - Preorder traversal
;; - Inorder traversal
;; - Postorder traversal.
;;
;; Playing left to right, this is how they work
;; PREORDER (me-first):
;;   returns the value of the current node
;;       then the preorder traversal of the left child
;;       then the preorder traversal of the right child
;; INORDER (me-in-order):
;;   returns the inorder traversal of the left child
;;       then the value of the node
;;       then the inorder traversal of the right child
;; POSTORDER (me-last):
;;   returns the postorder traversal of the left child
;;       then the postorder traversal of the right child
;;       then the value of the node.
;;
;; Given t0 as defined above:
;; t0 =              (4)
;;                   / \
;;                  /   \
;;                (2)   (6)
;;                / \   / \
;;               () () () ()
;;
;; PREORDER  = (4 2 6)
;; INORDER   = (2 4 6)
;; POSTORDER = (2 6 4)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; BINARY SEARCH TREES (BST)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; A binary search tree is a binary tree like the ones we have
;; defined, but they have the following properties:
;;  ... for any node tn,
;; (tnode-data tn) > (tnode-data (tnode-left tn))
;; (tnode-data tn) <= (tnode-data (tnode-right tn))
;;
;; In general, all the nodes that are in a node's left tree
;; will all be less than that node, and the ones on the right
;; are greater than or equal to that node!

;; Example:
;; bst1 =              (4)
;;                    /   \
;;                  /       \
;;                (2)       (6)
;;                / \      /   \
;;               () ()    ()   (7)
;;                             / \
;;                            ()  ()
;; This IS a binary search tree

;; bst2 =              (4)
;;                    /   \
;;                  /       \
;;                (5)       (6)
;;                / \      /   \
;;               () ()    ()   (2)
;;                             / \
;;                            ()  ()

;; The cool thing about BST's, you can just add something
;; to one of the nodes at the bottom, and it's sorted using
;; an inorder traversal!  You can always do an inorder and
;; get a sorted list.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; EXERCISES
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Now it's time for the weekly workout!

;;;;;;;;;;;;;;;;;;;;
;; EXERCISE 1:
;;;;;;;;;;;;;;;;;;;;

;; Write a procedure interval-add that takes two interval
;; records as defined before, and returns the interval
;; representing their merging.  For example, adding the
;; intervals 1-4 and 2-6 would be 1-6.
;; Likewise, two disjoint intervals (like 1-2 and 5-10)
;; cannot be added, and interval-add should throw an error.

;; SOLUTION

(define interval-add
  (lambda (i1 i2)
    (if (overlap? i1 i2)
        (make-interval 
          (min (interval-bottom i1) (interval-bottom i2))
          (max (interval-top i1) (interval-top i2)))
        (error 'interval-add "Intervals do not overlap"))))

;; Example tests:

(interval-add (make-interval 1 5) (make-interval 4 7))
;#[interval 1 7]
(interval-add (make-interval 5 10) (make-interval 1 2))
;Error in interval-add: Intervals do not overlap.

;; HINT: use overlap? as defined in class to see if they
;; are disjoint.
;; HINT2: use max and min
;; HINT3: use the error expression to generate an error.



;;;;;;;;;;;;;;;;;;;;
;; EXERCISE 2:
;;;;;;;;;;;;;;;;;;;;

;; Write a procedure called prune that prunes a tree!  That is,
;; it takes one parameter (t) and removes all the nodes that
;; have empty lists for both children.

;; Pruning of t0 as we've seen in lab and homework would result
;; in an empty tree!

;; SOLUTION
(define prune
  (lambda (t)
    (if (null? t)
	'()                               ;; can't prune an empty tree!
	(if (and (null? (tnode-left t))
		 (null? (tnode-right t)))
	    '()
	    (tree (tnode-data t)
		  (prune (tnode-left t))
		  (prune (tnode-right t)))))))
;; for testing:
(define t1
  (tree 4
	(tree 2
	      (tree 1 '() '())
	      (tree 3 '() '()))
	(tree 6
	      (tree 5 '() '())
	      (tree 7 '() '()))))

;; TESTS:

;; t0 =              (4)
;;                   / \
;;                  /   \
;;                (2)   (6)
;;                / \   / \
;;               () () () ()

;; prune t0 =        ()
(prune t0)
;#[tnode 4 () ()]

;; Take a more complex tree:

;; ta =                (4)
;;                    /   \
;;                  /       \
;;                (2)       (6)
;;                / \      /   \
;;               () ()    ()   (2)
;;                             / \
;;                            ()  ()

;; prune ta =        (4)
;;                   / \
;;                  /   \
;;                 ()   (6)
;;                      / \
;;                     () ()
(prune (tree 4 (tree 2 '() '()) (tree 6 '() (tree 2 '() '()))))
;#[tnode 4 () #[tnode 6 () ()]]

;; Notice both nodes containing 2 were removed
;; since they were the only ones with two empty children.

;; ASSUME it is a proper tree: i.e. it was defined
;; using the tree constructor defined in the homework
;; and in lab.


;;;;;;;;;;;;;;;;;;;;
;; EXERCISE 3
;;;;;;;;;;;;;;;;;;;;

;; For a-c, it is okay to just draw the tree diagrams (no code) in
;; your lab book.

;; a) Create a binary search tree that contains only one number: 4.
;; b) Add the value 9 to that tree
;; c) Add the following values in order they're given: 15 2 13 6 4.

;; HINT: remember, if a number it is equal, it is added on the
;;       right sub-tree.

;; d) write a procedure, bst-max that takes one argument: a binary
;;    search tree.  Have it return the largest data value in the
;;    tree.  (This should be quite simple, but tail recursive.)


;; SOLUTION

;; a)
(tree 4 '() '())

;; b)
(tree 4 '() (tree 9 '() '()))

;; c)
(tree 4
      '()
      (tree 9
	    '()
	    (tree 15 '() '())))
(tree 4
      (tree 2 '() '())
      (tree 9
	    '()
	    (tree 15
		  (tree 13 '() '())
		  '())))
(tree 4
      (tree 2 '() '())
      (tree 9
	    (tree 6 '() '())
	    (tree 15
		  (tree 13 '() '())
		  '())))
(tree 4
      (tree 2 '() '())
      (tree 9
	    (tree 6
		  (tree 4 '() '())
		  '())
	    (tree 15
		  (tree 13 '() '())
		  '())))


;; d)
(define bst-max
  (lambda (t)
    (if (null? t)
	(error 'bst-max "Tree is null!")  ;; invalid tree!
	(if (null? (tnode-right t))
	    (tnode-data t)                ;; nothing bigger
	    (bst-max (tnode-right t)))))) ;; something bigger (on the right)