# Association between key and value

**Author(s):**Pablo Chico, Manuel Carro.

This library implements a table. It takes its name from the classical "association lists". It allows storing a set of values and a key for each value, such that the values can later be accessed through these keys. These keys could not be ground terms, but they could not be instanciated later (so, this implementation unify with '==' instead of '='). The implementation uses a dynamically changing data structure for efficiency. When there are few elements the data structure used is a list of pairs. When the number of elements stored goes beyond some number, an AVL tree is used. There is a certain level of hysteresis so that no repeated data structure conversions occur when the number of elements is close to the threshold.

## Usage and interface

**Library usage:**`:- use_module(library(assoc)).`**Exports:***Predicates:*`empty_assoc/1`,`assoc_to_list/2`,`is_assoc/1`,`min_assoc/3`,`max_assoc/3`,`gen_assoc/3`,`get_assoc/3`,`get_assoc/5`,`get_next_assoc/4`,`get_prev_assoc/4`,`list_to_assoc/2`,`ord_list_to_assoc/2`,`map_assoc/2`,`map_assoc/3`,`map/3`,`foldl/4`,`put_assoc/4`,`put_assoc/5`,`add_assoc/4`,`update_assoc/5`,`del_assoc/4`,`del_min_assoc/4`,`del_max_assoc/4`.

**Imports:***System library modules:*`hiordlib`,`lists`.*Packages:*`prelude`,`nonpure`,`assertions`,`basicmodes`,`hiord`,`regtypes`.

## Documentation on exports

**Usage 1:**`empty_assoc(Assoc)`

True if Assoc is an empty `assoc_table`.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

**Usage 2:**`empty_assoc(Assoc)`

Assoc is an empty `assoc_table`.

*The following properties should hold at call time:*

(term_typing:var/1)Assoc is a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

**Usage:**`assoc_to_list(Assoc,L)`

Transforms Assoc into L where each pair of L was a association in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)L is a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:ord_pairs/1)L is a ordered list of elements of the form`key`-`value`.

**Usage:**`is_assoc(Assoc)`

True if Assoc is an `assoc_table`.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

**Usage:**`min_assoc(Assoc,Key,Value)`

Key and Value are `key` and `value` of the element with the smallest `key` in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)Key is a free variable.

(term_typing:var/1)Value is a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:value/1)Value is a valid value in a`assoc_table`.

**Usage:**`max_assoc(Assoc,Key,Value)`

Key and Value are the `key` and `value` of the element with the largest `key` in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)Key is a free variable.

(term_typing:var/1)Value is a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:key/1)Key is a valid key in a`assoc_table`.

(assoc:value/1)Value is a valid value in a`assoc_table`.

**Usage 1:**`gen_assoc(K,Assoc,V)`

Enumerate matching elements of Assoc in ascending order of their keys via backtracking.

*The following properties should hold at call time:*

(term_typing:var/1)K is a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)V is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

**Usage 2:**`gen_assoc(K,Assoc,V)`

Enumerate matching elements of Assoc in ascending order of their keys via backtracking whose value is V.

*The following properties should hold at call time:*

(term_typing:var/1)K is a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:nonvar/1)V is currently a term which is not a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

**Usage 1:**`get_assoc(K,Assoc,V)`

True if V is the value associated to the key K in the assoc_table Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:nonvar/1)V is currently a term which is not a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

**Usage 2:**`get_assoc(K,Assoc,V)`

V is the value associated to the key K in the assoc_table Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)V is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

**Usage:**`get_assoc(K,Assoc,Old,NewAssoc,New)`

NewAssoc is an `assoc_table` identical to Assoc except that the value associated with Key is New instead of Old.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)Old is a free variable.

(term_typing:var/1)NewAssoc is a free variable.

(term_typing:nonvar/1)New is currently a term which is not a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:value/1)Old is a valid value in a`assoc_table`.

(assoc:assoc_table/1)NewAssoc is a associations beetwen keys and values.

(assoc:value/1)New is a valid value in a`assoc_table`.

**Usage:**`get_next_assoc(K,Assoc,NextK,NextV)`

NextK and NextV are the next `key` and associated `value` after K in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)NextK is a free variable.

(term_typing:var/1)NextV is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:key/1)NextK is a valid key in a`assoc_table`.

(assoc:value/1)NextV is a valid value in a`assoc_table`.

**Usage:**`get_prev_assoc(K,Assoc,PrevK,PrevV)`

PrevK and PrevV are the previous `key` and associated `value` after K in Assoc.

*The following properties should hold at call time:*

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:key/1)PrevK is a valid key in a`assoc_table`.

(assoc:value/1)PrevV is a valid value in a`assoc_table`.

**Usage:**`list_to_assoc(L,Assoc)`

Transforms L into Assoc where each pair of L will be a association in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)L is currently a term which is not a free variable.

(term_typing:var/1)Assoc is a free variable.

(assoc:pairs/1)L is a list of elements of the form`key`-`value`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

**Usage:**`ord_list_to_assoc(L,Assoc)`

Transforms L, a list of pairs (using the functor `-/2`) sorted by its first element, into the table Assoc where each pair of L will become a association in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)L is currently a term which is not a free variable.

(term_typing:var/1)Assoc is a free variable.

(assoc:ord_pairs/1)L is a ordered list of elements of the form`key`-`value`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

**Usage:**`map_assoc(Pred,Assoc)`

