Generated on Fri Oct 19 11:24:54 2018 for Gecode by doxygen 1.6.3

val.hpp

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