In this package, finite mappings ("association lists") are represented by AVL trees, i.e. they are subject to the Adelson-Velskii-Landis balance criterion:
A tree is balanced iff for every node the heights of its two subtrees differ by at most 1.
The empty tree is represented as t. A tree with key K,
value V, and left and right subtrees L and R is
represented as t(K,V,|R|-|L|,L,R), where |T| denotes the
height of T.
The advantage of this representation is that lookup, insertion and deletion all become--in the worst case--O(log n) operations.
The algorithms are from [Wirth 76], section 4.4.6-4.4.8.
To load the package, enter the query
| ?- use_module(library(assoc)).
empty_assoc(?Assoc)
Assoc is an empty AVL tree.
assoc_to_list(+Assoc, ?List)
List is a list of Key-Value pairs in ascending
order with no duplicate Keys specifying the same finite function
as the association tree Assoc. Use this to convert an association
tree to a list.
is_assoc(+Assoc)
Assoc is a (proper) AVL tree. It checks both that the keys are in
ascending order and that Assoc is properly balanced.
min_assoc(+Assoc, ?Key, ?Val)
Key is the smallest key in Assoc and Val is its value.
max_assoc(+Assoc, ?Key, ?Val)
Key is the greatest key in Assoc and Val is its value.
gen_assoc(?Key, +Assoc, ?Value)
Key is associated with Value in the association tree
Assoc. Can be used to enumerate all Values by ascending
Keys.
get_assoc(+Key, +Assoc, ?Value)
Key is identical (==) to one of the keys in the association tree
Assoc, and Value unifies with the associated value.
get_assoc(+Key, +OldAssoc, ?OldValue, ?NewAssoc, ?NewValue)
OldAssoc and NewAssoc are association trees of the same
shape having the same elements except that the value for Key in
OldAssoc is OldValue and the value for Key in
NewAssoc is NewValue.
get_next_assoc(+Key, +Assoc, ?Knext, ?Vnext)
Knext and Vnext is the next key and associated value after
Key in Assoc.
get_prev_assoc(+Key, +Assoc, ?Kprev, ?Vprev)
Kprev and Vprev is the previous key and associated value
after Key in Assoc.
list_to_assoc(+List, ?Assoc)
List is a proper list of Key-Value pairs (in any
order) and Assoc is an association tree specifying the same finite
function from Keys to Values.
ord_list_to_assoc(+List, ?Assoc)
List is a proper list of Key-Value pairs
(keysorted) and Assoc is an association tree specifying the same
finite function from Keys to Values.
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.
map_assoc(:Pred, ?OldAssoc, ?NewAssoc)
put_assoc(+Key, +OldAssoc, +Val, ?NewAssoc)
OldAssoc and NewAssoc define the same finite function,
except that NewAssoc associates Key with Val.
OldAssoc need not have associated Key with any value.
del_assoc(+Key, +OldAssoc, ?Val, ?NewAssoc)
OldAssoc and NewAssoc define the same finite function except
that OldAssoc associates Key with Val and
NewAssoc doesn't associate Key with any value.
del_min_assoc(+OldAssoc, ?Key, ?Val, ?NewAssoc)
OldAssoc and NewAssoc define the same finite function except
that OldAssoc associates Key with Val and
NewAssoc doesn't associate Key with any value and Key
precedes all other keys in OldAssoc.
del_max_assoc(+OldAssoc, ?Key, ?Val, -NewAssoc)
OldAssoc and NewAssoc define the same finite function except that OldAssoc associates Key with Val and NewAssoc doesn't associate Key with any value and Key is preceded by all other keys in OldAssoc.