Generated on Wed Mar 19 07:29:57 2008 for Gecode by doxygen 1.5.5

val.icc

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2006
00011  *     Mikael Lagerkvist, 2006
00012  *
00013  *  Last modified:
00014  *     $Date: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
00015  *     $Revision: 6017 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 namespace Gecode { namespace Int { namespace Channel {
00043 
00048   template <class View>
00049   class ValInfo {
00050   public:
00052     View view;
00054     bool a;
00056     static ValInfo<View>* allocate(Space* home, int n);
00058     void init(View x, int n);
00060     void update(Space* home, bool share, ValInfo<View>& vi);
00062     bool doval(void) const;
00064     bool dodom(void) const;
00066     void assigned(void);
00068     void removed(int i);
00070     void done(void);
00071   };
00072 
00073   template <class View>
00074   forceinline ValInfo<View>*
00075   ValInfo<View>::allocate(Space* home, int n) {
00076     return static_cast<ValInfo<View>*>
00077       (home->alloc(n*sizeof(ValInfo<View>)));
00078   }
00079 
00080   template <class View>
00081   forceinline void
00082   ValInfo<View>::init(View x, int) {
00083     view = x; a = false;
00084   }
00085 
00086   template <class View>
00087   forceinline void
00088   ValInfo<View>::update(Space* home, bool share, ValInfo<View>& vi) {
00089     view.update(home,share,vi.view); a = vi.a;
00090   }
00091 
00092   template <class View>
00093   forceinline bool
00094   ValInfo<View>::doval(void) const {
00095     return !a && view.assigned();
00096   }
00097 
00098   template <class View>
00099   forceinline bool
00100   ValInfo<View>::dodom(void) const {
00101     return false;
00102   }
00103 
00104   template <class View>
00105   forceinline void
00106   ValInfo<View>::assigned(void) {
00107     a = true;
00108   }
00109 
00110   template <class View>
00111   forceinline void
00112   ValInfo<View>::removed(int) {}
00113 
00114   template <class View>
00115   forceinline void
00116   ValInfo<View>::done(void) {}
00117 
00118 
00119   // Propagate assigned views for x
00120   template <class View, class Info>
00121   ExecStatus
00122   doprop_val(Space* home, int n, Info* x, Info* y,
00123              int& n_na, ProcessStack& xa, ProcessStack& ya) {
00124     do {
00125       int i = xa.pop();
00126       int j = x[i].view.val();
00127       // Assign the y variable to i (or test if already assigned!)
00128       {
00129         ModEvent me = y[j].view.eq(home,i);
00130         if (me_failed(me))
00131           return ES_FAILED;
00132         // Record that y[j] has been assigned and must be propagated
00133         if (me_modified(me))
00134           ya.push(j);
00135       }
00136       // Prune the value j from all x variables
00137       for (int k=i; k--; ) {
00138         ModEvent me = x[k].view.nq(home,j);
00139         if (me_failed(me))
00140           return ES_FAILED;
00141         if (me_modified(me))
00142           if (me == ME_INT_VAL) {
00143             // Record that x[k] has been assigned and must be propagated
00144             xa.push(k);
00145           } else {
00146             // One value has been removed and this removal does not need
00147             // to be propagated again: after all y[j] = i, so it holds
00148             // that y[j] != k.
00149             x[k].removed(j);
00150           }
00151       }
00152       // The same for the other views
00153       for (int k=i+1; k<n; k++) {
00154         ModEvent me = x[k].view.nq(home,j);
00155         if (me_failed(me))
00156           return ES_FAILED;
00157         if (me_modified(me))
00158           if (me == ME_INT_VAL) {
00159             // Record that x[k] has been assigned and must be propagated
00160             xa.push(k);
00161           } else {
00162             // One value has been removed and this removal does not need
00163             // to be propagated again: after all y[j] = i, so it holds
00164             // that y[j] != k.
00165             x[k].removed(j);
00166           }
00167       }
00168       x[i].assigned(); n_na--;
00169     } while (!xa.empty());
00170     return ES_OK;
00171   }
00172 
00173   // Just do a test whether a call to the routine is necessary
00174   template <class View, class Info>
00175   forceinline ExecStatus
00176   prop_val(Space* home, int n, Info* x, Info* y,
00177            int& n_na, ProcessStack& xa, ProcessStack& ya) {
00178     if (xa.empty())
00179       return ES_OK;
00180     return doprop_val<View,Info>(home,n,x,y,n_na,xa,ya);
00181   }
00182 
00183   /*
00184    * The actual propagator
00185    *
00186    */
00187   template <class View, bool shared>
00188   forceinline
00189   Val<View,shared>::Val(Space* home, int n, ValInfo<View>* xy)
00190     : Base<ValInfo<View>,PC_INT_VAL>(home,n,xy) {}
00191 
00192   template <class View, bool shared>
00193   forceinline
00194   Val<View,shared>::Val(Space* home, bool share, Val<View,shared>& p)
00195     : Base<ValInfo<View>,PC_INT_VAL>(home,share,p) {}
00196 
00197   template <class View, bool shared>
00198   Actor*
00199   Val<View,shared>::copy(Space* home, bool share) {
00200     return new (home) Val<View,shared>(home,share,*this);
00201   }
00202 
00203   template <class View, bool shared>
00204   ExecStatus
00205   Val<View,shared>::propagate(Space* home, ModEventDelta) {
00206     GECODE_AUTOSTACK(int,-1, xa, n);
00207     GECODE_AUTOSTACK(int,-1, ya, n);
00208 
00209     ValInfo<View>* x = xy;
00210     ValInfo<View>* y = xy+n;
00211 
00212     // Scan x and y for assigned but not yet propagated views
00213     for (int i = n; i--; ) {
00214       if (x[i].doval()) xa.push(i);
00215       if (y[i].doval()) ya.push(i);
00216     }
00217 
00218     do {
00219       // Propagate assigned views for x
00220       GECODE_ES_CHECK((prop_val<View,ValInfo<View> >(home,n,x,y,n_na,xa,ya)));
00221       // Propagate assigned views for y
00222       GECODE_ES_CHECK((prop_val<View,ValInfo<View> >(home,n,y,x,n_na,ya,xa)));
00223       assert(ya.empty());
00224     } while (!xa.empty());
00225 
00226     if (n_na == 0) 
00227       return ES_SUBSUMED(this,home);
00228     return shared ? ES_NOFIX : ES_FIX;
00229   }
00230 
00231   template <class View, bool shared>
00232   Support::Symbol
00233   Val<View,shared>::ati(void) {
00234     return Reflection::mangle<View,shared>("Gecode::Int::Channel::Val");
00235   }
00236 
00237   template <class View, bool shared>
00238   Reflection::ActorSpec
00239   Val<View,shared>::spec(const Space* home, Reflection::VarMap& m) const {
00240     return Base<ValInfo<View>,PC_INT_VAL>::spec(home, m, ati());
00241   }
00242 
00243   template <class View, bool shared>
00244   void
00245   Val<View,shared>::post(Space* home, Reflection::VarMap& vars,
00246                          const Reflection::ActorSpec& spec) {
00247     const int n = spec.noOfArgs();
00248     ValInfo<View>* vi
00249       = ValInfo<View>::allocate(home,n);
00250     for (int i=0; i<n; i++) {
00251       vi[i].init(View(home, vars, spec[i]),n/2);
00252     }
00253     (void) new (home) Val<View,shared>(home,n/2,vi);
00254   }
00255 
00256   template <class View, bool shared>
00257   ExecStatus
00258   Val<View,shared>::post(Space* home, int n, ValInfo<View>* xy) {
00259     assert(n > 0);
00260     if (n == 1) {
00261       GECODE_ME_CHECK(xy[0].view.eq(home,0));
00262       GECODE_ME_CHECK(xy[1].view.eq(home,0));
00263       return ES_OK;
00264     }
00265     for (int i=2*n; i--; ) {
00266       GECODE_ME_CHECK(xy[i].view.gq(home,0));
00267       GECODE_ME_CHECK(xy[i].view.le(home,n));
00268     }
00269     (void) new (home) Val<View,shared>(home,n,xy);
00270     return ES_OK;
00271   }
00272 
00273 }}}
00274 
00275 // STATISTICS: int-prop
00276