Skip to content

Instantly share code, notes, and snippets.

@vishnuvyas
Created September 18, 2011 05:06
Show Gist options
  • Save vishnuvyas/1224750 to your computer and use it in GitHub Desktop.
Save vishnuvyas/1224750 to your computer and use it in GitHub Desktop.
A simple key-value style dictionary implementation in scheme (uses binary trees)
(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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment