;; An entry holds a key/value pair
;; for use in Dictionaries.
;;
(define-struct entry (key value))

;; have-key? key entry --> boolean
;; Returns whether the key is the same as that of the entry.
(define (have-key? key entry)
  (equal? key (entry-key entry)))


;; 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 dict-Factory
  (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)
                (local [;; helper: list-of-entries --> entry or false
                        ;; Does the key occur inside "entries"?
                        ;; If so, return that entry, else return false.
                        ;;
                        (define (helper entries)
                          (cond [(empty? entries) false]
                                [(cons?  entries)
                                 (cond [(have-key? key (first entries))
                                        (first entries)]
                                       [else (helper (rest entries))])]))]
                  (helper contents)))
              
              ]
        (begin
          (set! dict-count (add1 dict-count))
          (make-dict add! lookup))))))



(define (dict-nat-Factory)
  (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 (dict-Factory))
          
          ;; valid-index?: key --> boolean
          ;; Is k a valid key for the vector?
          ;;
          (define (valid-index? k) (and (integer? 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 (dict-nat-Factory))

(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 (dict-nat-Factory 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))