;; An entry holds a key/value pair ;; for use in Dictionaries. ;; (define-struct entry (key value)) ;; A Dictionary is a structure with two "methods" (fields which are functions): ;; add-fn! and lookup-fn are functions which signatures below. ;; (define-struct dict (add-fn! lookup-fn)) ;; add-fn!: ANY ANY --> ?? ;; SIDE-EFFECT: change the contents. ;; We return (the updated) contents, primarily for debugging purposes. ;; lookup: key --> entry or false ;; Does the key occur inside "contents"? ;; If so, return that entry, else return the sentinel false. ;;;;;;;;;;;;;;;;;; (define new-dict/list (local {(define dict-count 0)} (lambda () (local {;; a local list-of-entries, ;; used only by the dictionary we're creating now: ;; (define contents empty) ;; All contracts as per Dictionary above. (define (add! k val) (begin (set! contents (cons (make-entry k val) contents)) contents)) (define (lookup key) (lookup-helper key contents)) ;; lookup-helper: key, list-of-entries --> entry or false ;; Does the key occur inside "entries"? ;; If so, return that entry, else return the sentinel false. ;; (define (lookup-helper key entries) (cond [(empty? entries) false] [(cons? entries) (cond [(equal? key (entry-key (first entries))) (first entries)] [else (lookup-helper key (rest entries))])])) ; ; NB this function can be of course easily re-written as a list visitor. } (begin (set! dict-count (add1 dict-count)) (make-dict add! lookup)))))) (define (new-dict/vec) (local {; Our local datastore, for numeric keys: a vector. (define initial-size 10) (define notfound-sentinel false) (define data-nums (make-vector initial-size notfound-sentinel)) ; Our local datastore, for (define data-other (new-dict/list)) ;; valid-index?: key --> boolean ;; Is k a valid key for the vector? ;; (define (valid-index? k) (and (number? k) (<= 0 k))) ;; grow-datanums!: natnum --> (void) ;; Make sure that data-nums can hold at least n items. ; To ensure we don't waste too much time always growing in small ; increments, we'll at least double our size. ; (define (grow-datanums! n) (local {(define growth-factor 2) ; How much to grow by, if at all. (define curr-size (vector-length data-nums)) (define new-size (max n (* growth-factor curr-size))) ;; data-xfer: index --> any ;; Return data-nums[i], or (if i out of range for data-nums) ;; return the notfound-sentinel. ;; ;; Used with build-vector, this copies data-nums, ;; padding it out with notfound-sentinel. ;; (define (data-xfer i) (if (< i n) (vector-ref data-nums i) notfound-sentinel))} ; Body of grow-datanums!: (unless (< n curr-size) ; Only grow if needed (set! data-nums (build-vector new-size data-xfer))))) ;; All contracts as per Dictionary above. ;; We proceed by using the vector if possible, ;; else just forward the call to our other robust dict implementation. ;; add!: ANY, ANY --> vector-of-entry or list-of-entry ;; Again, the return value is for debugging mroe than anything. ;; (define (add! k v) (cond [(valid-index? k) (begin (when (>= k (vector-size data-nums)) (grow-datanums! k)) (vector-set! data-nums k v) data-nums)] [else ((dict-add-fn! data-other) k v)])) (define (lookup k) (cond [(valid-index? k) (if (< k (vector-size data-nums)) (vector-ref data-nums k) notfound-sentinel] [else ((dict-lookup-fn data-other) k)])) } (make-dict add! lookup))) ;;;;;; Tests ; Okay, actually both german and french nouns ; *should* be represented by a structure which includes a gender field. (define english->german (new-dict/vec 10)) (boolean=? false ((dict-lookup-fn english->german) 'health)) (boolean=? false ((dict-lookup-fn english->german) 1)) (boolean=? false ((dict-lookup-fn english->german) 11)) ((dict-add-fn! english->german) 'health 'gesundheit) ((dict-add-fn! english->german) 1 'eins) ((dict-add-fn! english->german) 11 'elf) ((dict-lookup-fn english->german) 'health) ((dict-lookup-fn english->german) 1) ((dict-lookup-fn english->german) 11) ((dict-add-fn! english->german) 'science 'wissenschaft) ((dict-lookup-fn english->german) 'health) (define english->french (new-dict/vec 10000)) (boolean=? false ((dict-lookup-fn english->french) 'health)) ((dict-add-fn! english->french) 'health 'sante) ((dict-add-fn! english->french) 'computer 'ordinateur) ((dict-add-fn! english->french) 'weekend 'weekend) ((dict-lookup-fn english->french) 'health) ((dict-add-fn! english->german) 'computer-science 'informatik) ((dict-lookup-fn english->german) 'science) ((dict-lookup-fn english->german) 'health) (boolean=? false ((dict-lookup-fn english->german) 'gymnasium))