PublicShow sourceassoc.pl -- Binary associations

Assocs are Key-Value associations implemented as a balanced binary tree (AVL tree).

Warning: instantiation of keys

AVL trees depend on the Prolog standard order of terms to organize the keys as a (balanced) binary tree. This implies that any term may be used as a key. The tree may produce wrong results, such as not being able to find a key, if the ordering of keys changes after the key has been inserted into the tree. The user is responsible to ensure that variables used as keys or appearing in a term used as key that may affect ordering are not unified, with the exception of unification against new fresh variables. For this reason, ground terms are safe keys. When using non-ground terms, either make sure the variables appear in places that do not affect the standard order relative to other keys in the tree or make sure to not unify against these variables as long as the tree is being used.

author
- R.A.O'Keefe, L.Damas, V.S.Costa and Jan Wielemaker
See also
- library(pairs), library(rbtrees)
Source empty_assoc(?Assoc) is semidet
Is true if Assoc is the empty association list.
Source assoc_to_list(+Assoc, -Pairs) is det
Translate Assoc to a list Pairs of Key-Value pairs. The keys in Pairs are sorted in ascending order.
Source assoc_to_keys(+Assoc, -Keys) is det
True if Keys is the list of keys in Assoc. The keys are sorted in ascending order.
Source assoc_to_values(+Assoc, -Values) is det
True if Values is the list of values in Assoc. Values are ordered in ascending order of the key to which they were associated. Values may contain duplicates.
Source is_assoc(+Assoc) is semidet
True if Assoc is an association list. This predicate checks that the structure is valid, elements are in order, and tree is balanced to the extent guaranteed by AVL trees. I.e., branches of each subtree differ in depth by at most 1. Does not validate that keys are sufficiently instantiated to ensure the tree remains valid if a key is further instantiated.
Source gen_assoc(?Key, +Assoc, ?Value) is nondet
True if Key-Value is an association in Assoc. Enumerates keys in ascending order on backtracking.
See also
- get_assoc/3.
Source get_assoc(+Key, +Assoc, -Value) is semidet
True if Key-Value is an association in Assoc.
Source get_assoc(+Key, +Assoc0, ?Val0, ?Assoc, ?Val) is semidet
True if Key-Val0 is in Assoc0 and Key-Val is in Assoc.
Source list_to_assoc(+Pairs, -Assoc) is det
Create an association from a list Pairs of Key-Value pairs. List must not contain duplicate keys.
Errors
- domain_error(unique_key_pairs, List) if List contains duplicate keys
Source ord_list_to_assoc(+Pairs, -Assoc) is det
Assoc is created from an ordered list Pairs of Key-Value pairs. The pairs must occur in strictly ascending order of their keys.
Errors
- domain_error(key_ordered_pairs, List) if pairs are not ordered.
Source map_assoc(:Pred, +Assoc) is semidet
True if Pred(Value) is true for all values in Assoc.
Source map_assoc(:Pred, +Assoc0, ?Assoc) is semidet
Map corresponding values. True if Assoc is Assoc0 with Pred applied to all corresponding pairs of of values.
Source max_assoc(+Assoc, -Key, -Value) is semidet
True if Key-Value is in Assoc and Key is the largest key.
Source min_assoc(+Assoc, -Key, -Value) is semidet
True if Key-Value is in assoc and Key is the smallest key.
Source put_assoc(+Key, +Assoc0, +Value, -Assoc) is det
Assoc is Assoc0, except that Key is associated with Value. This can be used to insert and change associations.
Source del_min_assoc(+Assoc0, ?Key, ?Val, -Assoc) is semidet
True if Key-Value is in Assoc0 and Key is the smallest key. Assoc is Assoc0 with Key-Value removed. Warning: This will succeed with no bindings for Key or Val if Assoc0 is empty.
Source del_max_assoc(+Assoc0, ?Key, ?Val, -Assoc) is semidet
True if Key-Value is in Assoc0 and Key is the greatest key. Assoc is Assoc0 with Key-Value removed. Warning: This will succeed with no bindings for Key or Val if Assoc0 is empty.
Source del_assoc(+Key, +Assoc0, ?Value, -Assoc) is semidet
True if Key-Value is in Assoc0. Assoc is Assoc0 with Key-Value removed.