;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;    LAB 6
;;
;;    Solutions
;;
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   Part 1:  Data Definitions and Examples
;;

;;;; Code-tree Data Definition

;; A leaf is a
;; (make-leaf symbol number)
(define-struct leaf (symbol weight))

;; A code-tree is either a
;; --leaf, or
; (make-code-tree (listof symbols) number
;          code-tree
;          code-tree)
(define-struct code-tree (symbols weight left right))

;; and where the following two invariants hold
;;       (a) For each node, the sum of the weights of the left subtree
;; plus the sum of the weights of the right subtree is
;; the weight of the node.
;;       (b) For each node, the symbols in the list of symbols of the node are
;; all of the symbols occurring in leaves of the left subtree
;; and all of the symbols occurring in leaves of the right subtree. 


;;;;;;;;;;;;;;;;;;;;
;;;  Code-tree Examples from Part 1c and 1d
(define tree-1
  (make-code-tree '(A B C D E F G H) 8
                  (make-code-tree '(A B C D) 4
                                  (make-code-tree '(A B) 2
                                               (make-leaf 'A 1)
                                               (make-leaf 'B 1))
                                  (make-code-tree '(C D) 2
                                               (make-leaf 'C 1)
                                               (make-leaf 'D 1)))
                  (make-code-tree '(E F G H) 4
                                  (make-code-tree '(E F) 2
                                               (make-leaf 'E 1)
                                               (make-leaf 'F 1))
                                  (make-code-tree '(G H) 2
                                               (make-leaf 'G 1)
                                               (make-leaf 'H 1)))))
  
(define tree-2
  (make-code-tree '(A B C D E F G H) 17
                  (make-leaf 'A 8)
                  (make-code-tree '(B C D E F G H) 9
                                  (make-code-tree '(B C D) 5
                                                  (make-leaf 'B 3)
                                                  (make-code-tree '(C D) 2
                                                                  (make-leaf 'C 1)
                                                                  (make-leaf 'D 1)))
                                  (make-code-tree '(E F G H) 4
                                                  (make-code-tree '(E F) 2
                                                                  (make-leaf 'E 1)
                                                                  (make-leaf 'F 1))
                                                  (make-code-tree '(G H) 2
                                                                  (make-leaf 'G 1)
                                                                  (make-leaf 'H 1))))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   Part 3:  Encoding and Decoding
;;

;;;;;;;;;;;;;;;;;;;;;;;;
;;;  Part 3a. Encoding

;; A bit is either 0 or 1
;; encode: (list-of symbols) code-tree -> (list-of bits)
;; encode msg using ctree
;; (define (encode msg ctree) ... ) 

;; Use structural recursion on msg (a list)
(define (encode msg ctree)
  (cond
    [(empty? msg) empty]
    [else 
     (append (encode-symbol (first msg) ctree)
             (encode (rest msg) ctree))]))

;; encod-symbol: symbol code-tree -> (list-of bits)
;; encode symbol using ctree
;; Use structural recursion on ctree (a code-tree)
;; NOTE:  it is a good idea to produce an error message if
;;     a problem arises.  This will help you spot errors when testing
(define (encode-symbol s ctree)
  (cond 
    [(leaf? ctree) empty]
    [else
     (cond
       [(intree? s (code-tree-left ctree))
        (cons 0 (encode-symbol s (code-tree-left ctree)))]
       [(intree? s (code-tree-right ctree))
        (cons 1 (encode-symbol s (code-tree-right ctree)))]
       [else "encode-symbol:  symbol not found on tree"])]))

;; intree?: symbol code-tree -> boolean
;;  Does symbol occur in code-tree?  By invariant (b) we need
;;  only test symbols occuring at root of tree
(define (intree? s ctree)
  (cond
    [(leaf? ctree) (symbol=? s (leaf-symbol ctree))]
    [else
     (ormap (lambda (t) (symbol=? s t)) (code-tree-symbols ctree))]))

;;;;;;;;;;;;;;;;;;;;;;;;
;;;  Part 3b. Decoding

;; A bit is either 0 or 1
;; decode: (list-of bits) code-tree -> (list-of symbols)
;; decode bits (list-of bits) using ctree
;; (define (decode bits ctree) ... )

;;;; You can use structural recursion on bits and ctree simultaneously.
;;;;   The trick is that you need to remember the original ctree, and 
;;;;    recurring on decode will forget this tree.  Use local!!

(define (decode bits ctree)
  (local
      ((define (decode-1 bits t)
         (cond
           [(and (leaf? t) (empty? bits)) (list (leaf-symbol t))]
           [(leaf? t) (cons (leaf-symbol t)
                            (decode-1 bits ctree))]
           [(empty? bits) "decode:  Out-of-bits before reaching a leaf."]
           [else  
            (cond
              [(= 0 (first bits)) (decode-1 (rest bits) (code-tree-left t))]
              [(= 1 (first bits)) (decode-1 (rest bits) (code-tree-right t))]
              [else "decode:  Not a bit."])])))
    (decode-1 bits ctree)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   Part 4:  Building Code Trees
;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Part 4a. Frequency Lists

;; An fpair is a
;; (make-fpair symbol weight)
(define-struct fpair (symbol weight)) 


;; create-leaves: (list-of fpair) -> (list-of leaf)
;; Create a list of leaves from list of fpairs
;; (define (create-leaves fpairs) ...) 
(define (create-leaves fpairs)
  (map (lambda (x) (make-leaf (fpair-symbol x) (fpair-weight x))) fpairs))

;;;  Examples:
(define freq-1 (list
                (make-fpair 'A 1)
                (make-fpair 'B 1)
                (make-fpair 'C 1)
                (make-fpair 'D 1)
                (make-fpair 'E 1)
                (make-fpair 'F 1)
                (make-fpair 'G 1)
                (make-fpair 'H 1)))

(define freq-2 (list
                (make-fpair 'C 1)
                (make-fpair 'D 1)
                (make-fpair 'E 1)
                (make-fpair 'F 1)
                (make-fpair 'G 1)
                (make-fpair 'H 1)
                (make-fpair 'B 3)
                (make-fpair 'A 8)))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Part 4b. build-code-tree


;; build-code-tree: (list-of s-w-p) -> code-tree
;; return a code-tree based on fpairs giving the frequency of each symbol.
;; fpairs is sorted in increasing order of weight
;; (define (build-code-tree fpairs) ... ) 
(define (build-code-tree fpairs)
  (local
      ((define leaves (create-leaves fpairs)))
    (first (merge-trees leaves))))


;; merge-trees: (list-of code-trees) -> (list-of code-trees)
;; Merge alocts as in step 2 of the algorithm in Part 1b
;; until alocts contains only one code-tree
;;  INVARIANT:  The alocts is sorted by increasing order of weight.
;; (define (merge-trees alocts)...) 

(define (merge-trees alocts)
  (cond
    ;; should not occur, unless original list is empty
    [(empty? alocts) "merge-trees:  alocts is empty"] 
    [(empty? (rest alocts)) alocts]
    [else
     (local
         ((define rest-alocts (rest (rest alocts)))
          ;; Step 2a:  alocts is already sorted
          (define ct1 (first alocts))
          (define ct2 (first (rest alocts)))
          ;;Step 2b:
          (define new-ctree 
            (make-code-tree (append-syms ct1 ct2)
                            (+ (get-wt ct1) (get-wt ct2))
                            ct1 
                            ct2))
          ;; Step 2c
          (define new-alocts (insert-tree new-ctree rest-alocts)))
       (merge-trees new-alocts))]))

;;;;;;;;;;;;;;;;;;;;;;;
;;;;  Helper functions for merge-tree

;;  append-syms:  code-tree code-tree -> (list-of symbols)
;;    append symbols in ct1 and ct2 into single list
(define (append-syms ct1 ct2)
  (local
      ((define s1 (cond
                   [(leaf? ct1) (list (leaf-symbol ct1))]
                   [else (code-tree-symbols ct1)]))
       (define s2 (cond
                    [(leaf? ct2) (list (leaf-symbol ct2))]
                    [else (code-tree-symbols ct2)])))
    (append s1 s2)))

;; get-wt:  code-tree -> number
;;   returns weight of tree
(define (get-wt t)
  (cond
    [(leaf? t) (leaf-weight t)]
    [else (code-tree-weight t)]))

;; insert-tree: code-tree (list-of code-tree) -> (list-of code-tree)
;;    insert ct into lcts ordered by weight
(define (insert-tree ct lcts)
  (cond
    [(empty? lcts) (list ct)]
    [else
     (cond
       [(< (get-wt ct) (get-wt (first lcts)))
        (cons ct lcts)]
       [else (cons (first lcts)
                   (insert-tree ct (rest lcts)))])]))
;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;