;;; association lists

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

(define (find-assoc key alist)
  (let ((binding (find-assoc-binding key alist)))
    (if binding
        (cadr binding)
        #f)))

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

(define (add-assoc! key val alist)
  (let ((binding (find-assoc-binding key alist)))
    (cond (binding 
           (set-car! (cdr binding) val)
           alist)
          (else 
           (add-assoc key val alist)))))

;;; 1-d table abstraction

(define table1-tag 'table1)
(define (make-table1)
  (cons table1-tag '()))
(define (table1-get tbl key)
  (find-assoc key (cdr tbl)))
(define (table1-set! tbl key val)
  (set-cdr! tbl 
            (add-assoc! key val (cdr tbl))))

(define (table1-size tbl)
  (length (cdr tbl)))

;;; 2-d table abstraction

(define table2-tag 'table2)
(define (make-table2)
  (cons table2-tag (make-table1)))
(define (table2-get tbl key-row key-col)
  (let ((row (table1-get (cdr tbl) key-row)))
    ;; row is itself a table1!
    (if row
        (table1-get row key-col)
        #f)))
(define (table2-set! tbl key-row key-col val)
  (let ((row (table1-get (cdr tbl) key-row)))
    (if row
        (table1-set! row key-col val)
        (let ((new-row (make-table1)))
          (table1-set! new-row
                       key-col
                       val)
          (table1-set! (cdr tbl)
                       key-row
                       new-row)))))

(define (table2-size tbl)
  (define (add-up l sum)
    (if (null? l) sum
        (add-up (cdr l) (+ sum (car l)))))
  (add-up (map (lambda (binding) (table1-size (cadr binding)))
               (cdr (cdr tbl)))
          0))

;;; test case

(define test1 (make-table2))
(table2-set! test1 'a 'b 'a-b)
(table2-set! test1 'a 'c 'a-c)
(table2-set! test1 'b 'a 'b-a)
(table2-set! test1 'c 'a 'c-a)
(table2-set! test1 'b 'b '())