Simple, Deterministic Dictionaries
1 Constructors
ddict
ddicteqv
ddicteq
mutable-ddict
mutable-ddicteqv
mutable-ddicteq
make-ddict
make-ddicteqv
make-ddicteq
make-mutable-ddict
make-mutable-ddicteqv
make-mutable-ddicteq
2 Basic Predicates
ddict?
immutable-ddict?
mutable-ddict?
ddict-equal?
ddict-eqv?
ddict-eq?
3 Basic Operations
ddict-set
ddict-set!
ddict-ref
ddict-has-key?
ddict-remove
ddict-remove!
ddict-count
ddict-empty?
4 Additional Operations
ddict-set*
ddict-set*!
ddict-ref!
ddict-update
ddict-update!
ddict-keys-subset?
ddict-clear!
ddict-clear
ddict-copy
ddict-copy-clear
5 Traversal and Iteration Functions
ddict-map
ddict-for-each
ddict->list
ddict-keys
ddict-values
ddict-position?
ddict-iterate-first
ddict-iterate-next
ddict-iterate-key
ddict-iterate-value
in-ddict
in-ddict-keys
in-ddict-values
for/  ddict
for/  ddicteqv
for/  ddicteq
for*/  ddict
for*/  ddicteqv
for*/  ddicteq
for/  mutable-ddict
for/  mutable-ddicteqv
for/  mutable-ddicteq
for*/  mutable-ddict
for*/  mutable-ddicteqv
for*/  mutable-ddicteq
6 Performance and Memory Usage
ddict-compact?
ddict-compact
ddict-compact!
6.12

Simple, Deterministic Dictionaries

Andrew Kent <[email protected]>

 (require data/ddict) package: ddict

This package defines immutable and mutable deterministic dictionaries (or ddicts, for short). A ddict is a dictionary (i.e. it implements the generic interface gen:dict) whose API mimics that of a hash table but which also guarantees LIFO ordering when iterating over the elements of the dictionary.

