/usr/share/mozart/doc/cpitut/node8.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 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>1.7 Advanced Topics</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="node7.html#u_connect"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD></TR></TABLE><DIV id="u_advanced"><H2><A name="u_advanced">1.7 Advanced Topics</A></H2><P>This section discusses issues of practical relevance not covered in this manual so far. It explains implementation techniques rather than giving ready-to-use code. </P><P></P><DIV id="u_advanced.detect"><H3><A name="u_advanced.detect">1.7.1 Detecting Equal Variables in a Vector</A></H3><P>A feature of the finite domain constraint system of Oz is that it is able to exploit equality between variables. For example, one can simplify linear equations in case equal variables are detected. Let us regard the equation <IMG alt="2u+v+7w-2x+y=0" src="latex66.png">. Imposing the equality constraints <IMG alt="u=x" src="latex67.png"> and <IMG alt="v=y" src="latex68.png"> allows to simplify the equation to <IMG alt="7w+2y=0" src="latex69.png">. This simplification offers the advantage that the propagator becomes computationally less complex resulting in a better execution performance. </P><P>The C<SPAN class="allcaps">PI</SPAN> provides the function </P><DIV class="apropos"><P class="margin"><CODE>OZ_findEqualVars</CODE></P><P> <CODE> int <SPAN class="keyword">*</SPAN> OZ_findEqualVars(int sz<SPAN class="keyword">,</SPAN> OZ_Term <SPAN class="keyword">*</SPAN> v)</CODE> </P></DIV><P>to detect equal variables in an <CODE>OZ_Term</CODE> array. It expects <CODE>v</CODE> to be an array with <CODE>sz</CODE> elements. Assume the application </P><P><CODE> int <SPAN class="keyword">*</SPAN> pa = OZ_findEqualVars(arr_sz<SPAN class="keyword">,</SPAN> x);</CODE> </P><P>where <CODE>pa</CODE> is called the position array. The array <CODE>x</CODE> is scanned with ascending index starting from 0 to determine the values of <CODE>pa</CODE>. If <CODE>x[i]</CODE> denotes a variable and this variable occurs the first time, the value of <CODE>pa[i]</CODE> is <CODE>i</CODE>. In case the variable occurs not the first time, <CODE>pa[i]</CODE> contains the index of the first occurrence. If <CODE>x[i]</CODE> denotes an integer, <CODE>pa[i]</CODE> contains -1. </P><P>As an example, consider the constraint <IMG alt="2a+3b-4c-5d+4e+8=0" src="latex70.png"> where at runtime the constraint <IMG alt="c=e \wedge d=2" src="latex71.png"> is imposed. The result of the equal variable detection is as follows. </P><P></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TD><P><CODE>i</CODE></P></TD><TD><P>0</P></TD><TD><P>1</P></TD><TD><P>2</P></TD><TD><P>3</P></TD><TD><P>4</P></TD></TR><TR valign="top"><TD><P><CODE>x[i]</CODE></P></TD><TD><P>a</P></TD><TD><P>b</P></TD><TD><P>c</P></TD><TD><P>d</P></TD><TD><P>e</P></TD></TR><TR valign="top"><TD><P><CODE>pa[i]</CODE></P></TD><TD><P>0</P></TD><TD><P>1</P></TD><TD><P>2</P></TD><TD><P>-1</P></TD><TD><P>2</P></TD></TR></TABLE><P> </P><P>The state of the propagator can now be updated to represent the equivalent constraint <IMG alt="2a+3b-2=0" src="latex72.png">. Thus, this simplification avoids tedious handling of equal variables in the propagation algorithm and it improves memory consumption and runtime behaviour. </P><DIV class="apropos"><P class="margin"><CODE>mayBeEqualVars</CODE></P><P> To avoid unnecessary calls of <CODE>OZ_findEqualVars()</CODE>, this function is intended to be used in conjunction with the member function <CODE>mayBeEqualVars()</CODE> of class <CODE>OZ_Propagator</CODE> (see also <A href="../cpiref/node3.html#r_prop.provided">Section 1.3.3 of ``The Mozart Constraint Extensions Reference''</A>). In case an equality constraint has been imposed on at least one variable occurring in the propagator's parameters, <CODE>mayBeEqualVars()</CODE> returns 1. </P></DIV><P>Note that the function <CODE>OZ_findEqualVars()</CODE> returns a pointer to a static array, i. e. another application of this function will override the previous values. </P><P></P></DIV><DIV id="u_advanced.redundant"><H3><A name="u_advanced.redundant">1.7.2 Avoiding Redundant Copying</A></H3><P>In <A href="node6.html#u_vector.class">Section 1.5.2</A> we learned that data structures referenced by the state of a propagator have to be copied whenever the Oz runtime system calls either the member function <CODE>gCollect()</CODE> or <CODE>sClone()</CODE>. But constant data structures, i. e. data structures which do not change during the propagator's lifetime, need only to be duplicated in case of a garbage collection. Otherwise it is sufficient to have a reference to such a constant data structure. Thus it is useful to use a reference counting technique to keep track of the number of references to the constant data structure, so that the destructor of the propagator can dispose the data structure when there is no reference left. </P><P>That is one reason why there are distinct member functions for garbage collection and space cloning. Garbage collection requires a fresh copy of constant data structures while space cloning requires only a reference and a reference counting technique is applicable. </P><P>The code presented in this section defines the class <CODE>ConstDataHdl</CODE> which can be used to avoid redundant copying of constant data structures by approptiate actions in <CODE>gCollect()</CODE> and <CODE>sClone()</CODE>. The class <CODE>ConstDataHdl</CODE> implements a reference counting scheme and holds in its state, apart from the actual constant data structure, the reference counter <CODE>_refCount</CODE> and the forward reference <CODE>_newLoc</CODE>. In our example the constant data structure is the string <CODE><SPAN class="string">"Constant data"</SPAN></CODE>. </P><P>The constructor of <CODE>ConstDataHdl</CODE> creates the constant data structure and initialises the reference counting mechanism. The operator <CODE>new</CODE> is redefined to allocate instances of <CODE>ConstDataHdl</CODE> on the heap. The operator <CODE>delete</CODE> decrements the reference counter and deallocates the instance of <CODE>ConstDataHdl</CODE> from the heap if there is no reference left. The member function <CODE>getRef()</CODE> is to be used if a new reference to an instance of <CODE>ConstDataHdl</CODE> is needed (<CODE>sClone()</CODE>). It increments <CODE>_refCount</CODE> and returns the self-reference <CODE>this</CODE>. The member function <CODE>copy()</CODE> is to be used if the constant data structure has to be duplicated which is the case in <CODE>gCollect()</CODE>. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">class</SPAN> <SPAN class="type">ConstDataHdl</SPAN> {<BR><SPAN class="keyword">private</SPAN>:<BR> <SPAN class="type">char</SPAN> <SPAN class="variablename">_constData</SPAN>[100];<BR> <BR> <SPAN class="type">int</SPAN> <SPAN class="variablename">_refCount</SPAN>;<BR> <SPAN class="type">ConstDataHdl</SPAN> * <SPAN class="variablename">_newLoc</SPAN>; <BR><SPAN class="keyword">public</SPAN>:<BR> <SPAN class="functionname">ConstDataHdl</SPAN>(<SPAN class="type">char</SPAN> * <SPAN class="variablename">str</SPAN>)<BR> : _refCount(1), _newLoc(<SPAN class="reference">NULL</SPAN>) {<BR> strcpy(_constData, str);<BR> }<BR> <SPAN class="keyword">static</SPAN> <SPAN class="type">void</SPAN> * <SPAN class="keyword">operator</SPAN> <SPAN class="keyword">new</SPAN> (<SPAN class="type">size_t</SPAN> <SPAN class="variablename">sz</SPAN>) {<BR> <SPAN class="keyword">return</SPAN> OZ_hallocChars(sz);<BR> }<BR> <SPAN class="keyword">static</SPAN> <SPAN class="type">void</SPAN> <SPAN class="keyword">operator</SPAN> <SPAN class="keyword">delete</SPAN> (<SPAN class="type">void</SPAN> * <SPAN class="variablename">p</SPAN>) {<BR> <SPAN class="keyword">if</SPAN> (0 == --((<SPAN class="type">ConstDataHdl</SPAN> *) p)->_refCount)<BR> OZ_hfreeChars((<SPAN class="type">char</SPAN> *) p,<SPAN class="keyword">sizeof</SPAN>(ConstDataHdl));<BR> }<BR> <SPAN class="type">ConstDataHdl</SPAN> * <SPAN class="functionname">getRef</SPAN>(<SPAN class="type">void</SPAN>) { <BR> _refCount += 1; <BR> <SPAN class="keyword">return</SPAN> <SPAN class="keyword">this</SPAN>; <BR> }<BR> <SPAN class="type">ConstDataHdl</SPAN> * <SPAN class="functionname">copy</SPAN> (<SPAN class="type">void</SPAN>) {<BR> <SPAN class="keyword">if</SPAN> (_newLoc)<BR> _newLoc->getRef();<BR> <SPAN class="keyword">else</SPAN> <BR> _newLoc = <SPAN class="keyword">new</SPAN> <SPAN class="type">ConstDataHdl</SPAN>(_constData);<BR> <SPAN class="keyword">return</SPAN> _newLoc;<BR> }<BR>};<BR> <BR></PRE></BLOCKQUOTE><P> </P><P>At its first invocation the member function <CODE>copy()</CODE> duplicates the instance it is called from, sets the forward reference <CODE>newLoc</CODE> to the location of the duplicate, and returns the reference to the duplicate. All subsequent invocations only increment the reference counter of the duplicate and return a reference to the duplicate.</P><P>To use the presented reference counting scheme in a propagator add to ...</P><P> </P><DL><DT>... the class definition of the propagator: </DT><DD><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">ConstDataHdl</SPAN> * <SPAN class="variablename">_constData</SPAN>;<BR></PRE></BLOCKQUOTE><P> </P></DD><DT>... the constructor definition of the propagator:</DT><DD><P></P><BLOCKQUOTE class="linenumbers"><PRE>_constData = <SPAN class="keyword">new</SPAN> <SPAN class="type">ConstDataHdl</SPAN>(<SPAN class="string">"Constant data"</SPAN>);<BR></PRE></BLOCKQUOTE><P> </P></DD><DT>... the destructor definition of the propagator:</DT><DD><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">delete</SPAN> _constData;<BR></PRE></BLOCKQUOTE><P> </P></DD><DT>... the definition of the member function <CODE>gCollect()</CODE>:</DT><DD><P></P><BLOCKQUOTE class="linenumbers"><PRE> _constData = _constData->copy();<BR></PRE></BLOCKQUOTE><P> </P></DD><DT>... the definition of the member function <CODE>sClone()()</CODE>:</DT><DD><P></P><BLOCKQUOTE class="linenumbers"><PRE> _constData = _constData->getRef();<BR></PRE></BLOCKQUOTE><P></P></DD></DL><P> </P><P>The presented class definition of <CODE>ConstDataHdl</CODE> can be adopted by redefining the embedded data structure <CODE>ConstDataHdl<SPAN class="keyword">::</SPAN>_constData</CODE> appropriately. </P><P></P></DIV><DIV id="u_advanced.reified"><H3><A name="u_advanced.reified">1.7.3 Reified Constraints</A></H3><P>This section sketches the implementation of reified constraints (see the section on reified constraints in <A href="../fdt/node35.html#chapter.reified">Chapter 8 of ``Finite Domain Constraint Programming in Oz. A Tutorial.''</A>) and goes into more details concerning the particularities of the class <CODE>OZ_FDIntVar</CODE>. </P><P>The idea of reification is as follows: A <IMG alt="0/1" src="latex73.png">-variable <EM>R</EM> is associated with a constraint <IMG alt="C" src="latex74.png">. The variable <IMG alt="R" src="latex75.png"> is called <EM>control variable</EM>. As long as the domain of <IMG alt="R" src="latex75.png"> is not constrained to a singleton domain, the constraint <IMG alt="C" src="latex74.png"> checks if the constraint store entails or disentails <IMG alt="C" src="latex74.png">. If so, the variable <IMG alt="R" src="latex75.png"> is constrained to 1 or 0, respectively. Otherwise, if <IMG alt="R" src="latex75.png"> is constrained to 0 or 1 then the constraint <IMG alt="C" src="latex74.png"> or <IMG alt="\neg C" src="latex76.png">, respectively, is imposed to the store. </P><P>The implementation of a reified constraint is explained for <IMG alt="(x
\leq y) \leftrightarrow r" src="latex77.png">, which will be implemented by the class <CODE>ReifiedLessEqProp</CODE>. We assume that the constraints <IMG alt="x \leq y" src="latex78.png"> and <IMG alt="x > y" src="latex79.png"> are implemented by the classes <CODE>LessEqProp</CODE> resp.<CODE>GreaterProp</CODE>. This section focuses on implementing <CODE>ReifiedLessEqProp<SPAN class="keyword">::</SPAN>propagate()</CODE>. </P><P>There are basically two cases to be regarded. The first case is that the domain of the control variable is an integer. Then <IMG alt="(x \leq y) \leftrightarrow r" src="latex80.png"> has to be replaced either by <IMG alt="x \leq y" src="latex78.png"> or by <IMG alt="x > y" src="latex79.png">. The technique to replace a propagator by another one is explained in <A href="node4.html#u_replacing">Section 1.3</A>. </P><P></P><DIV class="apropos"><P class="margin">Encapsulated Constraint Propagation</P><P> If the control variable is still a <IMG alt="0/1" src="latex73.png"> variable, the reified propagator checks if the constraint <IMG alt="x\leq y" src="latex81.png"> is entailed resp. disentailed by the store. For this, the propagator has to perform a constraint propagation such that the propagation results are only locally visible inside the propagator and not written to the store. This is called <EM>encapsulated constraint propagation</EM>. Additionally, the reified propagator checks if the constraints produced by encapsulated propagation, so-called <EM>encapsulated constraints</EM>, are subsumed by the constraint store. If so the control variable is constrained to 1. If the encapsulated constraints are inconsistent, the control variable is constrained to 0. Otherwise the control variable is left untouched. </P></DIV><DIV class="apropos"><P class="margin">The member function <CODE>readEncap</CODE></P><P> Instances of class <CODE>OZ_FDIntVar</CODE> are usually initialised by the member function <CODE>read()</CODE> or the constructor <CODE>OZ_FDIntVar(OZ_Term)</CODE> with the intention to make amplified constraints visible to the store. To obtain an instance of <CODE>OZ_FDIntVar()</CODE> providing encapsulated constraint propagation, the function <CODE>readEncap()</CODE> has to be used instead. Such an instance is used in the same way as in the non-encapsulated case. </P></DIV><P>The code below implements member function <CODE>propagate()</CODE> of class <CODE>ReifiedLessEq</CODE>. It is implemented in such a way that it utilises encapsulated propagation <A href="node8.html#label7"><SUP>1</SUP></A>. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="type">OZ_Return</SPAN> <SPAN class="reference">ReifiedLessEqProp</SPAN>::<SPAN class="functionname">propagate</SPAN>()<BR>{<BR> <SPAN class="type">OZ_FDIntVar</SPAN> <SPAN class="variablename">r</SPAN>(_r);<BR> <BR> <SPAN class="keyword">if</SPAN>(*r == fd_singl) {<BR> r.leave();<BR> <SPAN class="keyword">return</SPAN> replaceBy((r->getSingleElem() == 1) <BR> ? <SPAN class="keyword">new</SPAN> <SPAN class="type">LessEqProp</SPAN>(_x, _y) <BR> : <SPAN class="keyword">new</SPAN> <SPAN class="type">GreaterProp</SPAN>(_x, _y));<BR> }<BR> <BR> <SPAN class="type">OZ_FDIntVar</SPAN> <SPAN class="variablename">x</SPAN>, <SPAN class="variablename">y</SPAN>;<BR> x.readEncap(_x); y.readEncap(_y);<BR> <SPAN class="type">int</SPAN> <SPAN class="variablename">r_val</SPAN> = 0;<BR> <BR> // <SPAN class="comment">entailed by store?<BR></SPAN> <SPAN class="keyword">if</SPAN> (x->getMaxElem() <= y->getMinElem()) {<BR> r_val = 1;<BR> <SPAN class="keyword">goto</SPAN> <SPAN class="reference">quit</SPAN>;<BR> }<BR> <BR> <SPAN class="keyword">if</SPAN> (0 == (*x <= y->getMaxElem())) <SPAN class="keyword">goto</SPAN> <SPAN class="reference">quit</SPAN>;<BR> <SPAN class="keyword">if</SPAN> (0 == (*y >= x->getMinElem())) <SPAN class="keyword">goto</SPAN> <SPAN class="reference">quit</SPAN>;<BR> <BR> r.leave(); x.leave(); y.leave();<BR> <SPAN class="keyword">return</SPAN> OZ_SLEEP;<BR> <BR><SPAN class="reference">quit</SPAN>:<BR> <SPAN class="keyword">if</SPAN>(0 == (*r &= r_val)) {<BR> r.fail(); x.fail(); y.fail();<BR> <SPAN class="keyword">return</SPAN> OZ_FAILED;<BR> }<BR> <BR> r.leave(); x.leave(); y.leave();<BR> <SPAN class="keyword">return</SPAN> OZ_ENTAILED;<BR>}<BR></PRE></BLOCKQUOTE><P> </P><P>The implementation checks first whether the control variable <CODE>r</CODE> denotes a singleton. If so, the reified propagator is replaced by an appropriate propagator depending on the value of <CODE>r</CODE>. </P><P>Otherwise the code proceeds with defining the variables <CODE>x</CODE> and <CODE>y</CODE> as instances of class <CODE>OZ_FDIntVar</CODE>. Initialisation of <CODE>x</CODE> and <CODE>y</CODE> with <CODE>readEncap()</CODE> ensures encapsulated constraint propagation. Next it is checked if <IMG alt="x \leq y" src="latex78.png"> is entailed by the store, which is the case if <IMG alt="\overline{x} \leq \underline{y}" src="latex82.png"> is true <A href="node8.html#label8"><SUP>2</SUP></A>. If so, <CODE>r_val</CODE> is set to 1 and the code branches to label <CODE>quit</CODE>. Then the propagation rules are implemented. They are <IMG alt="x \leq
\overline{y}" src="latex83.png"> and <IMG alt="y \geq \underline{x}" src="latex84.png">. In case an inconsistency is detected, the code branches to label <CODE>quit</CODE> and the value of <CODE>r_val</CODE> is left at 0. Finally, the function <CODE>propagate()</CODE> returns <CODE>OZ_SLEEP</CODE> to the runtime system. </P><P>The code at label <CODE>quit</CODE> constrains <CODE>r</CODE> to the value of <CODE>r_val</CODE> and in case of an inconsistency it returns <CODE>OZ_FAILED</CODE>. Otherwise the propagator is left by returning <CODE>OZ_ENTAILED</CODE>.</P><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node7.html#u_connect"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD></TR></TABLE><HR align="left" width="30%"><DIV class="footnote"><A name="label7">1. </A>Of course, an alternative would have been to reason over the bounds of the domains.</DIV><DIV class="footnote"><A name="label8">2. </A>Note that <IMG alt="\underline{x}" src="latex85.png"> (<IMG alt="\overline{x}" src="latex86.png">) denotes the smallest (largest) integer of the current domain of <IMG alt="x" src="latex4.png"></DIV><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>
|