Node:Assoc, Next:Attributes, Previous:Arrays, Up:Top

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`)`OldAssoc`and`NewAssoc`are association trees of the same shape, and for each`Key`, if`Key`is associated with`Old`in`OldAssoc`and with`New`in`NewAssoc`,`Pred(Old,New)`is true.`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`.