#lang scribble/doc
@(require scribble/manual
          scribble/eval
          "../scribble.ss"
          "eval.ss")
@(require (for-label scheme (this-package-in scheme)))

@title[#:style 'quiet #:tag "dict"]{Dictionaries}

@defmodule/this-package[dict]

This module provides tools for manipulating dictionary values.

@section{Dictionary Lookup}

@defproc[(dict-ref! [d (and/c dict? dict-mutable?)]
                    [k any/c]
                    [v (or/c (-> any/c) any/c)])
         any/c]{

Looks up key @scheme[k] in dictionary @scheme[d].  If @scheme[d] has no entry
for @scheme[k], updates @scheme[d] to map @scheme[k] to the result of
@scheme[(v)] (if @scheme[v] is a procedure) or @scheme[v] (otherwise), and
returns the new mapping.

@defexamples[
#:eval (evaluator)
(define d (make-hash))
(dict-set! d 1 'one)
(dict-set! d 2 'two)
d
(dict-ref! d 2 'dos)
d
(dict-ref! d 3 'tres)
d
(dict-ref! d 4 gensym)
d
]

}

@defproc[(dict-ref/check [d dict?] [k (lambda (k) (dict-has-key? d k))])
         any/c]{

Looks up key @scheme[k] in dictionary @scheme[d].  Raises a contract error if
@scheme[d] has no entry for @scheme[k].  Equivalent to @scheme[(dict-ref d k)],
except for the specific exception value raised.

@defexamples[
#:eval (evaluator)
(dict-ref/check '([1 . one] [2 . two] [3 . three]) 2)
]

}

@defproc[(dict-ref/identity [d dict?] [k any/c]) any/c]{

Looks up key @scheme[k] in dictionary @scheme[d].  Returns @scheme[k] if
@scheme[d] has no entry for @scheme[k].  Equivalent to
@scheme[(dict-ref d k (lambda () k))].

@defexamples[
#:eval (evaluator)
(dict-ref/identity '([1 . one] [2 . two] [3 . three]) 2)
(dict-ref/identity '([1 . one] [2 . two] [3 . three]) 4)
]

}

@defproc[(dict-ref/default [d dict?] [k any/c] [v any/c]) any/c]{

Looks up key @scheme[k] in dictionary @scheme[d].  Returns @scheme[v] if
@scheme[d] has no entry for @scheme[k].  Equivalent to
@scheme[(dict-ref d k (lambda () v))].

@defexamples[
#:eval (evaluator)
(dict-ref/default '([1 . one] [2 . two] [3 . three]) 2 'other)
(dict-ref/default '([1 . one] [2 . two] [3 . three]) 4 'other)
]

}

@defproc[(dict-ref/failure [d dict?] [k any/c] [f (-> any/c)]) any/c]{

Looks up key @scheme[k] in dictionary @scheme[d].  Returns the result of
applying @scheme[f] (in tail position) if @scheme[d] has no entry for
@scheme[k].  Equivalent to @scheme[(dict-ref d k f)].

@defexamples[
#:eval (evaluator)
(dict-ref/failure '([1 . one] [2 . two] [3 . three]) 2 gensym)
(dict-ref/failure '([1 . one] [2 . two] [3 . three]) 4 gensym)
]

}

@section{Dictionary Accessors}

@defproc[(dict-has-key? [d dict?] [k any/c]) boolean?]{

Reports whether @scheme[d] has an entry for @scheme[k].

@defexamples[
#:eval (evaluator)
(dict-has-key? '([1 . one] [2 . two] [3 . three]) 2)
(dict-has-key? '([1 . one] [2 . two] [3 . three]) 4)
]

}

@defproc[(dict-domain [d dict?]) list?]{

Produces the domain of a dictionary as a list of keys.

@defexamples[
#:eval (evaluator)
(dict-domain '([1 . one] [2 . two] [3 . three]))
]

}

@defproc[(dict-range [d dict?]) list?]{

Produces the range of a dictionary as a list of values.

@defexamples[
#:eval (evaluator)
(dict-range '([1 . one] [2 . two] [3 . three]))
]

}

@section{Dictionary Combinations}

@defproc[(dict-union [d0 (and/c dict? dict-can-functional-set?)]
                     [d dict?] ...
                     [#:combine combine
                                (-> any/c any/c any/c any/c)
                                (lambda _ (error 'dict-union ...))])
         (and/c dict? dict-can-functional-set?)]{

Computes the union of @scheme[d0] with each dictionary @scheme[d] by functional
update, adding each element of each @scheme[d] to @scheme[d0] in turn.  For each
key @scheme[k] and value @scheme[v], if a mapping from @scheme[k] to some value
@scheme[v0] already exists, it is replaced with a mapping from @scheme[k] to
@scheme[(combine k v0 v)].

@defexamples[
#:eval (evaluator)
(dict-union '([1 . one]) '([2 . two]) '([3 . three]))
(dict-union '([1 . (one uno)] [2 . (two dos)])
            '([1 . (ein une)] [2 . (zwei deux)])
            #:combine (lambda (k v1 v2) (append v1 v2)))
]

}

@defproc[(dict-union! [d0 (and/c dict? dict-mutable?)]
                      [d dict?] ...
                      [#:combine combine
                                 (-> any/c any/c any/c any/c)
                                 (lambda _ (error 'dict-union! ...))])
         void?]{

Computes the union of @scheme[d0] with each dictionary @scheme[d] by mutable
update, adding each element of each @scheme[d] to @scheme[d0] in turn.  For each
key @scheme[k] and value @scheme[v], if a mapping from @scheme[k] to some value
@scheme[v0] already exists, it is replaced with a mapping from @scheme[k] to
@scheme[(combine k v0 v)].

@defexamples[
#:eval (evaluator)
(define d (make-hash))
d
(dict-union! d '([1 . (one uno)] [2 . (two dos)]))
d
(dict-union! d
             '([1 . (ein une)] [2 . (zwei deux)])
             #:combine (lambda (k v1 v2) (append v1 v2)))
d
]

}

@section{Dictionary Contract}

@defproc[(dict/c [key/c contract?] [value/c contract?]) contract?]{

Consumes one contract for keys and another for values, and produces a
higher-order contract that wraps dictionaries much the same way that arrow
contracts wrap functions.  Specifically, dictionary operations on the wrapped
dictionary require all keys to satisfy @scheme[key/c] and values to satisfy
@scheme[value/c].

The wrapped dictionary will support the same set of dictionary operations as the
base dictionary, and respond identically to @scheme[dict-mutable?],
@scheme[dict-can-remove-keys?], and @scheme[dict-can-functional-set?].

@emph{Warning:} Bear in mind that these checks are perfomed on every dictionary
operation, and dictionaries wrapped in @scheme[dict/c] multiple times will
perform the checks as many times for each operation.  Especially for immutable
dictionaries (which may be passed through a constructor that involves
@scheme[dict/c] on each update), contract-wrapped dictionaries may be much less
efficient than the original dictionaries.

}