recitation 12: association lists & hash tables

----------------------------------------------------------
tradeoff: concrete structures that are very efficient but prone to misuse
                                    vs.
          abstract structures that nicely insulate the implementation
          from its use but may suffer from efficiency issues

robust-ness, modularity, & ease of use will often triumph over speed

abstract data types (ADT)
 * abstraction of implementation from use
 * can write down types of the constructor/selectors & predicates
   but don't know the guts  It's not in the contract (unspecified).

----------------------------------------------------------
association list: (alist)  List of 2 element lists (key value)

(define (find-assoc key alist)
   (cond
    ((null? alist) #f)
    ((equal? key (caar alist)) (cadar alist))
    (else (find-assoc key (cdr alist)))))

(define (add-assoc key val alist)
  (cons (list key val) alist))

(define *phone-book*
  (list (list 'alice 6175551212)
	(list 'bob   6175555237)
	(list 'carol 6175556824)))

* write code to get bob's number

* what happens if you look up dan's number?

* write code to add erin's number

* if there are 50,000 phone numbers in *phone-book*, how
  long does it take to look up a person's number, on average?

* write code to add bob's new number

* what happens to his old number?

* write code to return the list of all the numbers ever stored 
  for a particular person, in chronological order

----------------------------------------------------------
mutation

* redefining at the top level is sort-of mutation, but we'll 
  learn REAL mutation on Tuesday & Wednesday

* convention: procedures that end in ! (pronounced "bang!") 
  are mutators

----------------------------------------------------------
vectors: (a.k.a. arrays, "efficient lists")

* vectors are fixed length 
* retrieval in O(1) (it's O(n) for lists)

  (make-vector k)             k is length of vector, initialize entries to #f
  (vector-ref vector k)       returns the kth element of vector
  (vector-set! vector k obj)  sets the kth element of the vector to obj

(define *students* (make-vector 5))
*students*  -->  #(#f #f #f #f #f)

(vector-set! *students* 0 'bob)
(vector-set! *students* 3 'alice)

*students*  -->  #(bob #f #f alice #f)

(vector-ref *students* 3)  ->  alice

* can you re-implement make-vector & vector-ref using cons?  
  (ignoring efficiency) 

----------------------------------------------------------
table: list of bindings/pairings of a key and a value
   (make-empty-table)   O(1)
   (put! key value)     O(1)
   (get key)            O(n)

hash tables: vector of bindings/pairings of a key and value
   the key is mapped to an index by a hash function

hash functions: "uniformly" distributes the keys throughout the
   range of legal index values (0 -> k-1).  "chooses a bucket".

collisions: multiple keys often map to same index.  Store an
   association list at each index.

hash tables:
   (make-empty-table)   O(n)  need to create & initialize the vector
   (put! key value)     O(1)  if the hash function is easy to compute
   (get key)            O(1)  for a "good" hash function, and a big 
                              enough vector

* other than the efficiency of operations, all the functions have the 
  same type and we can use a table without knowing the implementation

----------------------------------------------------------
hash table application: caller id

* given *phone-book* (an association list with 50,000 
  name/number pairings) write code to lookup the name 
  matching a particular phone number

* name lookup should be O(1) time expected

* the caller id system should use O(n) memory (n = 50,000)

(define *phone-book*
  (list (list 'alice 6175551212)
        (list 'bob   6175555237)
        (list 'carol 6175556824)))

(define *caller-id-length* 50000)

(define (make-caller-id-hash-table phone-book)
  (if (null? phone-book)
      (make-vector *caller-id-length*)
      (let ((answer (make-caller-id-hash-table (cdr phone-book))))
        (add-number (caar phone-book) (cadar phone-book) answer)
        answer)))

(define (add-number name number caller-id)
  (let ((index (phone-number-hash-function number)))
    (vector-set! caller-id index (cons (list name number) 
                                       (vector-ref caller-id index)))))

(define (phone-number-hash-function number) (modulo number *caller-id-length*))

(define (lookup-name number caller-id)
  (lookup-name-in-alist 
   number (vector-ref caller-id (phone-number-hash-function number))))

(define (lookup-name-in-alist number alist)
  (if (null? alist) 
      (error "unknown caller")
      (if (= (cadar alist) number) (caar alist)
          (lookup-name-in-alist number (cdr alist)))))

(define *caller-id* (make-caller-id-hash-table *phone-book*))

(lookup-name 6175555237 *caller-id*)   ->   bob

----------------------------------------------------------
real world hash table application: ray tracing 

   (... if we have time)

----------------------------------------------------------