library(assoc)
This library provides a binary tree implementation of "association
lists". The binary tree is not kept balanced, as opposed to
library(avl)
, which provides similar functionality based on balanced
AVL trees.
Exported predicates:
empty_assoc(
?Assoc)
assoc_to_list(
+Assoc,
-List)
gen_assoc(
?Key,
+Assoc,
?Value)
get_assoc/3
. Note that this predicate is not
determinate. If you want to maintain a finite bijection, it
is better to maintain two assocs than to drive one both ways.
The Keys and Values are enumerated in ascending order of Keys.
get_assoc(
+Key,
+Assoc,
-Value)
==
) one of the keys in Assoc, and Value
unifies with the associated value. Note that since we use the
term ordering to identify keys, we obtain logarithmic access,
at the price that it is not enough for the Key to unify with a
key in Assoc, it must be identical. This predicate is determinate.
The argument order follows the the pattern established by the
built-in predicate arg/3
(called the arg/3
, or selector, rule):
predicate(indices, structure, element).
The analogy with arg(
N,
Term,
Element)
is that
Key:N :: Assoc:Term :: Value:Element.
get_next_assoc(
+Key,
+Assoc,
-Knext,
-Vnext)
get_next_assoc/4
naturally fails. It assumes that Assoc is
a proper assoc. Key should normally be ground. Note that there is
no need for Key to be in the association at all. You can use this
predicate in combination with min_assoc/3
to traverse an association
tree; but if there are N pairs in the tree the cost will be O(N lg N).
If you want to traverse all the pairs, calling assoc_to_list/2
and
walking down the list will take O(N) time.
get_prev_assoc(
+Key,
+Assoc,
-Kprev,
-Vprev)
max_assoc/3
to traverse an assoc.
See the notes on get_next_assoc/4
.
is_assoc(
+Thing)
is_assoc/1
) being @<
than any non-variable.
list_to_assoc(
+List,
-Assoc)
list_to_assoc/2
doesn't check for
duplicate keys, but the association tree which gets built won't work.
ord_list_to_assoc(
+List,
-Assoc)
list_to_assoc/2
which trusts you to have sorted
the list already. If you pair up an ordered set with suitable
values, calling this instead will save the sort.
map_assoc(
:Pred,
+Assoc)
map_assoc(
:Pred,
?OldAssoc,
?NewAssoc)
map_assoc/3
may not terminate), and for each Key,
if Key is associated with Old in OldAssoc and with New in
NewAssoc, the proposition Pred(Old,New) is true. Normally we
assume that Pred is a function from Old to New, but the code
does not require that. There should be a version of this
predicate which passes Key to Pred as well as Old and New,
but there isn't. If you'd have a use for it, please tell us.
max_assoc(
+Assoc,
-Key,
-Val)
min_assoc(
+Assoc,
-Key,
-Val)
portray_assoc(
+Assoc)
writeq/1
. The point of this predicate is
to get association trees displayed nicely by print/1
.
put_assoc(
+Key,
+OldAssoc,
+Val,
-NewAssoc)