/usr/lib/swi-prolog/doc/Manual/nbset.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">

<HTML>
<HEAD>
<TITLE>SWI-Prolog 5.10.2 Reference Manual: Section A.13</TITLE><LINK REL=home HREF="index.html">
<LINK REL=contents HREF="Contents.html">
<LINK REL=index HREF="DocIndex.html">
<LINK REL=summary HREF="summary.html">
<LINK REL=previous HREF="lists.html">
<LINK REL=next HREF="www_browser.html">
<STYLE type="text/css">
/* Style sheet for SWI-Prolog latex2html
*/

dd.defbody
{ margin-bottom: 1em;
}

dt.pubdef
{ background-color: #c5e1ff;
}

.bib dd
{ margin-bottom: 1em;
}

.bib dt
{ float: left;
margin-right: 1.3ex;
}

pre.code
{ margin-left: 1.5em;
margin-right: 1.5em;
border: 1px dotted;
padding-top: 5px;
padding-left: 5px;
padding-bottom: 5px;
background-color: #f8f8f8;
}

div.navigate
{ text-align: center;
background-color: #f0f0f0;
border: 1px dotted;
padding: 5px;
}

div.title
{ text-align: center;
padding-bottom: 1em;
font-size: 200%;
font-weight: bold;
}

div.author
{ text-align: center;
font-style: italic;
}

div.abstract
{ margin-top: 2em;
background-color: #f0f0f0;
border: 1px dotted;
padding: 5px;
margin-left: 10%; margin-right:10%;
}

div.abstract-title
{ text-align: center;
padding: 5px;
font-size: 120%;
font-weight: bold;
}

div.toc-h1
{ font-size: 200%;
font-weight: bold;
}

div.toc-h2
{ font-size: 120%;
font-weight: bold;
margin-left: 2em;
}

div.toc-h3
{ font-size: 100%;
font-weight: bold;
margin-left: 4em;
}

div.toc-h4
{ font-size: 100%;
margin-left: 6em;
}

span.sec-nr
{ 
}

span.sec-title
{ 
}

span.pred-ext
{ font-weight: bold;
}

span.pred-tag
{ float: right;
font-size: 80%;
font-style: italic;
color: #202020;
}

/* Footnotes */

sup.fn { color: blue; text-decoration: underline; }
span.fn-text { display: none; }
sup.fn span {display: none;}
sup:hover span 
{ display: block !important;
position: absolute; top: auto; left: auto; width: 80%;
color: #000; background: white;
border: 2px solid;
padding: 5px; margin: 10px; z-index: 100;
font-size: smaller;
}
</STYLE>
</HEAD>
<BODY BGCOLOR="white">
<DIV class="navigate"><A class="nav" href="index.html"><IMG SRC="home.gif" BORDER=0 ALT="Home"></A>
<A class="nav" href="Contents.html"><IMG SRC="index.gif" BORDER=0 ALT="Contents"></A>
<A class="nav" href="DocIndex.html"><IMG SRC="yellow_pages.gif" BORDER=0 ALT="Index"></A>
<A class="nav" href="summary.html"><IMG SRC="info.gif" BORDER=0 ALT="Summary"></A>
<A class="nav" href="lists.html"><IMG SRC="prev.gif" BORDER=0 ALT="Previous"></A>
<A class="nav" href="www_browser.html"><IMG SRC="next.gif" BORDER=0 ALT="Next"></A>
</DIV>

<H2><A NAME="sec:A.13"><SPAN class="sec-nr">A.13</SPAN> <SPAN class="sec-title">library( 
nbset ): Non-backtrackable set</SPAN></A></H2>

<A NAME="nbset"></A>

<P>The library <CODE>library(nb_set)</CODE> defines <EM>non-backtrackable 
sets</EM>, implemented as binary trees. The sets are represented as 
compound terms and manipulated using <A NAME="idx:nbsetarg3:1578"></A><A class="pred" href="manipterm.html#nb_setarg/3">nb_setarg/3</A>. 
Non-backtrackable manipulation of datastructures is not supported by a 
large number of Prolog implementation, but it it has several advantages 
over using the database. It produces less garbage, is thread-safe, 
reentrant and deals with exceptions without leaking data.

