recitation 13: more mutation & trees

-------------------------------------------------------
(define (last-pair lst)
  (cond ((not (pair? lst)) (error "should be a pair!"))
	((null? (cdr lst)) lst)
	(else (last-pair (cdr lst)))))

(define (make-ring lst)
  (set-cdr! (last-pair lst) lst)
  lst)

(define (print-n-elements ring n)
  (cond ((null? ring) (error "not enough elements"))
        ((= n 0) (newline))
        (else (display (car ring))
              (display " ")
              (print-n-elements (cdr ring) (- n 1)))))

(define x (make-ring (list 1 2 3 4)))
(print-n-elements x 6)  ==>   1 2 3 4 1 2

* Write (insert-after! ring elt) and (insert-before! ring elt):

  (insert-after! x 'after)
  (print-n-elements x 10)  ==> 1 after 2 3 4 1 after 2 3 4
  (insert-before! x 'before)
  (print-n-elements x 10)  ==> 1 after 2 3 4 before 1 after 2 3

(define (insert-after! ring elt)
  (let ((tmp (cons elt (cdr ring))))
    (set-cdr! ring tmp)))
    
(define (insert-before! ring elt) 
  (insert-after! (backward ring) elt))

(define (backward ring) 
  (define (helper current)
    (if (eq? ring (forward current))
        current
        (helper (forward current))))
  (helper (forward ring)))

* What's the order of growth of insert-after! & insert-before!
    insert-after!:  O(1)     insert-before!:  O(n)

* How can we change the design of our ring data structure to make
  these operations O(1) time?
    use a doubly-linked list.  each element points to the next element, 
    like a regular list, but also to the previous element.  this could
    be done with two cons cells (or vectors of length 3!)

-------------------------------------------------------
(define (filter! f lst)
  (let ((root (cons '() lst)))
    (define (iter l)
      (cond ((or (null? l) (null? (cdr l))) '())
            ((f (cadr l)) (iter (cdr l)))
            (else
             (set-cdr! l (cddr l))
             (iter l))))
    (iter root)
    (cdr root)))

(define x (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))

x ==> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)

(define y (filter! even? x))

x ==> (1 2 4 6 8 10 12 14 16)
y ==> (2 4 6 8 10 12 14 16)

(define z (filter! (lambda (e) (= (remainder e 3) 0)) x))

x ==> (1 2 4 6 12)
y ==> (2 4 6 12)
z ==> (6 12)

-------------------------------------------------------
Huffman Encoding  (code from lecture: huffman.scm)

* why?

  Huffman encoding is a method for compression which reduces the
  number of bits needed for the most frequently occuring characters.

1. collect statistics 
   (define my-stats (stats "test"))

   my-stats ==>  ((s 1) (e 1) (t 2))

2. make-tree 
   (define my-tree (generate-huffman-tree my-stats))

   my-tree ==>  ((leaf t 2) ((leaf e 1) (leaf s 1) (e s) 2) (t e s) 4)

3. encode message
   (define my-encoded-message (encode (symbolize "set") my-tree))

   my-encoded-message ==>  (1 1 1 0 0)

4. decode message
   (define my-decoded-message (decode my-encoded-message my-tree))

   my-decoded-message ==>   (s e t)

* what happens if the message you want to encode contains symbols that
  aren't in the test message you collected statistics from?

  Error!  symbol can't be encoded