Generated on Wed Jan 4 17:49:10 2006 for Gecode by doxygen 1.4.6

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: 2005-08-03 11:41:13 +0200 (Wed, 03 Aug 2005) $ by $Author: schulte $
00010  *     $Revision: 2121 $
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   LinBool<View>::~LinBool(void) {
00037     x.cancel(this,PC_INT_VAL);
00038     y.cancel(this,PC_INT_BND);
00039   }
00040 
00041   template <class View>
00042   forceinline
00043   LinBool<View>::LinBool(Space* home, bool share, LinBool& p)
00044     : Propagator(home,share,p), n(p.n) {
00045     x.update(home,share,p.x);
00046     y.update(home,share,p.y);
00047   }
00048 
00049   template <class View>
00050   PropCost
00051   LinBool<View>::cost(void) const {
00052     return cost_lo(x.size(),PC_LINEAR_LO);
00053   }
00054 
00055   template <class View>
00056   void
00057   LinBool<View>::eliminate(void) {
00058     int e = 0;
00059     int m = x.size();
00060     for (int i = m; i--; )
00061       if (x[i].assigned()) {
00062         e+=x[i].val(); x[i]=x[--m];
00063       }
00064     x.size(m);
00065     n -= e;
00066   }
00067 
00068   template <class View>
00069   void
00070   LinBool<View>::all_one(Space* home) {
00071     for (int i = x.size(); i--; )
00072       x[i].t_one_none(home);
00073   }
00074 
00075   template <class View>
00076   void
00077   LinBool<View>::all_zero(Space* home) {
00078     for (int i = x.size(); i--; )
00079       x[i].t_zero_none(home);
00080   }
00081 
00082 
00083   /*
00084    * Equality propagator
00085    *
00086    */
00087   template <class View>
00088   forceinline
00089   EqBool<View>::EqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00090     : LinBool<View>(home,x,n,y) {}
00091 
00092   template <class View>
00093   ExecStatus
00094   EqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00095     (void) new (home) EqBool<View>(home,x,n,y);
00096     return ES_OK;
00097   }
00098 
00099   template <class View>
00100   forceinline
00101   EqBool<View>::EqBool(Space* home, bool share, EqBool<View>& p)
00102     : LinBool<View>(home,share,p) {}
00103 
00104   template <class View>
00105   Actor*
00106   EqBool<View>::copy(Space* home, bool share) {
00107     return new (home) EqBool<View>(home,share,*this);
00108   }
00109 
00110   template <class View>
00111   ExecStatus
00112   EqBool<View>::propagate(Space* home) {
00113     this->eliminate();
00114     GECODE_ME_CHECK(y.lq(home,x.size() - n));
00115     GECODE_ME_CHECK(y.gq(home,-n));
00116     if (x.size() == 0)
00117       return ES_SUBSUMED;
00118     if (y.min()+n == x.size()) {
00119       assert(y.assigned());
00120       this->all_one(home); return ES_SUBSUMED;
00121     }
00122     if (y.max()+n == 0) {
00123       assert(y.assigned());
00124       this->all_zero(home); return ES_SUBSUMED;
00125     }
00126     return ES_FIX;
00127   }
00128 
00129 
00130   /*
00131    * Disequality propagator
00132    *
00133    */
00134   template <class View>
00135   forceinline
00136   NqBool<View>::NqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00137     : LinBool<View>(home,x,n,y) {}
00138 
00139   template <class View>
00140   ExecStatus
00141   NqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00142     (void) new (home) NqBool<View>(home,x,n,y);
00143     return ES_OK;
00144   }
00145 
00146 
00147   template <class View>
00148   forceinline
00149   NqBool<View>::NqBool(Space* home, bool share, NqBool<View>& p)
00150     : LinBool<View>(home,share,p) {}
00151 
00152   template <class View>
00153   Actor*
00154   NqBool<View>::copy(Space* home, bool share) {
00155     return new (home) NqBool<View>(home,share,*this);
00156   }
00157 
00158 
00159   template <class View>
00160   ExecStatus
00161   NqBool<View>::propagate(Space* home) {
00162     this->eliminate();
00163     if ((x.size()-n < y.min() ) || (-n > y.max()))
00164       return ES_SUBSUMED;
00165     if (x.size() == 0) {
00166       GECODE_ME_CHECK(y.nq(home,-n));
00167       return ES_SUBSUMED;
00168     }
00169     if ((x.size() == 1) && y.assigned()) {
00170       if (y.val()+n == 1) {
00171         x[0].t_zero_none(home);
00172       } else {
00173         assert(y.val()+n == 0);
00174         x[0].t_one_none(home);
00175       }
00176       return ES_SUBSUMED;
00177     }
00178     return ES_FIX;
00179   }
00180 
00181 
00182 
00183   /*
00184    * Less or equal propagator
00185    *
00186    */
00187 
00188   template <class View>
00189   forceinline
00190   LqBool<View>::LqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00191     : LinBool<View>(home,x,n,y) {}
00192 
00193   template <class View>
00194   ExecStatus
00195   LqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00196     (void) new (home) LqBool<View>(home,x,n,y);
00197     return ES_OK;
00198   }
00199 
00200 
00201   template <class View>
00202   forceinline
00203   LqBool<View>::LqBool(Space* home, bool share, LqBool<View>& p)
00204     : LinBool<View>(home,share,p) {}
00205 
00206   template <class View>
00207   Actor*
00208   LqBool<View>::copy(Space* home, bool share) {
00209     return new (home) LqBool<View>(home,share,*this);
00210   }
00211 
00212 
00213   template <class View>
00214   ExecStatus
00215   LqBool<View>::propagate(Space* home) {
00216     this->eliminate();
00217     GECODE_ME_CHECK(y.gq(home,-n));
00218     if (x.size() <= y.min()+n)
00219       return ES_SUBSUMED;
00220     if (y.max()+n == 0) {
00221       this->all_zero(home); return ES_SUBSUMED;
00222     }
00223     return ES_FIX;
00224   }
00225 
00226 
00227 
00228   /*
00229    * Greater or equal propagator
00230    *
00231    */
00232   template <class View>
00233   forceinline
00234   GqBool<View>::GqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00235     : LinBool<View>(home,x,n,y) {}
00236 
00237   template <class View>
00238   ExecStatus
00239   GqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00240     (void) new (home) GqBool<View>(home,x,n,y);
00241     return ES_OK;
00242   }
00243 
00244 
00245   template <class View>
00246   forceinline
00247   GqBool<View>::GqBool(Space* home, bool share, GqBool<View>& p)
00248     : LinBool<View>(home,share,p) {}
00249 
00250   template <class View>
00251   Actor*
00252   GqBool<View>::copy(Space* home, bool share) {
00253     return new (home) GqBool<View>(home,share,*this);
00254   }
00255 
00256 
00257   template <class View>
00258   ExecStatus
00259   GqBool<View>::propagate(Space* home) {
00260     this->eliminate();
00261     GECODE_ME_CHECK(y.lq(home,x.size() - n));
00262     if (-n >= y.max())
00263       return ES_SUBSUMED;
00264     if (y.min()+n == x.size()) {
00265       this->all_one(home); return ES_SUBSUMED;
00266     }
00267     return ES_FIX;
00268   }
00269 
00270 }}}
00271 
00272 // STATISTICS: int-prop
00273