;; DICTIONARY

;; this is code for the running dictionary, which is implemented as an
;; association list. it contains code to treat the dictionary as a
;; shadowing store, or a functional store (set).


(module dict mzscheme
  (require (lib "match.ss")
           "list.ss")

  (provide (all-defined))

  ;; this one's trivial
  (define (dict-find  dict tag)
    (assoc-ref tag dict))


  ;; for put, we can enhance performance if we know wether the element
  ;; is already there or not. if this information is not known, there
  ;; are 2 options. either you search first, and dict-shadow when not
  ;; found. or you provide a thunk to dict-mute that calls
  ;; dict-shadow. the latter is less efficient, because it will discared
  ;; a consed list, the former will just search.


  ;; like put, but assume there are no occurances. if there are
  ;; occurances, they will be shadowed.

  (define (dict-shadow dict tag value)
    (cons (cons tag value) dict))



  ;; the most general update function.

  ;; - respects order
  ;; - reuses tails
  ;; - handler for matching cons cell (kons)
  ;; - handler for end of list (not-found)

  (define (dict-update kons tail
                       dict tag value)

    (let ((tag? (lambda (x) (eq? tag x))))
      (let mute ((d dict))
        (match d
               ;; done
               (() (tail))

               ;; element is on top -> replace
               ((((= tag? #t) . v) . r)
                (kons (cons tag value) r))

               ;; else recurse
               ((item . r)
                (cons item (mute r)))))))


  ;; now there are a lot of different update patterns.

  ;; REMOVE then SHADOW: this will put the item in the front, meaning
  ;; that subsequent operations will be faster, and reuse more tail.

  ;; REPLACE: this preserves order, but is only efficient for items near
  ;; the front, since it rebuilds list structure.

  ;; SEARCH then REPLACE/SHADOW: will preserve order, and put new items
  ;; in front.

  ;; REPLACE/QUEUE: will preserve order, and put new items in back.


  ;; i need only REMOVE+SHADOW and SHADOW. the former for updating
  ;; counters, and the second for accumulating addresses.

  (define (dict-remove dict tag)
    (dict-update (lambda (kar kdr) kdr) ;; discard it
                 (lambda () (raise `(tag-not-found ,tag))) ;; need it
                 dict tag #f))
  
  (define (dict-mute dict tag value)
    (dict-shadow
     (dict-remove dict tag)
     tag value))




  (define (dict-mute-recursive dict url value)
    (dict-mute dict (car url)
               (if (null? (cdr url))
                   value                   ;; found leaf node
                   (dict-mute-recursive    ;; recurse down dictionary chain
                    (dict-find dict (car url))
                    (cdr url) value))))

  (define (dict-find-recursive dict url)
    (let ((thing
           (dict-find dict (car url))))
      (and thing
           (if (null? (cdr url))
               thing            ;; found leaf node
               (dict-find-recursive thing
                                    (cdr url))))))


  ;; (dict-remove '((a . 1) (b . 2)) 'b)
  ;; (dict-mute '((a . 1) (b . 2) (c . 3)) 'c 123)



  ;; remove shadowed references.
  (define (dict-clean-reverse dict)
    (fold
     (lambda (record clean)
       (if (assoc (car record) clean)
           clean
           (cons record clean)))
     '() dict))

  ;; preserves order. linear reverse operator is ok, since the list
  ;; returned from dict-clean-reverse is fresh.
  (define (dict-clean dict)
    (reverse! (dict-clean-reverse dict))) 



)