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

PREDICATE

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

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.

PREDICATE

assoc_to_list/2:

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.

PREDICATE

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

PREDICATE

min_assoc/3:

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.

PREDICATE

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

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.

PREDICATE

gen_assoc/3:

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.

PREDICATE

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

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.

PREDICATE

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

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.

PREDICATE

get_next_assoc/4:

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.

PREDICATE

get_prev_assoc/4:

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.

PREDICATE

list_to_assoc/2:

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.

PREDICATE

ord_list_to_assoc/2:

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.

PREDICATE

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

PREDICATE

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

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

PREDICATE

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

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

PREDICATE

foldl/4:

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

PREDICATE

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

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.

PREDICATE

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

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

PREDICATE

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

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.

PREDICATE

update_assoc/5:

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.

PREDICATE

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

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.

PREDICATE

del_min_assoc/4:

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.

PREDICATE

del_max_assoc/4:

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.

Association between key and value

Usage and interface

Documentation on exports

Module Sections

Global Links

Indices