contents index next

16. fsa_array: Non-updatable Arrays (127+32 trees)

This module provides a non-updatable array data-structure. Accessing individual items in the array is very efficient. The arrays are implemented using O'Keefe's N+K trees, with N=127 and K=32.

NB. Array indices start at 0: so 0 refers to the first element of the array.

Here's an overview of the predicates provided:

The N+K tree data-structure is described in The Craft of Prolog, by Richard A. O'Keefe, MIT Press, 1990, chapters 4.5. and 4.6. It is similar to the tries described in section 2 of Tarjan and Yao, Storing a Sparse Table, CACM, 1979, 606-611; also refer to Knuth, The Art of Computing Vol 3.

16.1. List of Predicates

This section lists the predicates defined by this module.

16.1.1. fsa_array_new(-FsaArray[,?Size])

Initializes FsaArray as a new array. In this implementation of arrays the optional second argument is not used.

16.1.2. fsa_array_access(+Index,?Val[,?Default],+FsaArray)

Val is unified with the Index'th entry of FsaArray. This predicate thus subsumes setting and reading of a value in the array. Remember that you can't change values of an array (except by further instantiation). For the 4-ary form, if the Index'th entry was not yet defined, then Val is unified with Default (and not with the Index'th entry).

16.1.3. fsa_array_get(+Index,?Val,+FsaArray)

Val is unified with the Index'th entry of FsaArray. That entry must not be variable. This predicate is different from fsa_array_access/3 in that it can fail.

contents index next