Generated on Thu Jul 6 07:06:45 2006 for Gecode by doxygen 1.4.7

bool.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-06-20 07:40:00 +0200 (Tue, 20 Jun 2006) $ by $Author: schulte $
00010  *     $Revision: 3309 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Int { namespace Linear {
00023 
00024   /*
00025    * Base-class
00026    *
00027    */
00028   template <class View>
00029   LinBool<View>::LinBool(Space* home, ViewArray<BoolView>& x0, int n0, View y0)
00030     :  Propagator(home), x(x0), n(n0), y(y0) {
00031     x.subscribe(home,this,PC_INT_VAL);
00032     y.subscribe(home,this,PC_INT_BND);
00033   }
00034 
00035   template <class View>
00036   size_t
00037   LinBool<View>::dispose(Space* home) {
00038     assert(!home->failed());
00039     x.cancel(home,this,PC_INT_VAL);
00040     y.cancel(home,this,PC_INT_BND);
00041     (void) Propagator::dispose(home);
00042     return sizeof(*this);
00043   }
00044 
00045   template <class View>
00046   forceinline
00047   LinBool<View>::LinBool(Space* home, bool share, LinBool& p)
00048     : Propagator(home,share,p), n(p.n) {
00049     x.update(home,share,p.x);
00050     y.update(home,share,p.y);
00051   }
00052 
00053   template <class View>
00054   PropCost
00055   LinBool<View>::cost(void) const {
00056     return cost_lo(x.size(),PC_LINEAR_LO);
00057   }
00058 
00059   template <class View>
00060   void
00061   LinBool<View>::eliminate(void) {
00062     int e = 0;
00063     int m = x.size();
00064     for (int i = m; i--; )
00065       if (x[i].assigned()) {
00066         e+=x[i].val(); x[i]=x[--m];
00067       }
00068     x.size(m);
00069     n -= e;
00070   }
00071 
00072   template <class View>
00073   void
00074   LinBool<View>::all_one(Space* home) {
00075     for (int i = x.size(); i--; )
00076       x[i].t_one_none(home);
00077   }
00078 
00079   template <class View>
00080   void
00081   LinBool<View>::all_zero(Space* home) {
00082     for (int i = x.size(); i--; )
00083       x[i].t_zero_none(home);
00084   }
00085 
00086 
00087   /*
00088    * Equality propagator
00089    *
00090    */
00091   template <class View>
00092   forceinline
00093   EqBool<View>::EqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00094     : LinBool<View>(home,x,n,y) {}
00095 
00096   template <class View>
00097   ExecStatus
00098   EqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00099     (void) new (home) EqBool<View>(home,x,n,y);
00100     return ES_OK;
00101   }
00102 
00103   template <class View>
00104   forceinline
00105   EqBool<View>::EqBool(Space* home, bool share, EqBool<View>& p)
00106     : LinBool<View>(home,share,p) {}
00107 
00108   template <class View>
00109   Actor*
00110   EqBool<View>::copy(Space* home, bool share) {
00111     return new (home) EqBool<View>(home,share,*this);
00112   }
00113 
00114   template <class View>
00115   ExecStatus
00116   EqBool<View>::propagate(Space* home) {
00117     this->eliminate();
00118     GECODE_ME_CHECK(y.lq(home,x.size() - n));
00119     GECODE_ME_CHECK(y.gq(home,-n));
00120     if (x.size() == 0)
00121       return ES_SUBSUMED;
00122     if (y.min()+n == x.size()) {
00123       assert(y.assigned());
00124       this->all_one(home); return ES_SUBSUMED;
00125     }
00126     if (y.max()+n == 0) {
00127       assert(y.assigned());
00128       this->all_zero(home); return ES_SUBSUMED;
00129     }
00130     return ES_FIX;
00131   }
00132 
00133 
00134   /*
00135    * Disequality propagator
00136    *
00137    */
00138   template <class View>
00139   forceinline
00140   NqBool<View>::NqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00141     : LinBool<View>(home,x,n,y) {}
00142 
00143   template <class View>
00144   ExecStatus
00145   NqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00146     (void) new (home) NqBool<View>(home,x,n,y);
00147     return ES_OK;
00148   }
00149 
00150 
00151   template <class View>
00152   forceinline
00153   NqBool<View>::NqBool(Space* home, bool share, NqBool<View>& p)
00154     : LinBool<View>(home,share,p) {}
00155 
00156   template <class View>
00157   Actor*
00158   NqBool<View>::copy(Space* home, bool share) {
00159     return new (home) NqBool<View>(home,share,*this);
00160   }
00161 
00162 
00163   template <class View>
00164   ExecStatus
00165   NqBool<View>::propagate(Space* home) {
00166     this->eliminate();
00167     if ((x.size()-n < y.min() ) || (-n > y.max()))
00168       return ES_SUBSUMED;
00169     if (x.size() == 0) {
00170       GECODE_ME_CHECK(y.nq(home,-n));
00171       return ES_SUBSUMED;
00172     }
00173     if ((x.size() == 1) && y.assigned()) {
00174       if (y.val()+n == 1) {
00175         x[0].t_zero_none(home);
00176       } else {
00177         assert(y.val()+n == 0);
00178         x[0].t_one_none(home);
00179       }
00180       return ES_SUBSUMED;
00181     }
00182     return ES_FIX;
00183   }
00184 
00185 
00186 
00187   /*
00188    * Less or equal propagator
00189    *
00190    */
00191 
00192   template <class View>
00193   forceinline
00194   LqBool<View>::LqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00195     : LinBool<View>(home,x,n,y) {}
00196 
00197   template <class View>
00198   ExecStatus
00199   LqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00200     (void) new (home) LqBool<View>(home,x,n,y);
00201     return ES_OK;
00202   }
00203 
00204 
00205   template <class View>
00206   forceinline
00207   LqBool<View>::LqBool(Space* home, bool share, LqBool<View>& p)
00208     : LinBool<View>(home,share,p) {}
00209 
00210   template <class View>
00211   Actor*
00212   LqBool<View>::copy(Space* home, bool share) {
00213     return new (home) LqBool<View>(home,share,*this);
00214   }
00215 
00216 
00217   template <class View>
00218   ExecStatus
00219   LqBool<View>::propagate(Space* home) {
00220     this->eliminate();
00221     GECODE_ME_CHECK(y.gq(home,-n));
00222     if (x.size() <= y.min()+n)
00223       return ES_SUBSUMED;
00224     if (y.max()+n == 0) {
00225       this->all_zero(home); return ES_SUBSUMED;
00226     }
00227     return ES_FIX;
00228   }
00229 
00230 
00231 
00232   /*
00233    * Greater or equal propagator
00234    *
00235    */
00236   template <class View>
00237   forceinline
00238   GqBool<View>::GqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00239     : LinBool<View>(home,x,n,y) {}
00240 
00241   template <class View>
00242   ExecStatus
00243   GqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00244     (void) new (home) GqBool<View>(home,x,n,y);
00245     return ES_OK;
00246   }
00247 
00248 
00249   template <class View>
00250   forceinline
00251   GqBool<View>::GqBool(Space* home, bool share, GqBool<View>& p)
00252     : LinBool<View>(home,share,p) {}
00253 
00254   template <class View>
00255   Actor*
00256   GqBool<View>::copy(Space* home, bool share) {
00257     return new (home) GqBool<View>(home,share,*this);
00258   }
00259 
00260 
00261   template <class View>
00262   ExecStatus
00263   GqBool<View>::propagate(Space* home) {
00264     this->eliminate();
00265     GECODE_ME_CHECK(y.lq(home,x.size() - n));
00266     if (-n >= y.max())
00267       return ES_SUBSUMED;
00268     if (y.min()+n == x.size()) {
00269       this->all_one(home); return ES_SUBSUMED;
00270     }
00271     return ES_FIX;
00272   }
00273 
00274 }}}
00275 
00276 // STATISTICS: int-prop
00277