Examples:
> (define dd (ddict 'A 0 'B 1 'C 2))
> dd

#<ddict: '((C . 2) (B . 1) (A . 0))>

> "Note the ordering is LIFO w.r.t. the keys' insertion order"

"Note the ordering is LIFO w.r.t. the keys' insertion order"

> (ddict->list (ddict-set dd 'Z 25))

'((Z . 25) (C . 2) (B . 1) (A . 0))

> (define mdd (for/mutable-ddict ([idx (in-naturals)]
                                  [name (in-list '(null eins zwei drei))])
                (values idx name)))
> mdd

#<mutable-ddict: '((3 . drei) (2 . zwei) (1 . eins) (0 . null))>

> (ddict-set! mdd 4 'vier)
> (ddict-set! mdd 6 'sechs)
> (ddict-remove! mdd 1)
> (ddict-remove! mdd 3)
> (for ([(key val) (in-ddict mdd)]
        [n (in-naturals)])
    (printf "key ~a: ~a\n" n key)
    (printf "val ~a: ~a\n" n val))

key 0: 6

val 0: sechs

key 1: 4

val 1: vier

key 2: 2

val 2: zwei

key 3: 0

val 3: null

Caveats concerning concurrent modification: A mutable ddict can be manipulated with ddict-set!, ddict-remove!, ddict-ref!, and ddict-update! concurrently by multiple threads; updates to internal state are performed with a check-and-set operation which protects from invalid internal states. However, the following caveats apply:

Caveat concerning mutable keys: If a key in an equal?-based ddict is mutated, then the ddict’s behavior for insertion and lookup operations becomes unpredictable.

1 Constructors

procedure

(ddict key val ... ...)  (and/c immutable-ddict? ddict-equal?)

  key : any/c
  val : any/c

procedure

(ddicteqv key val ... ...)  (and/c immutable-ddict? ddict-eqv?)

  key : any/c
  val : any/c

procedure

(ddicteq key val ... ...)  (and/c immutable-ddict? ddict-eq?)

  key : any/c
  val : any/c

procedure

(mutable-ddict key val ... ...)

  (and/c mutable-ddict? ddict-equal?)
  key : any/c
  val : any/c

procedure

(mutable-ddicteqv key val ... ...)

  (and/c mutable-ddict? ddict-eqv?)
  key : any/c
  val : any/c

procedure

(mutable-ddicteq key val ... ...)

  (and/c mutable-ddict? ddict-eq?)
  key : any/c
  val : any/c
Creates a ddict with each key mapped to the immediately following val. Each key must have a val, so the total number of arguments must be even. Each constructor also specifies how keys are compared (e.g. ddict compares keys with equal?, ddicteqv compares keys with eqv?, etc).

The key to val mappings are added to the table in the order they appear in the argument list, so later mappings can hide earlier ones if the keys are equal.

procedure

(make-ddict [assocs])  (and/c immutable-ddict? ddict-equal?)

  assocs : (listof pair?) = null

procedure

(make-ddicteqv [assocs])  (and/c immutable-ddict? ddict-eqv?)

  assocs : (listof pair?) = null

procedure

(make-ddicteq [assocs])  (and/c immutable-ddict? ddict-eq?)

  assocs : (listof pair?) = null

procedure

(make-mutable-ddict [assocs])

  (and/c mutable-ddict? ddict-equal?)
  assocs : (listof pair?) = null

procedure

(make-mutable-ddicteqv [assocs])

  (and/c mutable-ddict? ddict-eqv?)
  assocs : (listof pair?) = null

procedure

(make-mutable-ddicteq [assocs])

  (and/c mutable-ddict? ddict-eq?)
  assocs : (listof pair?) = null
Creates a ddict that is initialized with the contents of assocs. In each element of assocs, the car is a key, and the cdr is the corresponding value. The mappings are added to the table in the order they appear in the argument list, so later mappings can hide earlier ones if the keys are equivalent w.r.t. the table’s key comparison function.

2 Basic Predicates

procedure

(ddict? v)  boolean?

  v : any/c
Returns #t if v is a ddict (i.e. if it is either a immutable-ddict or a mutable-ddict), #f otherwise.

procedure

(immutable-ddict? v)  boolean?

  v : any/c
Returns #t if v is an immutable-ddict, #f otherwise.

procedure

(mutable-ddict? v)  boolean?

  v : any/c
Returns #t if v is a mutable-ddict, #f otherwise.

procedure

(ddict-equal? dd)  boolean?

  dd : ddict?

procedure

(ddict-eqv? dd)  boolean?

  dd : ddict?

procedure

(ddict-eq? dd)  boolean?

  dd : ddict?
ddict-equal? returns #t if the given ddict’s keys are compared with equal?, #f otherwise.

ddict-eqv? returns #t if the given ddict’s keys are compared with eqv?, #f otherwise.

ddict-eq? returns #t if the given ddict’s keys are compared with eq?, #f otherwise.

3 Basic Operations

procedure

(ddict-set dd key val)  immutable-ddict?

  dd : immutable-ddict?
  key : any/c
  val : any/c
Functionally extends dd by mapping key to val, overwriting any existing mapping for key, and returning the extended ddict.

See also the caveat concerning mutable keys above.

procedure

(ddict-set! dd key val)  void?

  dd : mutable-ddict?
  key : any/c
  val : any/c
Extends dd by mapping key to val, overwriting any existing mapping for key.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

procedure

(ddict-ref dd key [failure-result])  any/c

  dd : ddict?
  key : any/c
  failure-result : (failure-result/c any/c)
   = (λ () (raise (exn:fail:contract ....)))
Returns the value for key in dd. If no value is found for key, then failure-result determines the result:

See also the caveat concerning mutable keys above.

procedure

(ddict-has-key? dd key)  boolean?

  dd : ddict?
  key : any/c
Returns #t if dd contains a value for the given key, #f otherwise.

procedure

(ddict-remove dd key)  immutable-ddict?

  dd : immutable-ddict?
  key : any/c
Functionally removes any existing mapping for key in dd, returning the fresh ddict.

See also the caveat concerning mutable keys above.

procedure

(ddict-remove! dd key)  void?

  dd : mutable-ddict?
  key : any/c
Removes any existing mapping for key in dd.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

procedure

(ddict-count dd)  exact-nonnegative-integer?

  dd : ddict?
Returns the number of keys mapped by dd.

procedure

(ddict-empty? dd)  boolean?

  dd : ddict?
Returns #t just in case (zero? (ddict-count dd)) is #t, #f otherwise.

4 Additional Operations

procedure

(ddict-set* dd key val ... ...)  immutable-ddict?

  dd : immutable-ddict?
  key : any/c
  val : any/c
Functionally extends dd by mapping each key to the following val, overwriting any existing mapping for each key, and returning the extended ddict. Mappings are added to the table in the order they appear in the argument list, so later mappings can hide earlier ones if the keys are equivalent w.r.t. the table’s key comparison function.

procedure

(ddict-set*! dd key val ... ...)  void?

  dd : mutable-ddict?
  key : any/c
  val : any/c
Extends dd by mapping each key to the following val, overwriting any existing mapping for each key, and returning the extended ddict. Mappings are added to the table in the order they appear in the argument list, so later mappings can hide earlier ones if the keys are equivalent w.r.t. the table’s key comparison function.

procedure

(ddict-ref! dd key to-set)  any/c

  dd : mutable-ddict?
  key : any/c
  to-set : any/c
Returns the value for key in dd. If no value is found for key, then to-set determines the result as in ddict-ref (i.e., it is either a thunk that computes a value or a plain value), and this result is stored in dd for the key.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

procedure

(ddict-update dd key updater [failure-result])  any/c

  dd : immutable-ddict?
  key : any/c
  updater : (any/c . -> . any/c)
  failure-result : (failure-result/c any/c)
   = (λ () (raise (exn:fail:contract ....)))
Composes ddict-ref and ddict-set to functionally update an existing mapping in dd, where the optional failure-result argument is used as in ddict-ref when no mapping exists for key already.

See also the caveat concerning mutable keys above.

procedure

(ddict-update! dd key updater [failure-result])  void?

  dd : mutable-ddict?
  key : any/c
  updater : (any/c . -> . any/c)
  failure-result : (failure-result/c any/c)
   = (λ () (raise (exn:fail:contract ....)))
Composes ddict-ref and ddict-set! to update an existing mapping in dd, where the optional failure-result argument is used as in ddict-ref when no mapping exists for key already.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

procedure

(ddict-keys-subset? dd1 dd2)  boolean?

  dd1 : ddict?
  dd2 : ddict?
Returns #t if dd2 contains an entry for each key present in dd1, otherwise returns #f.

procedure

(ddict-clear! dd)  void?

  dd : mutable-ddict?
Removes all mappings from dd in constant time.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

procedure

(ddict-clear dd)  immutable-ddict?

  dd : immutable-ddict?
Functionally removes all mappings from dd in constant time.

procedure

(ddict-copy dd)  mutable-ddict?

  dd : ddict?
Returns a mutable ddict with the same mappings, same key-comparison mode as dd.

procedure

(ddict-copy-clear dd)  ddict?

  dd : ddict?
Produces an empty ddict with the same key-comparison procedure and mutability of dd.

5 Traversal and Iteration Functions

procedure

(ddict-map dd proc)  (listof any/c)

  dd : ddict?
  proc : (any/c any/c . -> . any/c)
Applies the procedure proc to each key and associated value of dd in LIFO order w.r.t. the order they were inserted into dd, accumulating the results into a list.

procedure

(ddict-for-each dd proc)  void?

  dd : ddict?
  proc : (any/c any/c . -> . any/c)
Applies the procedure proc to each key and associated value of dd (for the side-effects of proc) in LIFO order w.r.t. the order they were inserted into dd.

procedure

(ddict->list dd)  (listof (cons/c any/c any/c))

  dd : ddict?
Returns a list of the key–value pairs of dd in in LIFO order w.r.t. the order they were inserted into dd.

procedure

(ddict-keys dd)  (listof any/c)

  dd : ddict?
Returns a list of the keys in dd in LIFO order w.r.t. the order they were inserted into dd.

procedure

(ddict-values dd)  (listof any/c)

  dd : ddict?
Returns a list of the values in dd in LIFO order w.r.t. the order their associated keys were inserted into dd.

procedure

(ddict-position? v)  boolean?

  v : any/c
Returns #t if v is a position used for iterating over a ddict , otherwise returns #f.

procedure

(ddict-iterate-first dd)  ddict-position?

  dd : ddict?

procedure

(ddict-iterate-next dd pos)  ddict-position?

  dd : ddict?
  pos : ddict-position?

procedure

(ddict-iterate-key dd pos)  any/c

  dd : ddict?
  pos : ddict-position?

procedure

(ddict-iterate-value dd pos)  any/c

  dd : ddict?
  pos : ddict-position?
Functions which allow for the manual iteration over a ddict, in LIFO order w.r.t. the insertion order of the keys.

procedure

(in-ddict dd)  sequence?

  dd : ddict?

procedure

(in-ddict-keys dd)  sequence?

  dd : ddict?

procedure

(in-ddict-values dd)  sequence?

  dd : ddict?
in-ddict returns a sequence containing the keys and associated values of dd in LIFO order w.r.t. the order they were inserted into dd.

in-ddict-keys returns a sequence containing the keys of dd in LIFO order w.r.t. the order they were inserted into dd.

in-ddict-values returns a sequence containing the values of dd in LIFO order w.r.t. the order their keys were inserted into dd.

These forms provide for fast, direct iteration when used in conjunction with Racket’s various for loops.

syntax

(for/ddict (for-clause ...) body-or-break ... body)

syntax

(for/ddicteqv (for-clause ...) body-or-break ... body)

syntax

(for/ddicteq (for-clause ...) body-or-break ... body)

syntax

(for*/ddict (for-clause ...) body-or-break ... body)

syntax

(for*/ddicteqv (for-clause ...) body-or-break ... body)

syntax

(for*/ddicteq (for-clause ...) body-or-break ... body)

syntax

(for/mutable-ddict (for-clause ...) body-or-break ... body)

syntax

(for/mutable-ddicteqv (for-clause ...) body-or-break ... body)

syntax

(for/mutable-ddicteq (for-clause ...) body-or-break ... body)

syntax

(for*/mutable-ddict (for-clause ...) body-or-break ... body)

syntax

(for*/mutable-ddicteqv (for-clause ...) body-or-break ... body)

syntax

(for*/mutable-ddicteq (for-clause ...) body-or-break ... body)

Like for/hash, but producing a ddict with the respective mutability and key comparison function.

6 Performance and Memory Usage

Performance. Immutable and mutable ddicts internally use Racket’s immutable hash data structure along with a list of keys in order to provide hash-like performance and a deterministic iteration order. ddict operations obviously have overhead which the native hash operations do not, but as a dictionary increases in size the overhead should become less noticeable (i.e. the overhead is constant for the atomic ddict operations so the asymptotic complexity is unaffected). To determine if this overhead is acceptable you should of course perform your own application-specific benchmarks.

Memory Usage. In order to keep ddict operations such as ddict-remove efficient (i.e. non-linear), we do not immediately remove elements from the internal key list. Instead, a certain amount of “fragmentation” in the key list is tolerated, but once it passes a predetermined threshold (when the number of removed key slots exceeds the number of active keys), the list is then “defragmented”. To prevent this fragmentation from causing unexpected memory leaks, each key in the key list is stored in a weak-box so its presence in the key list after removal does not prevent garbage collection that would otherwise occur.

The hope is that these implementation details are mostly unobservable to ddict users since their costs will be amortized.

If a user is concerned and wants more fine grained control over the presence of internal fragmentation (e.g. if removals are performed early on in computation then never again) the following functions report on the presence of fragmentation and allow a user to remove any:

procedure

(ddict-compact? dd)  boolean?

  dd : ddict?
Returns #t if dd contains no fragmentation in its key list, otherwise returns #f.

procedure

(ddict-compact dd)  immutable-ddict?

  dd : immutable-ddict?
Returns a defragmented version of dd (i.e. the mappings are the same, but any unnecessary space in the internal key list is removed).

procedure

(ddict-compact! dd)  void?

  dd : mutable-ddict?
Defragments the internal key list of dd.