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 instantiated 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.

Documentation on exports

PREDICATEempty_assoc/1

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.

Usage:assoc_to_list(Assoc,L)

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

PREDICATEis_assoc/1

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.

PREDICATEmin_assoc/3

Usage:min_assoc(Assoc,Key,Value)

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

PREDICATEmax_assoc/3

Usage:max_assoc(Assoc,Key,Value)

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

PREDICATEgen_assoc/3

Usage 1:gen_assoc(K,Assoc,V)

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

Usage 2:gen_assoc(K,Assoc,V)

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

PREDICATEget_assoc/3

Usage 1:get_assoc(K,Assoc,V)

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

Usage 2:get_assoc(K,Assoc,V)

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

PREDICATEget_assoc/5

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.

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

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

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.

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.

PREDICATEmap_assoc/2

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),?).

PREDICATEmap_assoc/3

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.

Meta-predicate with arguments: map_assoc(pred(2),?,?).

PREDICATEmap/3

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.

Meta-predicate with arguments: map(?,pred(3),?).

PREDICATEfoldr/4

Usage:foldr(Assoc,Pred,DS,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.

Meta-predicate with arguments: foldr(?,pred(4),?,?).

PREDICATEput_assoc/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.

PREDICATEput_assoc/5

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).

PREDICATEadd_assoc/4

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.

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.

PREDICATEdel_assoc/4

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).

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.

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.

Documentation on imports

This module has the following direct dependencies: