A simple key-value style dictionary implementation in scheme (uses binary trees)

bintree-dict.scm

(define (make-table-cell key val)
  ;; make a symbol table - atleast one table is required.
  (cons (cons key value) (cons #f #f)))

;; some functions to access individual table cells
(define (get-key table-cell) (caar table))
(define (get-value table-cell) (cdr (car table)))
(define (get-left table-cell) (car (cdr table)))
(define (get-right table-cell) (cdr (cdr table)))

(define (set-key! table-cell key) (set-car! (car table-cell) key))
(define (set-value! table-cell value) (set-cdr! (car table-cell) value))
(define (set-left! table-cell left-val) (set-car! (cdr table-cell) left-val))
(define (set-right! table-cell right-val) (set-cdr! (cdr table-cell) right-val))

(define (add-pair! table pair)
  ;; adds a pair to our table - when the key is already present
  ;; returns #f
  (let ((key (car pair))
	(val (cdr pair))
	(table-key (get-key table)))
    (cond ((string=? key table-key) #f)
	  
	  ;; now when the key is lesser than key of the table
	  ;; we need to explore the left cell of the table.
	  ((string< key table-key)
	   (if (get-left table)
	       (add-pair! (get-left table) pair)
	       (set-left! table (make-table-cell key val))))

	  ;; now when the key is greater than the table-key
	  ;; we need to explore the right branch
	  ((string> key table-key)
	   (if (get-right table)
	       (add-pair! (get-right table) pair)
	       (set-right! table (make-table-cell) key-val))))))

(define (get-table-cell table key)
  ;; given a table return the table-cell where the key
  ;; was found else return #f
  (let ((tkey (get-key table))
	(tval (get-value table)))
    (cond ((string= key tkey) table)
	  ((string< key tkey)
	   (if (get-left table) 
	       (get-table-cell (get-left table) key)
	       #f))
	  ((string> key tkey)
	   (if (get-right table)
	       (get-table-cell (get-right table) key)
	       #f)))))


(define (get-value-alt table key alt)
  ;; simlar to get value but returns alt when a key is not found
  (let ((cell (get-table-cell table key)))
    (if cell (get-value cell) alt)))

(define (get-value table key)
  ;; given a table get its value - if no value is present then
  ;; returns #f
  (let ((cell (get-table-cell table key)))
    (if cell (get-value cell) #f)))

(define (make-table values)
  (if (null? values)
      #f
      (let ((tcell (make-table-cell (car (car values)) (cadr (car values)))))
	(for-each (lambda (x) (add-pair! tcell x)) (cdr values))
	tcell)))