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.

Documentation on exports

PREDICATE

Usage 1: empty_assoc(Assoc)

  • Description: 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)

  • Description: 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

Usage: assoc_to_list(Assoc,L)

  • Description: 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

Usage: is_assoc(Assoc)

  • Description: 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

Usage: min_assoc(Assoc,Key,Value)

  • Description: 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

Usage: max_assoc(Assoc,Key,Value)

  • Description: 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

Usage 1: gen_assoc(K,Assoc,V)

  • Description: 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)

  • Description: 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

Usage 1: get_assoc(K,Assoc,V)

  • Description: 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)

  • Description: 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

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

  • Description: 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

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

  • Description: 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

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

  • Description: 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

Usage: list_to_assoc(L,Assoc)

  • Description: 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

Usage: ord_list_to_assoc(L,Assoc)

  • Description: 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

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

Usage: map_assoc(Pred,Assoc)

  • Description: 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.

PREDICATE

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

Usage: map_assoc(Pred,Assoc,NewAssoc)

  • Description: 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.

PREDICATE

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

Usage: map(Assoc1,Pred,Assoc2)

  • Description: 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.

PREDICATE

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

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

  • Description: 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.

PREDICATE

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

  • Description: 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

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

  • Description: 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

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

  • Description: 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

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

  • Description: 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

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

  • Description: 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

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

  • Description: 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

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

  • Description: 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.