\libdoc{nb_set}{Non-backtrackable set}

The library \pllib{nb_set} defines \jargon{non-backtrackable sets},
implemented as binary trees. The sets are represented as compound terms
and manipulated using nb_setarg/3. Non-backtrackable manipulation of
data structures is not supported by a large number of Prolog
implementations, but it has several advantages over using the
database. It produces less garbage, is thread-safe, reentrant and deals
with exceptions without leaking data.

Similar to the \pllib{assoc} library, keys can be any Prolog term, but
it is not allowed to instantiate or modify a term.

One of the ways to use this library is to generate unique values on
backtracking \emph{without} generating \emph{all} solutions first,
for example to act as a filter between a generator producing many
duplicates and an expensive test routine, as outlined below:

\begin{code}
generate_and_test(Solution) :-
	empty_nb_set(Set),
	generate(Solution),
	add_nb_set(Solution, Set, true),
	test(Solution).
\end{code}


\begin{description}
    \predicate{empty_nb_set}{1}{?Set}
True if \arg{Set} is a non-backtrackable empty set.

    \predicate{add_nb_set}{2}{+Key, !Set}
Add \arg{Key} to \arg{Set}. If \arg{Key} is already a member of
\arg{Set}, add_nb_set/3 succeeds without modifying \arg{Set}.

    \predicate{add_nb_set}{3}{+Key, !Set, ?New}
If \arg{Key} is not in \arg{Set} and \arg{New} is unified to
\const{true}, \arg{Key} is added to \arg{Set}.  If \arg{Key}
is in \arg{Set}, \arg{New} is unified to \const{false}.  It can
be used for many purposes:

\begin{center}
\begin{tabular}{ll}
\tt add_nb_set(+, +, false)	& Test membership \\
\tt add_nb_set(+, +, true)	& Succeed only if new member \\
\tt add_nb_set(+, +, Var)	& Succeed, binding \arg{Var} \\
\end{tabular}
\end{center}

    \predicate{gen_nb_set}{2}{+Set, -Key}
Generate all members of \arg{Set} on backtracking in the standard order
of terms.  To test membership, use add_nb_set/3.

    \predicate{size_nb_set}{2}{+Set, -Size}
Unify \arg{Size} with the number of elements in \arg{Set}.

    \predicate{nb_set_to_list}{2}{+Set, -List}
Unify \arg{List} with a list of all elements in \arg{Set} in the standard
order of terms (i.e., an \jargon{ordered list}).
\end{description}