CSC151 2007S, Class 38: Representing Color Palettes with Vectors

* Normal start-of-class time for discussion of campus issues.

Admin:
* EC for  ...
  * attending tonight's Con Brio concert (9:30 in the pub).
  * attending Thursday noon applied studio recital in Sebring-Lewis.
  * attending Thursday 4:15 talk on Calculus for Dogs.
  * attending Friday noon or evening talk by Patch Adams.
  * attending Saturday Evening's 10:00 p.m. RHPS.
  * Participating in the following: Jonathan Tsu and Ian Young are conducting a usability study on the Grinnell CS Department website as a project for Human-Computer Interaction.  They are looking for students currently taking Fundamentals of CS to take part.  The study should take about twenty minutes to complete.  Email [youngian] if you are interested.  
* Reading for Friday: Analyzing Algorithms (ready Thursday).
* Thanks for the stupid profquote.  (Yes, I did accept it.)

Overview:
* Problems with lists.
* A solution: Vectors.
* Important vector procedures.
* Representing palettes with vectors.
* Lab.

==Back to Lists==

* A list is ...
  * An ordered bunch of elements (which Biologists or Biological Chemists 
    would call "polarity")
  * Grouped together
  * "Growable"
* Basic list operations plus one basic value
  * car cdr cons null? null
* But lots of operations built on top of those
  * list-ref, reverse, index-of, member, ...
* Lists are
  * Hard to change?
  * Expensive to randomly access
* Hard to change:
  * Given a list, lst, change the fifth element to E
    (cons (car lst) 
          (cons (cadr lst) 
                (cons (caddr lst) 
                      (cons (cadddr lst)
                            (cons 'E
                                  (cdddddr))))))
  * And that horrid expression didn't even change the list, it built a
    new list

The Solution: Design another data type
* Easier to change
* Faster to get to elements

The Strategy: Reserve a chunk of memory
* Fixed size
* Broken up into regular cells, each of which holds a value
* Basic math gives you the loocation of any cell
  * Suppose the chunk starts at memory location v, and each cell is w wide.
  * Where is element 3?
    v + 3w
THese reserved chunks of memory are called "vectors"

Basic vector operations:
* (vector _ _ _ _ _)
* (make-vector size _)
* (vector-ref vec pos) - Equally Fast for any element of vector 
  * (in constrat to list-ref, which requires pos cdrs
* (vector-set! vec pos newval)
* (vector-length vec)

Using vectors for palettes
* Close your eyes and envision the whiteboard that I drewe
* Key points:
  * Reloading an image from the encoding requires LOTS of cdring through the
    list
  * A vector is an appropriate replacement