Ex-3.26

This is an implementation of one dimensional table, where (key, value) records are organized in a binary tree.

;here is the binary tree implementation
;constructor
(define (make-tree entry left right)
  (list entry left right))
;selectors
(define (entry tree)
  (car tree))
(define (left-branch tree)
  (cadr tree))
(define (right-branch tree)
  (caddr tree))
;mutator
(define (set-left-branch! tree value)
  (set-car! (cdr tree) value))
(define (set-right-branch! tree value)
  (set-car! (cddr tree) value))


;here is the one dimensional table impl
;using above interface

;assume there is a compare procedure for the set
;of keys, that returs -1,0,+1 if key1 is less than key2,
;key1 is equal to key2, key1 is greater than key2
;respectively
(define (compare key1 key2) ...)
;for numeric keys following is what the compare will
;look like
(define (compare key1 key2)
  (cond
   ((= key1 key2) 0)
   ((< key1 key2) -1)
   (else 1)))

(define (make-table)
  (cons '*table* nil))
(define (insert! key value table)
  (define (insert-aux! tree)
    (let* ((record (entry tree))
           (index (compare key (car record))))
      (cond
       ((= index 0) (set-cdr! record value))
       ((< index 0)
        (if (null? (left-branch tree))
            (set-left-branch!
             tree
             (make-tree (cons key value) nil nil))
            (insert-aux! (left-branch tree))))
       (else
        (if (null? (right-branch tree))
            (set-right-branch!
             tree
             (make-tree (cons key value) nil nil))
            (insert-aux! (right-branch tree)))))))
  (if (null? (cdr table))
      (set-cdr! table (make-tree (cons key value) nil nil))
      (insert-aux! (cdr table))))
(define (lookup key table)
  (define (lookup-aux tree)
    (if (null? tree) #f
        (let* ((record (entry tree))
               (index (compare key (car record))))
          (cond
           ((= index 0) (cdr record))
           ((< index 0) (lookup-aux (left-branch tree)))
           (else 
            (lookup-aux (right-branch tree)))))))
  (lookup-aux (cdr table)))