Next: lib-bags, Previous: lib-atts, Up: The Prolog Library [Contents][Index]

`library(avl)`

This library module provides an AVL tree implementation of "association
lists". The binary tree *is* kept balanced, as opposed to
`library(assoc)`

, which provides similar functionality based on
binary trees that are not kept balanced.

Exported predicates:

`empty_avl(`

`?AVL`)-
is true when

`AVL`is an empty AVL tree. `avl_to_list(`

`+AVL`,`-List`)-
assumes that

`AVL`is a proper AVL tree, and is true when`List`is a list of`Key-Value`pairs in ascending order with no duplicate keys specifying the same finite function as`AVL`. Use this to convert an`AVL`to an ordered list. `is_avl(`

`+AVL`)-
is true when

`AVL`is a (proper) AVL tree. It checks both the order condition (that the keys are in ascending order as you go from left to right) and the height balance condition. This code relies on variables (to be precise, the first anonymous variable in is_avl/1) being`@<`

than any non-variable. in strict point of fact you*can*construct an AVL tree with variables as keys, but`is_avl/1`

doesn’t believe it, and it is not good taste to do so. `avl_domain(`

`+AVL`,`-Domain`)-
unifies

`Domain`with the ordered set representation of the domain of the AVL tree (the keys of it). As the keys are in ascending order with no duplicates, we just read them off like`avl_to_list/2`

. `avl_range(`

`+AVL`,`-Range`)-
unifies

`Range`with the ordered set representation of the range of the AVL (the values associated with its keys, not the keys themselves). Note that the cardinality (length) of the domain and the range are seldom equal, except of course for trees representing invertible maps. `avl_min(`

`+AVL`,`-Key`)-
is true when

`Key`is the smallest key in`AVL`. `avl_min(`

`+AVL`,`-Key`,`-Val`)-
is true when

`Key`is the smallest key in`AVL`and`Val`is its value. `avl_max(`

`+AVL`,`-Key`)-
is true when

`Key`is the greatest key in`AVL`. `avl_max(`

`+AVL`,`-Key`,`-Val`)-
is true when

`Key`is the greatest key in`AVL`and`Val`is its value. `avl_height(`

`+AVL`,`-Height`)-
is true when

`Height`is the height of the given AVL tree, that is, the longest path in the tree has`Height`’node’s on it. `avl_size(`

`+AVL`,`-Size`)-
is true when

`Size`is the size of the AVL tree, the number of ’node’s in it. `portray_avl(`

`+AVL`)-
writes an AVL tree to the current output stream in a pretty form so that you can easily see what it is. Note that an AVL tree written out this way can NOT be read back in; for that use

`writeq/1`

. The point of this predicate is to get AVL trees displayed nicely by`print/1`

. `avl_member(`

`?Key`,`+AVL`)-
is true when

`Key`is one of the keys in the given AVL. This predicate should be used to enumerate the keys, not to look for a particular key (use`avl_fetch/2`

or`avl_fetch/3`

for that). The`Keys`are enumerated in ascending order. `avl_member(`

`?Key`,`+AVL`,`?Val`)-
is true when

`Key`is one of the keys in the given AVL and`Val`is the value the AVL associates with that`Key`. This predicate should be used to enumerate the keys and their values, not to look up the value of a known key (use`avl_fetch/3`

) for that. The`Keys`are enumerated in ascending order. `avl_fetch(`

`+Key`,`+AVL`)-
is true when the (given)

`Key`is one of the keys in the (given) AVL. Use this to test whether a known Key occurs in`AVL`and you don’t want to know the value associated with it. `avl_fetch(`

`+Key`,`+AVL`,`-Val`)-
is true when the (given)

`Key`is one of the keys in the (given) AVL and the value associated with it therein is`Val`. It should be used to look up*known*keys, not to enumerate keys (use either`avl_member/2`

or`avl_member/3`

for that). `avl_next(`

`+Key`,`+AVL`,`-Knext`)-
is true when

`Knext`is the next key after`Key`in`AVL`; that is,`Knext`is the smallest key in`AVL`such that`Knext @> Key`. `avl_next(`

`+Key`,`+AVL`,`-Knext`,`-Vnext`)-
is true when

`Knext`is the next key after`Key`in`AVL`and`Vnext`is the value associated with`Knext`in`AVL`. That is,`Knext`is the smallest key in`AVL`such that`Knext @> Key`, and`avl_fetch(`

