;; 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 max-key) (local {; Our local datastore, for numeric keys: a vector. (define data-smallnums (make-vector max-key false)) ; Our local datastore, for (define data-other (new-dict/list)) ;; small-num?: key --> boolean ;; Is k a valid key for the vector? ;; (define (small-num? k) (and (number? k) (<= 0 k) (< k max-key))) ;; 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 [(small-num? k) (begin (vector-set! data-smallnums k v) data-smallnums)] [else ((dict-add-fn! data-other) k v)])) (define (lookup k) (cond [(small-num? k) (vector-ref data-smallnums k)] ; Note how we initialized the vector to contain false -- our 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))