/usr/share/mozart/doc/cpitut/node7.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>1.6 Connecting Finite Domain and Finite Set Constraints</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node6.html#u_vectors"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD><TD><A href="node8.html#u_advanced">Next >></A></TD></TR></TABLE><DIV id="u_connect"><H2><A name="u_connect">1.6 Connecting Finite Domain and Finite Set Constraints</A></H2><P> The propagator in this section involves apart from finite domain constraints also finite set constraints. Its semantics is straightforward: it connects a domain variable <IMG alt="D" src="latex7.png"> and a set variable <IMG alt="S" src="latex10.png"> by projecting the changes of the constraints in both directions. Hereby, the finite domain variable designates an integer <IMG alt="i" src="latex49.png"> (as usual) and the set variable designates a singleton set <IMG alt="\{e\}" src="latex60.png"> where <IMG alt="i = e" src="latex61.png">. </P><P class="margin">Propagation Rules</P><P> There are three propagation rules: </P><OL type="1"><LI><P><IMG alt="\#S = 1" src="latex62.png"></P></LI><LI><P><IMG alt="D \subseteq S" src="latex63.png"></P></LI><LI><P><IMG alt="S \subseteq D" src="latex64.png"></P></LI></OL><P> The last two rules propagate the changes of the upper bound of the set constraint to the domain constraint and the other way around. </P><H3><A name="label3">1.6.1 The Class Definition</A></H3><P> The class definition does not have any particularities. It follows the scheme known from previous sections. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">class</SPAN> <SPAN class="type">ConnectProp</SPAN> : <SPAN class="keyword">public</SPAN> <SPAN class="type">OZ_Propagator</SPAN> {<BR><SPAN class="keyword">private</SPAN>:<BR> <SPAN class="keyword">static</SPAN> <SPAN class="type">OZ_PropagatorProfile</SPAN> <SPAN class="variablename">profile</SPAN>;<BR><SPAN class="keyword">protected</SPAN>:<BR> <SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">_fs</SPAN>;<BR> <SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">_fd</SPAN>;<BR><SPAN class="keyword">public</SPAN>:<BR> <SPAN class="functionname">ConnectProp</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">fsvar</SPAN>, <SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">fdvar</SPAN>) <BR> : _fs(fsvar), _fd(fdvar) {}<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">void</SPAN> <SPAN class="functionname">gCollect</SPAN>(<SPAN class="type">void</SPAN>) {<BR> OZ_gCollectTerm(_fd);<BR> OZ_gCollectTerm(_fs);<BR> }<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">void</SPAN> <SPAN class="functionname">sClone</SPAN>(<SPAN class="type">void</SPAN>) {<BR> OZ_sCloneTerm(_fd);<BR> OZ_sCloneTerm(_fs);<BR> }<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">size_t</SPAN> <SPAN class="functionname">sizeOf</SPAN>(<SPAN class="type">void</SPAN>) {<BR> <SPAN class="keyword">return</SPAN> <SPAN class="keyword">sizeof</SPAN>(ConnectProp);<BR> }<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">OZ_Term</SPAN> <SPAN class="functionname">getParameters</SPAN>(<SPAN class="type">void</SPAN>) <SPAN class="keyword">const</SPAN> {<BR> <SPAN class="keyword">return</SPAN> OZ_cons(_fs, (OZ_cons(_fd, OZ_nil())));<BR> }<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">OZ_PropagatorProfile</SPAN> *<SPAN class="functionname">getProfile</SPAN>(<SPAN class="type">void</SPAN>) <SPAN class="keyword">const</SPAN> {<BR> <SPAN class="keyword">return</SPAN> &profile;<BR> }<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">OZ_Return</SPAN> <SPAN class="functionname">propagate</SPAN>();<BR>};<BR></PRE></BLOCKQUOTE><P> Note that set variables are handled the same way as domain variables. </P><H3><A name="label4">1.6.2 The Propagation Function</A></H3><P> The implementation of the propagation function starts with retrieving the constrained variables from the constraint store using the constructors of the classes <CODE>OZ_FDIntVar</CODE> and <CODE>OZ_FSetVar</CODE>. The class <CODE>OZ_FSetVar</CODE> provides for the same member functions as <CODE>OZ_FDIntVar</CODE> such that handling set variables does not differ from handling domain variables. </P><P class="margin">Propagation</P><P> The propagation starts with the first rule. it uses the member function <CODE>OZ_FSetConstraint<SPAN class="keyword">::</SPAN>putcard(int<SPAN class="keyword">,</SPAN> <BR>int)</CODE> to impose the cardinality constraint upon <IMG alt="S" src="latex10.png">. The second rule implemented by removing all elements from <IMG alt="D" src="latex7.png"> that are definitely not in <IMG alt="S" src="latex10.png"> (see <A href="../cpiref/node8.html#r_fsc.refl">Section 1.8.3 of ``The Mozart Constraint Extensions Reference''</A> for details on <CODE>OZ_FSetConstraint<SPAN class="keyword">::</SPAN>getNotInSet()</CODE>). The last propagation rule uses the operator <CODE>OZ_FSetConstraint<SPAN class="keyword">::</SPAN>operator <SPAN class="keyword"><=</SPAN></CODE> for <IMG alt="S \subseteq
D" src="latex65.png">. The constructor <CODE>OZ_FSetConstraint</CODE> is used to convert the <CODE>OZ_Finite Domain</CODE> appropriately. Note that imposing constraints on <IMG alt="D" src="latex7.png"> resp. <IMG alt="S" src="latex10.png"> are guarded by <CODE>FailOnEmpty</CODE> resp. <CODE>FailOnInvalid</CODE> to catch failures. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">OZ_Return</SPAN> <SPAN class="reference">ConnectProp</SPAN>::<SPAN class="functionname">propagate</SPAN>() {<BR> <BR>printf(<SPAN class="string">"ConnectProp::propagate\n"</SPAN>);<BR> <BR> <SPAN class="type">OZ_FDIntVar</SPAN> <SPAN class="variablename">fd</SPAN>(_fd);<BR> <SPAN class="type">OZ_FSetVar</SPAN> <SPAN class="variablename">fs</SPAN>(_fs);<BR> <BR> // <SPAN class="comment">1st propagation rule<BR></SPAN> fs->putCard(1, 1); <BR> <BR> // <SPAN class="comment">2nd propagation rule<BR></SPAN> FailOnEmpty(*fd -= fs->getNotInSet());<BR> <BR> // <SPAN class="comment">3rd propagation rule<BR></SPAN> FailOnInvalid(*fs <= OZ_FSetConstraint(*fd));<BR> <BR> <SPAN class="keyword">return</SPAN> (fd.leave() | fs.leave()) ? OZ_SLEEP : OZ_ENTAILED;<BR> <BR><SPAN class="reference">failure</SPAN>:<BR> fd.fail(); fs.fail();<BR> <SPAN class="keyword">return</SPAN> OZ_FAILED;<BR>}<BR></PRE></BLOCKQUOTE><P> The macro <CODE>FailOnInvalid</CODE> is define as </P><BLOCKQUOTE class="linenumbers"><PRE>#define <SPAN class="functionname">FailOnInvalid</SPAN>(<SPAN class="variablename">X</SPAN>) <SPAN class="keyword">if</SPAN>(!(X)) <SPAN class="keyword">goto</SPAN> <SPAN class="reference">failure</SPAN>;<BR></PRE></BLOCKQUOTE><P> since finite set operator return <CODE>OZ_FALSE</CODE> in case an inconsistency occured. </P><P> The propagator closes with calling <CODE>leave()</CODE> for both variables and returning <CODE>OZ_SLEEP</CODE> resp. <CODE>OZ_ENTAILED</CODE> depending on whether not all variables denote values or they do. </P><H3><A name="label5">1.6.3 The Header Function and Connecting to the Native Functor Interface</A></H3><P> The header function uses <CODE>OZ_Expect<SPAN class="keyword">::</SPAN>expectFSetVar</CODE> to check for a set variable. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="functionname">OZ_BI_define</SPAN>(connect, 2, 0)<BR>{<BR> OZ_EXPECTED_TYPE(OZ_EM_FSET<SPAN class="string">","</SPAN>OZ_EM_FD);<BR> <SPAN class="type">OZ_Expect</SPAN> <SPAN class="variablename">pe</SPAN>;<BR> OZ_EXPECT(pe, 0, expectFSetVar);<BR> OZ_EXPECT(pe, 1, expectIntVar);<BR> <BR> <SPAN class="keyword">return</SPAN> pe.impose(<SPAN class="keyword">new</SPAN> <SPAN class="type">ConnectProp</SPAN>(OZ_in(0), OZ_in(1)));<BR>}<BR>OZ_BI_end<BR> <BR><SPAN class="type">OZ_PropagatorProfile</SPAN> <SPAN class="reference">ConnectProp</SPAN>::<SPAN class="variablename">profile</SPAN>;<BR></PRE></BLOCKQUOTE><P> The predefined macro <CODE>OZ_EM_FSET</CODE> is used to produce an appropriate error message in case an type exception has to be risen. </P><P> The C part of the native functor interface is given below. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">OZ_C_proc_interface</SPAN> *<SPAN class="functionname">oz_init_module</SPAN>(<SPAN class="type">void</SPAN>)<BR>{<BR> <SPAN class="keyword">static</SPAN> <SPAN class="type">OZ_C_proc_interface</SPAN> <SPAN class="variablename">i_table</SPAN>[] = {<BR> {<SPAN class="string">"connect"</SPAN>, 2, 0, connect},<BR> {0, 0, 0, 0}<BR> };<BR> <BR> <SPAN class="keyword">return</SPAN> i_table;<BR>}<BR></PRE></BLOCKQUOTE><P> </P><H3><A name="label6">1.6.4 Testing the Propagator</A></H3><P>To make the propagator available on Oz side feed the following code: </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR>Connect = {{New Module<SPAN class="keyword">.</SPAN>manager init}<BR> link(url: <SPAN class="string">'sync.so{native}'</SPAN> $)}<SPAN class="keyword">.</SPAN>connect<BR>{Wait Connect}<BR>{Show Connect}<BR></PRE></BLOCKQUOTE><P> The variable <CODE>Connect</CODE> refers to the propagator. By feeding the code below line by line one can observe (e. g. using the Browser <A href="../browser/index.html">``The Oz Browser''</A>), how the propagator works. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> S = {FS<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>decl}<BR> I = {FD<SPAN class="keyword">.</SPAN>decl} <BR> % <SPAN class="comment">S = I = <BR></SPAN>{Connect S I} % <SPAN class="comment">{{}..{0#134217726}}#1 {0#134217726}<BR></SPAN>{FS<SPAN class="keyword">.</SPAN>exclude 2 S} % <SPAN class="comment">{{}..{0#1 3#134217726}}#1 {0#1 3#34217726}<BR></SPAN>I <SPAN class="keyword">::</SPAN> 1<SPAN class="keyword">#</SPAN>100 % <SPAN class="comment">{{}..{1 3#100}}#1 {1 3#100}<BR></SPAN>{FS<SPAN class="keyword">.</SPAN>exclude 1 S} % <SPAN class="comment">{{}..{3#100}}#1 {3#100}<BR></SPAN>I <SPAN class="keyword"><:</SPAN> 4 % <SPAN class="comment">{3}#1 3<BR></SPAN></PRE></BLOCKQUOTE><P> The comments at the end of each line indicate the constraints after feeding that line. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node6.html#u_vectors"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD><TD><A href="node8.html#u_advanced">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|