bool-view.icc

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
00011  *     $Revision: 6017 $
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 Linear {
00039 
00040   /*
00041    * Base-class
00042    *
00043    */
00044   template <class XV, class YV>
00045   LinBoolView<XV,YV>::LinBoolView(Space* home,
00046                                   ViewArray<XV>& x0, YV y0, int c0)
00047     :  Propagator(home), x(x0), y(y0), c(c0) {
00048     x.subscribe(home,this,PC_INT_VAL);
00049     y.subscribe(home,this,PC_INT_BND);
00050   }
00051 
00052   template <class XV, class YV>
00053   forceinline size_t
00054   LinBoolView<XV,YV>::dispose(Space* home) {
00055     assert(!home->failed());
00056     x.cancel(home,this,PC_INT_VAL);
00057     y.cancel(home,this,PC_INT_BND);
00058     (void) Propagator::dispose(home);
00059     return sizeof(*this);
00060   }
00061 
00062   template <class XV, class YV>
00063   forceinline
00064   LinBoolView<XV,YV>::LinBoolView(Space* home, bool share, LinBoolView& p)
00065     : Propagator(home,share,p), c(p.c) {
00066     x.update(home,share,p.x);
00067     y.update(home,share,p.y);
00068   }
00069 
00070   template <class XV, class YV>
00071   PropCost
00072   LinBoolView<XV,YV>::cost(ModEventDelta) const {
00073     return cost_lo(x.size(),PC_LINEAR_LO);
00074   }
00075 
00076   template <class XV, class YV>
00077   Reflection::ActorSpec
00078   LinBoolView<XV,YV>::spec(const Space* home, Reflection::VarMap& m,
00079                            const Support::Symbol& ati) const {
00080     Reflection::ActorSpec s(ati);
00081     return s << x.spec(home, m)
00082              << y.spec(home, m)
00083              << c;
00084   }
00085 
00086 
00087   /*
00088    * Equality propagator
00089    *
00090    */
00091   template <class XV, class YV>
00092   forceinline
00093   EqBoolView<XV,YV>::EqBoolView(Space* home, ViewArray<XV>& x, YV y, int c)
00094     : LinBoolView<XV,YV>(home,x,y,c) {}
00095 
00096   template <class XV, class YV>
00097   ExecStatus
00098   EqBoolView<XV,YV>::post(Space* home, ViewArray<XV>& x, YV y, int c) {
00099     if (y.assigned())
00100       return EqBoolInt<XV>::post(home,x,y.val()+c);
00101     int n = x.size();
00102     for (int i = n; i--; )
00103       if (x[i].one()) {
00104         x[i]=x[--n]; c--;
00105       } else if (x[i].zero()) {
00106         x[i]=x[--n];
00107       }
00108     x.size(n);
00109     GECODE_ME_CHECK(y.lq(home,n-c));
00110     GECODE_ME_CHECK(y.gq(home,-c));
00111     if (n == 0)
00112       return ES_OK;
00113     if (y.min()+c == n) {
00114       assert(y.assigned());
00115       for (int i = n; i--; )
00116         GECODE_ME_CHECK(x[i].one_none(home));
00117       return ES_OK;
00118     }
00119     if (y.max()+c == 0) {
00120       assert(y.assigned());
00121       for (int i = n; i--; )
00122         GECODE_ME_CHECK(x[i].zero_none(home));
00123       return ES_OK;
00124     }
00125     (void) new (home) EqBoolView<XV,YV>(home,x,y,c);
00126     return ES_OK;
00127   }
00128 
00129   template <class XV, class YV>
00130   forceinline
00131   EqBoolView<XV,YV>::EqBoolView(Space* home, bool share, EqBoolView<XV,YV>& p)
00132     : LinBoolView<XV,YV>(home,share,p) {}
00133 
00134   template <class XV, class YV>
00135   Actor*
00136   EqBoolView<XV,YV>::copy(Space* home, bool share) {
00137     return new (home) EqBoolView<XV,YV>(home,share,*this);
00138   }
00139 
00140   template <class XV, class YV>
00141   inline Support::Symbol
00142   EqBoolView<XV,YV>::ati(void) {
00143     return Reflection::mangle<XV,YV>("Gecode::Int::Linear::EqBoolView");
00144   }
00145 
00146   template <class XV, class YV>
00147   Reflection::ActorSpec
00148   EqBoolView<XV,YV>::spec(const Space* home, Reflection::VarMap& m) const {
00149     return LinBoolView<XV,YV>::spec(home, m, ati());
00150   }
00151 
00152   template <class XV, class YV>
00153   void
00154   EqBoolView<XV,YV>::post(Space* home, Reflection::VarMap& vars,
00155                           const Reflection::ActorSpec& spec) {
00156     spec.checkArity(3);
00157     ViewArray<XV> x(home, vars, spec[0]);
00158     YV y(home, vars, spec[1]);
00159     int c = spec[2]->toInt();
00160     (void) new (home) EqBoolView<XV,YV>(home, x, y, c);
00161   }
00162     
00163   template <class XV, class YV>
00164   ExecStatus
00165   EqBoolView<XV,YV>::propagate(Space* home, ModEventDelta) {
00166     int n = x.size();
00167     for (int i = n; i--; )
00168       if (x[i].one()) {
00169         x[i]=x[--n]; c--;
00170       } else if (x[i].zero()) {
00171         x[i]=x[--n];
00172       }
00173     x.size(n);
00174     GECODE_ME_CHECK(y.lq(home,n-c));
00175     GECODE_ME_CHECK(y.gq(home,-c));
00176     if (n == 0)
00177       return ES_SUBSUMED(this,sizeof(*this));
00178     if (y.min()+c == n) {
00179       assert(y.assigned());
00180       for (int i = n; i--; )
00181         GECODE_ME_CHECK(x[i].one_none(home));
00182       return ES_SUBSUMED(this,sizeof(*this));
00183     }
00184     if (y.max()+c == 0) {
00185       assert(y.assigned());
00186       for (int i = n; i--; )
00187         GECODE_ME_CHECK(x[i].zero_none(home));
00188       return ES_SUBSUMED(this,sizeof(*this));
00189     }
00190     if (y.assigned())
00191       GECODE_REWRITE(this,EqBoolInt<XV>::post(home,x,y.val()+c));
00192     return ES_FIX;
00193   }
00194 
00195 
00196   /*
00197    * Disequality propagator
00198    *
00199    */
00200   template <class XV, class YV>
00201   forceinline
00202   NqBoolView<XV,YV>::NqBoolView(Space* home, ViewArray<XV>& x, YV y, int c)
00203     : LinBoolView<XV,YV>(home,x,y,c) {}
00204 
00205   template <class XV, class YV>
00206   ExecStatus
00207   NqBoolView<XV,YV>::post(Space* home, ViewArray<XV>& x, YV y, int c) {
00208     if (y.assigned())
00209       return NqBoolInt<XV>::post(home,x,y.val()+c);
00210     int n = x.size();
00211     for (int i = n; i--; )
00212       if (x[i].one()) {
00213         x[i]=x[--n]; c--;
00214       } else if (x[i].zero()) {
00215         x[i]=x[--n];
00216       }
00217     x.size(n);
00218     if ((n-c < y.min() ) || (-c > y.max()))
00219       return ES_OK;
00220     if (n == 0) {
00221       GECODE_ME_CHECK(y.nq(home,-c));
00222       return ES_OK;
00223     }
00224     if ((n == 1) && y.assigned()) {
00225       if (y.val()+c == 1) {
00226         GECODE_ME_CHECK(x[0].zero_none(home));
00227       } else {
00228         assert(y.val()+c == 0);
00229         GECODE_ME_CHECK(x[0].one_none(home));
00230       }
00231       return ES_OK;
00232     }
00233     (void) new (home) NqBoolView<XV,YV>(home,x,y,c);
00234     return ES_OK;
00235   }
00236 
00237 
00238   template <class XV, class YV>
00239   forceinline
00240   NqBoolView<XV,YV>::NqBoolView(Space* home, bool share, NqBoolView<XV,YV>& p)
00241     : LinBoolView<XV,YV>(home,share,p) {}
00242 
00243   template <class XV, class YV>
00244   Actor*
00245   NqBoolView<XV,YV>::copy(Space* home, bool share) {
00246     return new (home) NqBoolView<XV,YV>(home,share,*this);
00247   }
00248 
00249   template <class XV, class YV>
00250   inline Support::Symbol
00251   NqBoolView<XV,YV>::ati(void) {
00252     return Reflection::mangle<XV,YV>("Gecode::Int::Linear::NqBoolView");
00253   }
00254 
00255   template <class XV, class YV>
00256   Reflection::ActorSpec
00257   NqBoolView<XV,YV>::spec(const Space* home, Reflection::VarMap& m) const {
00258     return LinBoolView<XV,YV>::spec(home, m, ati());
00259   }
00260 
00261   template <class XV, class YV>
00262   void
00263   NqBoolView<XV,YV>::post(Space* home, Reflection::VarMap& vars,
00264                           const Reflection::ActorSpec& spec) {
00265     spec.checkArity(3);
00266     ViewArray<XV> x(home, vars, spec[0]);
00267     YV y(home, vars, spec[1]);
00268     int c = spec[2]->toInt();
00269     (void) new (home) NqBoolView<XV,YV>(home, x, y, c);
00270   }
00271 
00272   template <class XV, class YV>
00273   ExecStatus
00274   NqBoolView<XV,YV>::propagate(Space* home, ModEventDelta) {
00275     int n = x.size();
00276     for (int i = n; i--; )
00277       if (x[i].one()) {
00278         x[i]=x[--n]; c--;
00279       } else if (x[i].zero()) {
00280         x[i]=x[--n];
00281       }
00282     x.size(n);
00283     if ((n-c < y.min() ) || (-c > y.max()))
00284       return ES_SUBSUMED(this,home);
00285     if (n == 0) {
00286       GECODE_ME_CHECK(y.nq(home,-c));
00287       return ES_SUBSUMED(this,home);
00288     }
00289     if ((n == 1) && y.assigned()) {
00290       if (y.val()+c == 1) {
00291         GECODE_ME_CHECK(x[0].zero_none(home));
00292       } else {
00293         assert(y.val()+c == 0);
00294         GECODE_ME_CHECK(x[0].one_none(home));
00295       }
00296       return ES_SUBSUMED(this,sizeof(*this));
00297     }
00298     return ES_FIX;
00299   }
00300 
00301 
00302   /*
00303    * Greater or equal propagator
00304    *
00305    */
00306   template <class XV, class YV>
00307   forceinline
00308   GqBoolView<XV,YV>::GqBoolView(Space* home, ViewArray<XV>& x, YV y, int c)
00309     : LinBoolView<XV,YV>(home,x,y,c) {}
00310 
00311   template <class XV, class YV>
00312   ExecStatus
00313   GqBoolView<XV,YV>::post(Space* home, ViewArray<XV>& x, YV y, int c) {
00314     if (y.assigned())
00315       return GqBoolInt<XV>::post(home,x,y.val()+c);
00316     // Eliminate assigned views
00317     int n = x.size();
00318     for (int i = n; i--; )
00319       if (x[i].one()) {
00320         x[i]=x[--n]; c--;
00321       } else if (x[i].zero()) {
00322         x[i]=x[--n];
00323       }
00324     x.size(n);
00325     GECODE_ME_CHECK(y.lq(home,n-c));
00326     if (-c >= y.max())
00327       return ES_OK;
00328     if (y.min()+c == n) {
00329       for (int i = n; i--; )
00330         GECODE_ME_CHECK(x[i].one_none(home));
00331       return ES_OK;
00332     }
00333     (void) new (home) GqBoolView<XV,YV>(home,x,y,c);
00334     return ES_OK;
00335   }
00336 
00337 
00338   template <class XV, class YV>
00339   forceinline
00340   GqBoolView<XV,YV>::GqBoolView(Space* home, bool share, GqBoolView<XV,YV>& p)
00341     : LinBoolView<XV,YV>(home,share,p) {}
00342 
00343   template <class XV, class YV>
00344   Actor*
00345   GqBoolView<XV,YV>::copy(Space* home, bool share) {
00346     return new (home) GqBoolView<XV,YV>(home,share,*this);
00347   }
00348 
00349   template <class XV, class YV>
00350   inline Support::Symbol
00351   GqBoolView<XV,YV>::ati(void) {
00352     return Reflection::mangle<XV,YV>("Gecode::Int::Linear::GqBoolView");
00353   }
00354 
00355   template <class XV, class YV>
00356   Reflection::ActorSpec
00357   GqBoolView<XV,YV>::spec(const Space* home, Reflection::VarMap& m) const {
00358     return LinBoolView<XV,YV>::spec(home, m, ati());
00359   }
00360 
00361   template <class XV, class YV>
00362   void
00363   GqBoolView<XV,YV>::post(Space* home, Reflection::VarMap& vars,
00364                           const Reflection::ActorSpec& spec) {
00365     spec.checkArity(3);
00366     ViewArray<XV> x(home, vars, spec[0]);
00367     YV y(home, vars, spec[1]);
00368     int c = spec[2]->toInt();
00369     (void) new (home) GqBoolView<XV,YV>(home, x, y, c);
00370   }
00371 
00372   template <class XV, class YV>
00373   ExecStatus
00374   GqBoolView<XV,YV>::propagate(Space* home, ModEventDelta) {
00375     int n = x.size();
00376     for (int i = n; i--; )
00377       if (x[i].one()) {
00378         x[i]=x[--n]; c--;
00379       } else if (x[i].zero()) {
00380         x[i]=x[--n];
00381       }
00382     x.size(n);
00383     GECODE_ME_CHECK(y.lq(home,n-c));
00384     if (-c >= y.max())
00385       return ES_SUBSUMED(this,home);
00386     if (y.min()+c == n) {
00387       for (int i = n; i--; )
00388         GECODE_ME_CHECK(x[i].one_none(home));
00389       return ES_SUBSUMED(this,home);
00390     }
00391     if (y.assigned())
00392       GECODE_REWRITE(this,GqBoolInt<XV>::post(home,x,y.val()+c));
00393     return ES_FIX;
00394   }
00395 
00396 }}}
00397 
00398 // STATISTICS: int-prop
00399