Did you know ... | Search Documentation: |

Tries |

Tries (also called *digital tree*, *radix tree* or
*prefix tree* maintain a mapping between a variant of a term (see
=@=/2) and a value. They
have been introduced in SWI-Prolog 7.3.21 as part of the implementation
of *tabling*. The current implementation is rather immature. In
particular, the following limitations currently apply:

- Tries are not thread-safe.
- Tries should not be modified while non-deterministic predicates such as trie_gen/3 are running on the trie.
- Terms cannot have
*attributed variables*. - Terms cannot be
*cyclic*. Possibly this will not change because cyclic terms can only be supported after creating a canonical form of the term.

**We give the definition of these predicates for reference and
debugging tabled predicates. Future versions are likely to get a more
stable and safer implementation. The API to tries should not be
considered stable.**

**trie_new**(`-Trie`)- Create a new trie and unify
`Trie`with a handle to the trie. The trie handle is a*blob*. Tries are subject to atom garbage collection. **trie_destroy**(`+Trie`)- Destroy
`Trie`. This removes all nodes from the trie and causes further access to`Trie`to raise an existence_error exception. The handle itself is reclaimed by atom garbage collection. - [semidet]
**is_trie**(`@Trie`) - True when
`Trie`is a trie object. See also current_trie/1. - [nondet]
**current_trie**(`-Trie`) - True if
`Trie`is a currently existing trie. As this enumerates and then filters all known atoms this predicate is slow and should only be used for debugging purposes. See also is_trie/1. **trie_insert**(`+Trie, +Key`)- Insert the term
`Key`into`Trie`. If`Key`is already part of`Trie`the predicates*fails*silently. This is the same as trie_insert/3, but using a fixed reserved`Value`. **trie_insert**(`+Trie, +Key, +Value`)- Insert the term
`Key`into`Trie`and associate it with`Value`.`Value`can be any term. If`Key`-`Value`is already part of`Trie`, the predicates*fails*silently. If`Key`is in`Trie`associated with a different value, a`permission_error`

is raised. **trie_update**(`+Trie, +Key, +Value`)- As trie_insert/3,
but if
`Key`is in`Trie`, its associated value is*updated*. **trie_insert**(`+Trie, +Term, +Value, -Handle`)- As trie_insert/3,
returning a handle to the trie node. This predicate is currently unsafe
as
`Handle`is an integer used to encode a pointer. It was used to implement a pure Prolog version of the`library(tabling)`

library. **trie_delete**(`+Trie, +Key, ?Value`)- Delete
`Key`from`Trie`if the value associated with`Key`unifies with`Value`. **trie_lookup**(`+Trie, +Key, -Value`)- True if the term
`Key`is in`Trie`and associated with`Value`. **trie_term**(`+Handle, -Term`)- True when
`Term`is a copy of the term associated with`Handle`. The result is undefined (including crashes) if`Handle`is not a handle returned by trie_insert_new/3 or the node has been removed afterwards. - [nondet]
**trie_gen**(`+Trie, ?Key`) - True when
`Key`is a member of`Trie`. See also trie_gen_compiled/2. - [nondet]
**trie_gen**(`+Trie, ?Key, -Value`) - True when
`Key`is associated with`Value`in`Trie`. Backtracking retrieves all pairs. Currently scans the entire trie, even if`Key`is partly known. Currently unsafe if`Trie`is modified while the values are being enumerated. See also trie_gen_compiled/3. - [nondet]
**trie_gen_compiled**(`+Trie, ?Key`) - [nondet]
**trie_gen_compiled**(`+Trie, ?Key, -Value`) - Similar to trie_gen/3,
but uses a
*compiled*representation of`Trie`. The compiled representation is created lazily and manipulations of the trie (insert, delete) invalidate the current compiled representation. The compiled representation generates answers faster and, as it runs on a snapshot of the trie, is immune to concurrent modifications of the trie. This predicate is used to generate answers from*answer tries*as used for tabled execution. See section 7. - [nondet]
**trie_property**(`?Trie, ?Property`) - True if
`Trie`exists with`Property`. Intended for debugging and statistical purposes. Retrieving some of these properties visit all nodes of the trie. Defined properties are**value_count**(`-Count`)- Number of key-value pairs in the trie.
**node_count**(`-Count`)- Number of nodes in the trie.
**size**(`-Bytes`)- Required storage space of the trie.
**compiled_size**(`-Bytes`)- Required storage space for the compiled representation as used by trie_gen_compiled/2,3.
**hashed**(`-Count`)- Number of nodes that use a hashed index to its children.
**lookup_count**(`-Count`)- Number of trie_lookup/3
calls (only when compiled with
`O_TRIE_STATS`

). **gen_call_count**(`-Count`)- Number of trie_gen/3
calls (only when compiled with
`O_TRIE_STATS`

). **wait**(`-Count`)- Number of times a thread waited on this trie for another thread to
complete it (shared tabling, only when compiled with
`O_TRIE_STATS`

). **deadlock**(`-Count`)- Number of times this trie was part of a deadlock and its completion was
abandoned (shared tabling, only when compiled with
`O_TRIE_STATS`

).

In addition, a number of additional properties are defined on

*answer tries*.**invalidated**(`-Count`)- Number of times the trie was invalidated (incremental tabling).
**reevaluated**(`-Count`)- Number of times the trie was re-evaluated (incremental tabling).
**idg_affected_count**(`-Count`)- Number of answer tries affected by this one (incremental tabling).
**idg_dependent_count**(`-Count`)- Number of answer tries this one depends on (incremental tabling).
**idg_size**(`-Bytes`)- Number of bytes in the IDG node representation.

Tags are associated to your profile if you are logged in

Tags: