```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
```