Did you know ... Search Documentation:
nb_set.pl -- Non-backtrackable sets
PublicShow source

This library provides a non-backtrackabe set of terms that are variants of each other. It is primarily intended to implement distinct/1 from library(solution_sequences). The set is implemented as a hash table that is built using non-backtrackable primitives, notably nb_setarg/3.

The original version of this library used binary trees which provides immediate ordering. As the trees were not balanced, performance could get really poor. The complexity of balancing trees using non-backtrackable primitives is too high.

author
- Jan Wielemaker
Source empty_nb_set(-Set)
Create an empty non-backtrackable set.
Source add_nb_set(+Key, !Set) is det
Source add_nb_set(+Key, !Set, ?New) is semidet
add_nb_set(+Key, !Set, ?New) is semidet
Insert Key into the set. If a variant (see =@=/2) of Key is already in the set, the set is unchanged and New is unified with false. Otherwise, New is unified with true and a copy of Key is added to the set.
To be done
- Computing the hash for cyclic terms is performed with the help of term_factorized/3, which performs rather poorly.
Source hash_key(+Term, +BucketCount, -Key) is det[private]
Compute a hash for Term. Note that variant_hash/2 currently does not handle cyclic terms, so use term_factorized/3 to get rid of the cycles. This means that this library is rather slow when cyclic terms are involved.
Source nb_set_to_list(+Set, -List)
Get the elements of a an nb_set. List is sorted to the standard order of terms.
Source gen_nb_set(+Set, -Key)
Enumerate the members of a set in the standard order of terms.
Source size_nb_set(+Set, -Size)
Unify Size with the number of elements in the set

Re-exported predicates

The following predicates are exported from this file while their implementation is defined in imported modules or non-module files loaded by this module.

Source add_nb_set(+Key, !Set) is det
Source add_nb_set(+Key, !Set, ?New) is semidet
add_nb_set(+Key, !Set, ?New) is semidet
Insert Key into the set. If a variant (see =@=/2) of Key is already in the set, the set is unchanged and New is unified with false. Otherwise, New is unified with true and a copy of Key is added to the set.
To be done
- Computing the hash for cyclic terms is performed with the help of term_factorized/3, which performs rather poorly.