23. map_bbbtree: Balanced Binary Trees: Maps

This module implements maps using bounded balanced binary trees. It is adapted from set_bbbtree, which itself is adapted from the Mercury version. The original of that version is available from http://www.cs.mu.oz.au/research/mercury/. That implementation is based on `Functional Pearls: Efficient sets -a balancing act' by Stephen Adams, J. Functional Programming 3 (4): 553-561, Oct 1993.

A map is a set of key/value pairs, such that each key is associated with at most one value. Keys are required to be ground. The typical operations on maps such as lookup the value of a given key are O(log n) where n is the number of pairs in the map. A potentially more efficient implementation of maps is provided by the fsa_hash, fsa_m_hash and fsa_u_hash modules.

23.1. List of Predicates

This section lists the predicates defined by this module.

23.1.1. map_bbbtree__init(?Bbbtree)

Initializes Bbbtree as an empty map.

23.1.2. map_bbbtree__empty(?Bbbtree)

Bbbtree is an empty map.

23.1.3. map_bbbtree__size(+Bbbtree,?Size)

Size is the number of pairs in map Bbbtree.

23.1.4. map_bbbtree__get(+Key,?Val,+Bbbtree)

Val is the value associated with Key in the map Bbbtree. This predicate fails if Key is not a key of Bbbtree.

23.1.5. map_bbbtree__least(+Bbbtree,?Least,?Val)

Key is the least key in Bbbtree (using the standard order ordering of terms). Its value is Val.

23.1.6. map_bbbtree__largest(+Bbbtree,?Largest,?Val)

Key is the largest key in Bbbtree (using the standard order ordering of terms). Its value is Val.

23.1.7. map_bbbtree__put(+Key,?Val,+Bbbtree0,-Bbbtree)

Bbbtree is the same map as Bbbtree0, except that Key is now associated with Val.

23.1.8. map_bbbtree__put_list(+Bbbtree0,+KeyValList,-Bbbtree

Bbbtree is the same map as Bbbtree0, except that each of the key-value pairs in KeyValList are in Bbbtree.

23.1.9. map_bbbtree__delete(+Bbbtree0,+Key,-Bbbtree)

Bbbtree is the result of removing Key and its associated value from Bbbtree0. Succeeds if Key was not a key of Bbbtree0 (cf map_bbbtree__remove).

23.1.10. map_bbbtree__delete_list(+Keys,+Bbbtree0,-Bbbtree)

Bbbtree is the result of deleting all keys Keys with associated values from Bbbtree0. These keys are not required to exist in Bbbtree0 (cf map_bbbtree__remove_list).

23.1.11. map_bbbtree__remove(+Bbbtree0,+Key,-Bbbtree)

Bbbtree is the result of removing Key and its associated value from Bbbtree0. Fails if Key was not a key of Bbbtree0 (cf map_bbbtree__delete).

23.1.12. map_bbbtree__remove_list(+Keys,+Bbbtree0,-Bbbtree)

Bbbtree is the result of removing all keys Keys with associated values from Bbbtree0. These keys are required to exist in Bbbtree0 (cf map_bbbtree__delete_list).

23.1.13. map_bbbtree__remove_least(+Bbbtree0,?Key,?Val,-Bbbtree)

Key is the least key in Bbbtree0 (using standard ordering of terms). Its value is Value. Bbbtree is the same map as Bbbtree0 except that Key is removed.

23.1.14. map_bbbtree__remove_largest(+Bbbtree0,?Key,?Val,-Bbbtree)

Key is the largest key in Bbbtree0 (using standard ordering of terms). Its value is Value. Bbbtree is the same map as Bbbtree0 except that Key is removed.

23.1.15. map_bbbtree__list_to_map(+KeyValList,-Bbbtree)

Bbbtree is the map for the key-value pairs given as a list in KeyValList.

23.1.16. map_bbbtree__sorted_list_to_map(+SortedKeyValueList,-Bbbtree)

SortedKeyValueList is a sorted list of key value pairs; Bbbtree is the corresponding map.

23.1.17. map_bbbtree__sorted_list_to_map_len(+SortedKeyValueList,-Bbbtree,+Len)

SortedKeyValueList is a sorted list of key value pairs; Bbbtree is the corresponding map. Len is the lenth of the list.

23.1.18. map_bbbtree__to_sorted_list(+Bbbtree,?SortedKeyValList)

SortedKeyValList is a sorted list of the key-value pairs in the map Bbbtree.