Assoc is an association tree, and for each Key, if Key is associated with Value in Assoc, Pred(Value) is true.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Pred is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

*Meta-predicate*with arguments:

`map_assoc((pred 1),?)`.

**Usage:**`map_assoc(Pred,Assoc,NewAssoc)`

Assoc and NewAssoc are association trees of the same shape, and for each Key, if Key is associated with Old in Assoc and with new in NewAssoc, Pred(Old,New) is true.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Pred is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)NewAssoc is a free variable.

*Meta-predicate*with arguments:

`map_assoc((pred 2),?,?)`.

**Usage:**`map(Assoc1,Pred,Assoc2)`

Applies Pred with arity 3 to each value of the assoc_table Assoc1 obtaining the new assoc_table Assoc2 in which only the values can have changed.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc1 is currently a term which is not a free variable.

(term_typing:nonvar/1)Pred is currently a term which is not a free variable.

(term_typing:var/1)Assoc2 is a free variable.

*Meta-predicate*with arguments:

`map(?,(pred 3),?)`.

**Usage:**`foldl(Assoc,DS,Pred,NDS)`

Applies Pred with arity 4 to each value of the assoc_table Assoc. If Pred is satisfied, it updates the data-structure DS. Otherwise it fails.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:nonvar/1)DS is currently a term which is not a free variable.

(term_typing:nonvar/1)Pred is currently a term which is not a free variable.

(term_typing:var/1)NDS is a free variable.

*Meta-predicate*with arguments:

`foldl(?,?,(pred 4),?)`.

**Usage:**`put_assoc(K,Assoc,V,NewAssoc)`

The value V is inserted in Assoc associated to the key K and the result is NewAssoc. This can be used to insert and change associations.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:nonvar/1)V is currently a term which is not a free variable.

(term_typing:var/1)NewAssoc is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)NewAssoc is a associations beetwen keys and values.

**Usage:**`put_assoc(K,Assoc1,V,Assoc2,Member)`

The value V is inserted in Assoc1 associated to the key K and the result is Assoc2. If the key K doesn't belong to the Assoc1 then Member is unified with no. Otherwise, Assoc2 is the result of substituting the association K-OldValue by K-V and Member is unified with yes(OldValue).

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc1 is currently a term which is not a free variable.

(term_typing:nonvar/1)V is currently a term which is not a free variable.

(term_typing:var/1)Assoc2 is a free variable.

(term_typing:var/1)Member is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc1 is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)Assoc2 is a associations beetwen keys and values.

(assoc:is_member/1)Member is no or yes(value).

**Usage:**`add_assoc(K,Assoc1,V,Assoc2)`

This is similar to `put_value/5` but Key must not appear in Assoc1 (Member in put_value/5 is known to be no). An error is thrown otherwise.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc1 is currently a term which is not a free variable.

(term_typing:nonvar/1)V is currently a term which is not a free variable.

(term_typing:var/1)Assoc2 is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc1 is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)Assoc2 is a associations beetwen keys and values.

**Usage:**`update_assoc(K,Assoc1,V,Assoc2,OldVar)`

This is similar to `put_assoc/5` but Key must not appear in Assoc1 (Member in put_value/5 is known to be no). An error is thrown otherwise.

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc1 is currently a term which is not a free variable.

(term_typing:nonvar/1)V is currently a term which is not a free variable.

(term_typing:var/1)Assoc2 is a free variable.

(term_typing:var/1)OldVar is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc1 is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)Assoc2 is a associations beetwen keys and values.

(assoc:value/1)OldVar is a valid value in a`assoc_table`.

**Usage:**`del_assoc(K,Assoc1,V,Assoc2)`

Delete in Assoc1 the key K to give Assoc2. If the key K does not belong to the Assoc1 then Member is unified with no and Assoc1 and Assoc2 are unified. Otherwise Assoc2 is the result of deleting the key K and its associated Value, and Member is unified with yes(Value).

*The following properties should hold at call time:*

(term_typing:nonvar/1)K is currently a term which is not a free variable.

(term_typing:nonvar/1)Assoc1 is currently a term which is not a free variable.

(term_typing:var/1)V is a free variable.

(term_typing:var/1)Assoc2 is a free variable.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:assoc_table/1)Assoc1 is a associations beetwen keys and values.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)Assoc2 is a associations beetwen keys and values.

**Usage:**`del_min_assoc(Assoc,K,V,NewAssoc)`

Assoc and NewAssoc define the same finite function except that Assoc associates K with V and NewAssoc doesn't associate K with any value and K precedes all other keys in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)K is a free variable.

(term_typing:var/1)V is a free variable.

(term_typing:var/1)NewAssoc is a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)NewAssoc is a associations beetwen keys and values.

**Usage:**`del_max_assoc(Assoc,K,V,NewAssoc)`

Assoc and NewAssoc define the same finite function except that Assoc associates K with V and NewAssoc doesn't associate K with any value and K is preceded by all other keys in Assoc.

*The following properties should hold at call time:*

(term_typing:nonvar/1)Assoc is currently a term which is not a free variable.

(term_typing:var/1)K is a free variable.

(term_typing:var/1)V is a free variable.

(term_typing:var/1)NewAssoc is a free variable.

(assoc:assoc_table/1)Assoc is a associations beetwen keys and values.

(assoc:key/1)K is a valid key in a`assoc_table`.

(assoc:value/1)V is a valid value in a`assoc_table`.

(assoc:assoc_table/1)NewAssoc is a associations beetwen keys and values.