/usr/share/mozart/doc/cpitut/node6.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 4 5 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>1.5 Using Vectors in Propagators</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="node5.html#u_nesting"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD><TD><A href="node7.html#u_connect">Next >></A></TD></TR></TABLE><DIV id="u_vectors"><H2><A name="u_vectors">1.5 Using Vectors in Propagators</A></H2><P>This section explains how propagators with vectors as parameters can be implemented by the C<SPAN class="allcaps">PI</SPAN> . </P><P></P><DIV id="u_vector.element"><H3><A name="u_vector.element">1.5.1 The <EM>element</EM> Constraint</A></H3><P>The previous section explained techniques of how to handle propagator parameters which are vectors. This section implements the constraint <IMG alt="element(n, [d_1,\ldots,d_m], v)" src="latex40.png">, whose declarative semantics is defined by <IMG alt="d_n=v" src="latex41.png">. </P><P>All parameters of the <IMG alt="element" src="latex42.png"> propagator are allowed to be finite domain variables resp. a vector of finite domain variables. We have the following propagation rules, which determine the operational semantics of the propagator for the constraint <IMG alt="element" src="latex42.png">. </P><DIV id="u_vector.rule_e1"><P class="margin"></P><P> Rule 1: <IMG alt="n := dom(n) \cap \{i \; | \; \exists j \in dom(v): j \in
dom(d_i)\}" src="latex43.png"> </P></DIV><DIV id="u_vector.rule_e2"><P class="margin"></P><P> Rule 2: <IMG alt="v := dom(v) \cap \left(\bigcup_{i \in (dom(n) \cap
\{1,\ldots,m\})} dom(d_i) \right)" src="latex44.png"> </P></DIV><DIV id="u_vector.rule_e3"><P class="margin"></P><P> Rule 3: <IMG alt="\mbox{if} \;\;\; dom(n) = \{o\} \;\;\; \mbox{then} \;\;\; d_o
:= dom(v)" src="latex45.png"> </P></DIV><P>Note that <IMG alt="dom(x)" src="latex46.png"> denotes the current domain of <IMG alt="x" src="latex4.png"> and <IMG alt="x := d" src="latex47.png"> denotes the update of <IMG alt="dom(x)" src="latex46.png"> with <IMG alt="d" src="latex48.png">. </P><P>The first rule states that the domain of <IMG alt="n" src="latex6.png"> can only contain values <IMG alt="i" src="latex49.png"> such that <IMG alt="dom(d_i)" src="latex50.png"> and <IMG alt="dom(v)" src="latex51.png"> share at least one value. The propagation rule (Rule 2) states that the domain of <IMG alt="v" src="latex52.png"> cannot contain any value which does not occur in at least one <IMG alt="d_i" src="latex53.png"> indexed by the values <IMG alt="i" src="latex49.png"> of the domain of <IMG alt="n" src="latex6.png">, i. e. <IMG alt="i \in dom(n)" src="latex54.png">. The third rule says that as soon as <IMG alt="n" src="latex6.png"> is a singleton containing <IMG alt="o" src="latex55.png">, the <IMG alt="o" src="latex55.png">th element of <IMG alt="d" src="latex48.png"> is equal to <IMG alt="v" src="latex52.png">. The implementation of these rules is given in <A href="node6.html#u_vector.rules">Section 1.5.5</A>. </P><P></P></DIV><DIV id="u_vector.class"><H3><A name="u_vector.class">1.5.2 The Class Definition of <CODE>ElementProp</CODE></A></H3><P>The state of an instance of the class <CODE>ElementProp</CODE> contains a pointer to an array of <CODE>OZ_Term</CODE>s, namely <CODE>_d</CODE>. This is necessary, since it is not known beforehand how many elements are contained in the vector <IMG alt="d" src="latex48.png">. The size of the vector is stored in <CODE>_d_size</CODE>. Using a dynamic array in the state has some significant implications to the implementation of the member functions. The first function concerned is the constructor which has to allocate sufficient heap memory for the vector. The C<SPAN class="allcaps">PI</SPAN> provides the function <CODE>OZ_vectorSize()</CODE>, which computes the size of a vector passed as <CODE>OZ_Term</CODE>. This size is used to allocate an appropriately sized chunk of memory using the C<SPAN class="allcaps">PI</SPAN> function <CODE>OZ_hallocOzTerms()</CODE>. Finally, the vector as Oz data structure has to be converted to a C/C++ array. For convenience, the C<SPAN class="allcaps">PI</SPAN> provides the function <CODE>OZ_getOzTermVector()</CODE> which does this conversion. The following code gives the class definition described so far. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">class</SPAN> <SPAN class="type">ElementProp</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="type">OZ_Term</SPAN> <SPAN class="variablename">_n</SPAN>, <SPAN class="variablename">_v</SPAN>, * <SPAN class="variablename">_d</SPAN>;<BR> <SPAN class="type">int</SPAN> <SPAN class="variablename">_d_size</SPAN>;<BR><SPAN class="keyword">public</SPAN>:<BR> <SPAN class="functionname">ElementProp</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">n</SPAN>, <SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">d</SPAN>, <SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">v</SPAN>) <BR> : _n(n), _v(v), _d_size (OZ_vectorSize(d))<BR> {<BR> _d = OZ_hallocOzTerms(_d_size);<BR> OZ_getOzTermVector(d, _d);<BR> }<BR> <BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">OZ_Return</SPAN> <SPAN class="functionname">propagate</SPAN>(<SPAN class="type">void</SPAN>);<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>(ElementProp); <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> <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">virtual</SPAN> <SPAN class="type">void</SPAN> <SPAN class="functionname">gCollect</SPAN>(<SPAN class="type">void</SPAN>);<BR> <SPAN class="keyword">virtual</SPAN> <SPAN class="type">void</SPAN> <SPAN class="functionname">sClone</SPAN>(<SPAN class="type">void</SPAN>);<BR>};<BR> <BR><SPAN class="type">OZ_PropagatorProfile</SPAN> <SPAN class="reference">ElementProp</SPAN>::<SPAN class="variablename">profile</SPAN>;<BR></PRE></BLOCKQUOTE><P> </P><P>The function <CODE>getParameters()</CODE> returns the arguments of the propagator in a list. Thereby, the vector <IMG alt="d" src="latex48.png"> is represented in a sublist. The local C/C++ variable <CODE>list</CODE> is used to build up the list from the end of the vector. Therefore it is initialised as empty list and extended element-wise. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">OZ_Term</SPAN> <SPAN class="reference">ElementProp</SPAN>::<SPAN class="functionname">getParameters</SPAN>(<SPAN class="type">void</SPAN>) <SPAN class="keyword">const</SPAN> {<BR> <SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">list</SPAN> = OZ_nil();<BR> <BR> <SPAN class="keyword">for</SPAN> (<SPAN class="type">int</SPAN> <SPAN class="variablename">i</SPAN> = _d_size; i--; )<BR> list = OZ_cons(_d[i], list); <BR> <BR> <SPAN class="keyword">return</SPAN> OZ_cons(_n, <BR> OZ_cons(list, <BR> OZ_cons(_v, OZ_nil())));<BR>}<BR></PRE></BLOCKQUOTE><P> </P><P>The member functions <CODE>gCollect()</CODE> and <CODE>sClone()</CODE> update the propagator's references to the heap after the propagator has been copied by garbage collection or space cloning. Updating the data members <CODE>_n</CODE> and <CODE>_v</CODE> is done by applying <CODE>OZ_gCollectTerm()</CODE> resp. <CODE>OZ_sCloneTerm</CODE> to them. Updating the array <CODE>_d</CODE> requires to duplicate the array and then to update all elements. This funtionality is provided by <CODE>OZ_gCollectAllocBlock()</CODE> (<CODE>OZ_sCloneAllocBlock()</CODE>) for garbage collection (space cloning). Here comes the code of those member functions. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">void</SPAN> <SPAN class="reference">ElementProp</SPAN>::<SPAN class="functionname">gCollect</SPAN>(<SPAN class="type">void</SPAN>) {<BR> OZ_gCollectTerm(_n);<BR> OZ_gCollectTerm(_v);<BR> _d = OZ_gCollectAllocBlock(_d_size, _d);<BR>}<BR> <BR><SPAN class="type">void</SPAN> <SPAN class="reference">ElementProp</SPAN>::<SPAN class="functionname">sClone</SPAN>(<SPAN class="type">void</SPAN>) {<BR> OZ_sCloneTerm(_n); <BR> OZ_sCloneTerm(_v);<BR> _d = OZ_sCloneAllocBlock(_d_size, _d);<BR>}<BR></PRE></BLOCKQUOTE><P> </P><P></P></DIV><DIV id="u_vector.header"><H3><A name="u_vector.header">1.5.3 The Header Function</A></H3><P>The implementation of the C/C++ function to impose the <IMG alt="element" src="latex42.png"> propagator is straightforward with the techniques presented in <A href="node5.html#u_nesting">Section 1.4</A>. Note that this C/C++ function treats empty vectors separately, since an empty list (resp. literal) is a valid vector, but the <IMG alt="element" src="latex42.png"> constraint is not defined on empty vectors. Therefore, the header function is left via the member function <CODE><SPAN class="keyword">fail</SPAN>()</CODE> in case a vector of length 0 is detected. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="functionname">OZ_BI_define</SPAN>(fd_element, 3, 0)<BR>{<BR> OZ_EXPECTED_TYPE(OZ_EM_FD<BR> <SPAN class="string">","</SPAN>OZ_EM_VECT OZ_EM_FD<BR> <SPAN class="string">","</SPAN>OZ_EM_FD);<BR> <BR> <SPAN class="type">ExtendedExpect</SPAN> <SPAN class="variablename">pe</SPAN>;<BR> <BR> OZ_EXPECT(pe, 0, expectIntVar);<BR> OZ_EXPECT(pe, 1, expectVectorIntVarAny);<BR> OZ_EXPECT(pe, 2, expectIntVar);<BR> <BR> <SPAN class="keyword">if</SPAN> (OZ_vectorSize(OZ_in(1)) == 0) <BR> <SPAN class="keyword">return</SPAN> pe.fail();<BR> <BR> <SPAN class="keyword">return</SPAN> pe.impose(<SPAN class="keyword">new</SPAN> <SPAN class="type">ElementProp</SPAN>(OZ_in(0), <BR> OZ_in(1), <BR> OZ_in(2)));<BR>}<BR>OZ_BI_end<BR> <BR></PRE></BLOCKQUOTE><P> </P><P>The implementation uses the class <CODE>ExtendedExpect</CODE> (as explained in <A href="node5.html#u_nesting.customize">Section 1.4.3</A> since the imposition of this propagator requires to check if the second argument is a vector of finite domain variables and this functionality is not directly provided by the C<SPAN class="allcaps">PI</SPAN> class <CODE>OZ_Expect</CODE>. </P><P></P></DIV><DIV id="u_vector.iterators"><H3><A name="u_vector.iterators">1.5.4 Iterators Make Life Easier</A></H3><P>The propagator for the <IMG alt="element" src="latex42.png"> constraint operates on a vector, which is represented by an array in the state of the propagator. The member function <CODE>propagate()</CODE> has to apply certain functions, like <CODE>leave()</CODE> and <CODE><SPAN class="keyword">fail</SPAN>()</CODE>, to all elements of the array at once and not to individual elements. Therefore, it makes sense to define an <EM>iterator</EM> for such data structures. </P><P>The following code presents an iterator class for an <CODE>OZ_FDIntVar</CODE> array, which will be used by the member function <CODE>propagate()</CODE> of the <IMG alt="element" src="latex42.png"> propagator. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">class</SPAN> <SPAN class="type">Iterator_OZ_FDIntVar</SPAN> {<BR><SPAN class="keyword">private</SPAN>:<BR> <SPAN class="type">int</SPAN> <SPAN class="variablename">_l_size</SPAN>;<BR> <SPAN class="type">OZ_FDIntVar</SPAN> * <SPAN class="variablename">_l</SPAN>;<BR><SPAN class="keyword">public</SPAN>:<BR> <SPAN class="functionname">Iterator_OZ_FDIntVar</SPAN>(<SPAN class="type">int</SPAN> <SPAN class="variablename">s</SPAN>, <SPAN class="type">OZ_FDIntVar</SPAN> * <SPAN class="variablename">l</SPAN>)<BR> : _l_size(s), _l(l) { }<BR> <BR> <SPAN class="type">OZ_Boolean</SPAN> <SPAN class="functionname">leave</SPAN>(<SPAN class="type">void</SPAN>) {<BR> <SPAN class="type">OZ_Boolean</SPAN> <SPAN class="variablename">vars_left</SPAN> = OZ_FALSE;<BR> <SPAN class="keyword">for</SPAN> (<SPAN class="type">int</SPAN> <SPAN class="variablename">i</SPAN> = _l_size; i--; ) <BR> vars_left |= _l[i].leave();<BR> <SPAN class="keyword">return</SPAN> vars_left;<BR> }<BR> <SPAN class="type">void</SPAN> <SPAN class="functionname">fail</SPAN>(<SPAN class="type">void</SPAN>) {<BR> <SPAN class="keyword">for</SPAN> (<SPAN class="type">int</SPAN> <SPAN class="variablename">i</SPAN> = _l_size; i--; _l[i].fail());<BR> }<BR>};<BR></PRE></BLOCKQUOTE><P> </P><P>The iterator class provides the member functions <CODE>leave()</CODE> and <CODE><SPAN class="keyword">fail</SPAN>()</CODE> which call in turn the corresponding member functions on all elements of the array <CODE>l</CODE>. The function <CODE>leave()</CODE> returns 1 if there is at least one non-singleton domain left. </P><P></P></DIV><DIV id="u_vector.rules"><H3><A name="u_vector.rules">1.5.5 Implementing the Propagation Rules</A></H3><P>The <CODE>propagate()</CODE> member function implements the propagation rules presented in <A href="node6.html#u_vector.element">Section 1.5.1</A> for the constraint <IMG alt="element(n, [d_1,\ldots,d_m], v)" src="latex40.png">. </P><P>The function <CODE>propagate()</CODE> defines local variables of type <CODE>OZ_FDIntVar</CODE>. Then it initializes the iterator object <CODE>D</CODE>. That avoids having to apply a member function to each element of <CODE>d</CODE> by hand if all elements have to be considered. The following <CODE><SPAN class="keyword">for</SPAN></CODE>-loop initializes the elements of <CODE>d</CODE>. </P><P>The code coming after the implementation of the propagation rules (see below) checks if there is a non-singleton domain left, and if so it returns <CODE>OZ_SLEEP</CODE>. Otherwise the propagator is entailed and consequently returns <CODE>OZ_ENTAILED</CODE>. The label <CODE>failure</CODE> is provided because of the use of the macro <CODE>FailOnEmpty</CODE> (see <A href="node3.html#u_getting_started.propagation">Section ``The Propagation Part of a Propagator''</A>) and the corresponding code applies <CODE><SPAN class="keyword">fail</SPAN></CODE> to all variables of type <CODE>OZ_FDIntVar</CODE>. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">OZ_Return</SPAN> <SPAN class="reference">ElementProp</SPAN>::<SPAN class="functionname">propagate</SPAN>(<SPAN class="type">void</SPAN>)<BR>{<BR> <SPAN class="type">OZ_FDIntVar</SPAN> <SPAN class="variablename">n</SPAN>(_n), v(_v), d[_d_size];<BR> <SPAN class="type">Iterator_OZ_FDIntVar</SPAN> <SPAN class="variablename">D</SPAN>(_d_size, d);<BR> <BR> <SPAN class="keyword">for</SPAN> (<SPAN class="type">int</SPAN> <SPAN class="variablename">i</SPAN> = _d_size; i--; )<BR> d[i].read(_d[i]);<BR> <BR> { /* <SPAN class="comment">propagation rule for n */</SPAN> <BR> <SPAN class="type">OZ_FiniteDomain</SPAN> <SPAN class="variablename">aux_n</SPAN>(fd_empty);<BR> <BR> <SPAN class="keyword">for</SPAN> (<SPAN class="type">int</SPAN> <SPAN class="variablename">i</SPAN> = _d_size; i --; )<BR> <SPAN class="keyword">if</SPAN> ((*(d[i]) & *v) != fd_empty) <BR> aux_n += (i + 1);<BR> <BR> FailOnEmpty(*n &= aux_n);<BR> }<BR> { /* <SPAN class="comment">propagation rule for v */</SPAN> <BR> <SPAN class="type">OZ_FiniteDomain</SPAN> <SPAN class="variablename">aux_v</SPAN>(fd_empty);<BR> <BR> <SPAN class="keyword">for</SPAN> (<SPAN class="type">int</SPAN> <SPAN class="variablename">i</SPAN> = n->getMinElem(); <BR> i != -1;<BR> i = n->getNextLargerElem(i))<BR> aux_v = aux_v | *(d[i - 1]);<BR> <BR> FailOnEmpty(*v &= aux_v);<BR> }<BR> { /* <SPAN class="comment">propagation rule for d[n] */</SPAN> <BR> <SPAN class="keyword">if</SPAN> (n->getSize() == 1) {<BR> <SPAN class="type">int</SPAN> <SPAN class="variablename">o</SPAN> = n->getSingleElem();<BR> D.leave(); n.leave(); v.leave();<BR> <SPAN class="keyword">return</SPAN> replaceBy(_v, _d[o - 1]);<BR> }<BR> }<BR> <SPAN class="keyword">return</SPAN> (D.leave() | n.leave() | v.leave()) <BR> ? OZ_SLEEP : OZ_ENTAILED;<BR> <BR><SPAN class="reference">failure</SPAN>:<BR> D.fail(); n.fail(); v.fail();<BR> <SPAN class="keyword">return</SPAN> OZ_FAILED;<BR>}<BR></PRE></BLOCKQUOTE><P> </P><P>The propagation rules are implemented in the same order as they are presented in <A href="node6.html#u_vector.element">Section 1.5.1</A>. That ensures that the values for <IMG alt="i" src="latex49.png"> in rule 2 <A href="node6.html#u_vector.rule_e2">*</A> are always in the index range of the vector <CODE>d</CODE>, since rule 1 <A href="node6.html#u_vector.rule_e1">*</A> makes sure that only valid indices are contained in the domain of <IMG alt="n" src="latex6.png">. Note that the indices of vectors in Oz range over <IMG alt="1 \ldots n" src="latex56.png"> and the corresponding indices of C/C++ arrays over <IMG alt="0 \ldots n-1" src="latex57.png">. </P><DIV class="apropos"><P class="margin">Implementation of propagation rules</P><P> The implementation of the propagation rule 1 <A href="node6.html#u_vector.rule_e1">*</A> starts with an initially empty auxiliary domain <CODE>aux_n</CODE>. It collects all integers <IMG alt="i" src="latex49.png"> in the auxiliary domain, where the intersection of <IMG alt="d_i" src="latex53.png"> and <IMG alt="v" src="latex52.png"> is not empty. That is equivalent to finding at least one <IMG alt="j" src="latex58.png"> being contained in <IMG alt="d_i" src="latex53.png"> and <IMG alt="v" src="latex52.png">. The domain of <IMG alt="n" src="latex6.png">, i. e. <CODE>n</CODE>, is constrained by <CODE>aux_n</CODE>. </P></DIV><P>The second rule 2 <A href="node6.html#u_vector.rule_e2">*</A> states that the domain of <IMG alt="v" src="latex52.png"> cannot contain values that are not possible elements of the vector <IMG alt="d" src="latex48.png">. The implementation uses again an initially empty auxiliary domain <CODE>aux_v</CODE> and collects in a loop all elements of <IMG alt="d_i" src="latex53.png"> in <CODE>aux_v</CODE> by iterating over all <IMG alt="i" src="latex49.png"> being contained in <IMG alt="n" src="latex6.png">. The implementation of this rule closes with constraining <CODE>v</CODE> by <CODE>aux_v</CODE>. </P><P>The last rule, rule 3 <A href="node6.html#u_vector.rule_e3">*</A>, is only applied if <IMG alt="n" src="latex6.png"> is determined, i. e. <CODE>n<SPAN class="keyword">-></SPAN>getSize()</CODE> returns 1. Then it retrieves the value <IMG alt="o" src="latex55.png">, applies <CODE>leave()</CODE> to all variables of type <CODE>OZ_FDIntVar</CODE> and replaces the <IMG alt="element" src="latex42.png"> propagator by the equality <IMG alt="v = d_o" src="latex59.png"> using the member function <CODE>replaceBy()</CODE> of class <CODE>OZ_Propagator</CODE> (see <A href="node4.html#u_replacing">Section 1.3</A>).</P><P> </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node5.html#u_nesting"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD><TD><A href="node7.html#u_connect">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>
|