.`Knext`,`AVL`,`Vnext`) `avl_prev(`

`+Key`,`+AVL`,`-Kprev`)-
is true when

`Kprev`is the key previous to`Key`in`AVL`; that is,`Kprev`is the greatest key in`AVL`such that`Kprev @< Key`. `avl_prev(`

`+Key`,`+AVL`,`-Kprev`,`-Vprev`)-
is true when

`Kprev`is the key previous to Key in`AVL`and`Vprev`is the value associated with`Kprev`in`AVL`. That is,`Kprev`is the greatest key in`AVL`such that`Kprev @< Key`, and`avl_fetch(`

.`Kprev`,`AVL`,`Vprev`) `avl_change(`

`+Key`,`?AVL1`,`?Val1`,`?AVL2`,`?Val2`)-
is true when

`AVL1`and`AVL2`are avl trees of exactly the same shape,`Key`is a key of both of them,`Val1`is the value associated with`Key`in`AVL1`and`Val2`is the value associated with it in`AVL2`, and when`AVL1`and`AVL2`are identical except perhaps for the value they assign to`Key`. Use this to change the value associated with a`Key`which is already present, not to insert a new`Key`(it won’t). `ord_list_to_avl(`

`+List`,`-AVL`)-
is given a list of

`Key-Val`pairs where the`Keys`are already in standard order with no duplicates (this is not checked) and returns an AVL representing the same associations. This takes`O(N)`time, unlike`list_to_avl/2`

which takes`O(N lg N)`. `list_to_avl(`

`+Pairs`,`-AVL`)-
is given a proper list of

`Key-Val`pairs where the`Keys`are in no particular order (but are sufficiently instantiated to be told apart) and returns an AVL representing the same associations. This works by starting with an empty tree and inserting the elements of the list into it. This takes`O(N lg N)`time. Since it is possible to read off a sorted list in`O(N)`time from the result,`O(N lg N)`is as good as can possibly be done. If the same`Key`appears more than once in the input, the last value associated with it will be used. Could be defined as:list_to_avl(Pairs, AVL) :- ( foreach(K-V,Pairs), fromto(empty,AVL0,AVL1,AVL) do avl_store(K, AVL0, V, AVL1) ).

`avl_store(`

`+Key`,`+OldAVL`,`+Val`,`?NewAVL`)-
is true when

`OldAVL`and`NewAVL`define the same finite function except that`NewAVL`associates`Val`with`Key`.`OldAVL`need not have associated any value at all with`Key`. When it didn’t, you can read this as "insert`(Key->Val)`into`OldAVL`giving`NewAVL`". `avl_incr(`

`+Key`,`+OldAVL`,`+Incr`,`+NewAVL`)-
if

`Key`is not present in`OldAVL`, adds`Key->Incr`. if`Key->N`is present in`OldAvl`, changes it to`Key->N+Incr`. `avl_delete(`

`+Key`,`+OldAVL`,`-Val`,`-NewAVL`)-
is true when

`OldAVL`and`NewAVL`define the same finite function except that`OldAVL`associates`Key`with`Val`and`NewAVL`doesn’t associate`Key`with any value. `avl_del_min(`

`+OldAVL`,`-Key`,`-Val`,`-NewAVL`)-
is true when

`OldAVL`and`NewAVL`define the same finite function except that`OldAVL`associates`Key`with`Val`and`NewAVL`doesn’t associate`Key`with any value and`Key`precedes all other keys in`OldAVL`. `avl_del_max(`

`+OldAVL`,`-Key`,`-Val`,`-NewAVL`)-
is true when

`OldAVL`and`NewAVL`define the same finite function except that`OldAVL`associates`Key`with`Val`and`NewAVL`doesn’t associate`Key`with any value and`Key`is preceded by all other keys in`OldAVL`. `avl_map(`

`:Pred`,`+AVL`)-
is true when

`AVL`is an association tree, and for each`Key`, if`Key`is associated with`Value`in`AVL`,`Pred(Value)`is true. `avl_map(`

`:Pred`,`+OldAVL`,`-NewAVL`)-
is true when

`OldAVL`and`NewAVL`are association trees of the same shape, and for each`Key`, if`Key`is associated with`Old`in`OldAVL`and with`New`in`NewAVL`,`Pred(Old,New)`is true.

Send feedback on this subject.