<P>Similar to the <CODE>library(assoc)</CODE> library keys can be any 
Prolog term, but it is not allowed to instantiate or modify a term.

<P>One of the ways to use this library is to generate unique values on 
backtracking <EM>without</EM> generating <EM>all</EM> solutions first, 
for example to act as a filter between a generator producing many 
duplicates and an expensive test routine, as outlines below.

<PRE class="code">
generate_and_test(Solution) :-
        empty_nb_set(Set),
        generate(Solution),
        add_nb_set(Solution, Set, true),
        test(Solution).
</PRE>

<DL>
<DT class="pubdef"><A NAME="empty_nb_set/1"><STRONG>empty_nb_set</STRONG>(<VAR>?Set</VAR>)</A></DT>
<DD class="defbody">
True if <VAR>Set</VAR> is a non-backtrackable emoty set.</DD>
<DT class="pubdef"><A NAME="add_nb_set/2"><STRONG>add_nb_set</STRONG>(<VAR>+Key, 
!Set</VAR>)</A></DT>
<DD class="defbody">
Add <VAR>Key</VAR> to <VAR>Set</VAR>. If <VAR>Key</VAR> is already a 
member of
<VAR>Set</VAR>, <A NAME="idx:addnbset3:1579"></A><A class="pred" href="nbset.html#add_nb_set/3">add_nb_set/3</A> 
succeeds without modifying <VAR>Set</VAR>.</DD>
<DT class="pubdef"><A NAME="add_nb_set/3"><STRONG>add_nb_set</STRONG>(<VAR>+Key, 
!Set, ?New</VAR>)</A></DT>
<DD class="defbody">
If <VAR>Key</VAR> is not in <VAR>Set</VAR> and <VAR>New</VAR> is unified 
to
<CODE>true</CODE> <VAR>Key</VAR> is added to <VAR>Set</VAR>. If <VAR>Key</VAR> 
is in <VAR>Set</VAR> <VAR>New</VAR> is unified to <CODE>false</CODE>. It 
can be used for many purposes:

<P>
<CENTER>
<TABLE BORDER=0 FRAME=void RULES=groups>
<TR VALIGN=top><TD><TT>add_nb_set(+, +, false)</TT></TD><TD>Test 
membership </TD></TR>
<TR VALIGN=top><TD><TT>add_nb_set(+, +, true)</TT></TD><TD>Succeed only 
if new member </TD></TR>
<TR VALIGN=top><TD><TT>add_nb_set(+, +, Var)</TT></TD><TD>Succeed, 
bindin <VAR>Var</VAR> </TD></TR>
</TABLE>

</CENTER>
</DD>
<DT class="pubdef"><A NAME="gen_nb_set/2"><STRONG>gen_nb_set</STRONG>(<VAR>+Set, 
-Key</VAR>)</A></DT>
<DD class="defbody">
Generate all members of <VAR>Set</VAR> on backtracking in the standard 
order of terms. To test membership, use <A NAME="idx:addnbset3:1580"></A><A class="pred" href="nbset.html#add_nb_set/3">add_nb_set/3</A>.</DD>
<DT class="pubdef"><A NAME="size_nb_set/2"><STRONG>size_nb_set</STRONG>(<VAR>+Set, 
-Size</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>Size</VAR> with the number of elements in <VAR>Set</VAR>.</DD>
<DT class="pubdef"><A NAME="nb_set_to_list/2"><STRONG>nb_set_to_list</STRONG>(<VAR>+Set, 
-List</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>List</VAR> with a list of all elements in set in the standard 
order of terms (i.e. and <EM>ordered list</EM>).
</DD>
</DL>

<P></BODY></HTML>
swi-prolog-nox 5.10.4-3ubuntu1 / usr / lib / swi-prolog / doc / Manual / nbset.html
