bool-view.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-09-07 11:03:52 +0200 (Thu, 07 Sep 2006) $ by $Author: schulte $
00010  *     $Revision: 3609 $
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 XV, class YV>
00029   LinBoolView<XV,YV>::LinBoolView(Space* home,
00030                                   ViewArray<XV>& x0, YV y0, int c0)
00031     :  Propagator(home), x(x0), y(y0), c(c0) {
00032     x.subscribe(home,this,PC_INT_VAL);
00033     y.subscribe(home,this,PC_INT_BND);
00034   }
00035 
00036   template <class XV, class YV>
00037   size_t
00038   LinBoolView<XV,YV>::dispose(Space* home) {
00039     assert(!home->failed());
00040     x.cancel(home,this,PC_INT_VAL);
00041     y.cancel(home,this,PC_INT_BND);
00042     (void) Propagator::dispose(home);
00043     return sizeof(*this);
00044   }
00045 
00046   template <class XV, class YV>
00047   forceinline
00048   LinBoolView<XV,YV>::LinBoolView(Space* home, bool share, LinBoolView& p)
00049     : Propagator(home,share,p), c(p.c) {
00050     x.update(home,share,p.x);
00051     y.update(home,share,p.y);
00052   }
00053 
00054   template <class XV, class YV>
00055   PropCost
00056   LinBoolView<XV,YV>::cost(void) const {
00057     return cost_lo(x.size(),PC_LINEAR_LO);
00058   }
00059 
00060 
00061 
00062   /*
00063    * Equality propagator
00064    *
00065    */
00066   template <class XV, class YV>
00067   forceinline
00068   EqBoolView<XV,YV>::EqBoolView(Space* home, ViewArray<XV>& x, YV y, int c)
00069     : LinBoolView<XV,YV>(home,x,y,c) {}
00070 
00071   template <class XV, class YV>
00072   ExecStatus
00073   EqBoolView<XV,YV>::post(Space* home, ViewArray<XV>& x, YV y, int c) {
00074     if (y.assigned())
00075       return EqBoolInt<XV>::post(home,x,y.val()+c);
00076     int n = x.size();
00077     for (int i = n; i--; )
00078       if (x[i].one()) {
00079         x[i]=x[--n]; c--;
00080       } else if (x[i].zero()) {
00081         x[i]=x[--n];
00082       }
00083     x.size(n);
00084     GECODE_ME_CHECK(y.lq(home,n-c));
00085     GECODE_ME_CHECK(y.gq(home,-c));
00086     if (n == 0)
00087       return ES_OK;
00088     if (y.min()+c == n) {
00089       assert(y.assigned());
00090       for (int i = n; i--; )
00091         x[i].t_one_none(home);
00092       return ES_OK;
00093     }
00094     if (y.max()+c == 0) {
00095       assert(y.assigned());
00096       for (int i = n; i--; )
00097         x[i].t_zero_none(home);
00098       return ES_OK;
00099     }
00100     (void) new (home) EqBoolView<XV,YV>(home,x,y,c);
00101     return ES_OK;
00102   }
00103 
00104   template <class XV, class YV>
00105   forceinline
00106   EqBoolView<XV,YV>::EqBoolView(Space* home, bool share, EqBoolView<XV,YV>& p)
00107     : LinBoolView<XV,YV>(home,share,p) {}
00108 
00109   template <class XV, class YV>
00110   Actor*
00111   EqBoolView<XV,YV>::copy(Space* home, bool share) {
00112     return new (home) EqBoolView<XV,YV>(home,share,*this);
00113   }
00114 
00115   template <class XV, class YV>
00116   ExecStatus
00117   EqBoolView<XV,YV>::propagate(Space* home) {
00118     int n = x.size();
00119     for (int i = n; i--; )
00120       if (x[i].one()) {
00121         x[i]=x[--n]; c--;
00122       } else if (x[i].zero()) {
00123         x[i]=x[--n];
00124       }
00125     x.size(n);
00126     GECODE_ME_CHECK(y.lq(home,n-c));
00127     GECODE_ME_CHECK(y.gq(home,-c));
00128     if (n == 0)
00129       return ES_SUBSUMED;
00130     if (y.min()+c == n) {
00131       assert(y.assigned());
00132       for (int i = n; i--; )
00133         x[i].t_one_none(home);
00134       return ES_SUBSUMED;
00135     }
00136     if (y.max()+c == 0) {
00137       assert(y.assigned());
00138       for (int i = n; i--; )
00139         x[i].t_zero_none(home);
00140       return ES_SUBSUMED;
00141     }
00142     if (y.assigned()) {
00143       GECODE_ES_CHECK(EqBoolInt<XV>::post(home,x,y.val()+c));
00144       return ES_SUBSUMED;
00145     }
00146     return ES_FIX;
00147   }
00148 
00149 
00150   /*
00151    * Disequality propagator
00152    *
00153    */
00154   template <class XV, class YV>
00155   forceinline
00156   NqBoolView<XV,YV>::NqBoolView(Space* home, ViewArray<XV>& x, YV y, int c)
00157     : LinBoolView<XV,YV>(home,x,y,c) {}
00158 
00159   template <class XV, class YV>
00160   ExecStatus
00161   NqBoolView<XV,YV>::post(Space* home, ViewArray<XV>& x, YV y, int c) {
00162     if (y.assigned())
00163       return NqBoolInt<XV>::post(home,x,y.val()+c);
00164     int n = x.size();
00165     for (int i = n; i--; )
00166       if (x[i].one()) {
00167         x[i]=x[--n]; c--;
00168       } else if (x[i].zero()) {
00169         x[i]=x[--n];
00170       }
00171     x.size(n);
00172     if ((n-c < y.min() ) || (-c > y.max()))
00173       return ES_OK;
00174     if (n == 0) {
00175       GECODE_ME_CHECK(y.nq(home,-c));
00176       return ES_OK;
00177     }
00178     if ((n == 1) && y.assigned()) {
00179       if (y.val()+c == 1) {
00180         x[0].t_zero_none(home);
00181       } else {
00182         assert(y.val()+c == 0);
00183         x[0].t_one_none(home);
00184       }
00185       return ES_OK;
00186     }
00187     (void) new (home) NqBoolView<XV,YV>(home,x,y,c);
00188     return ES_OK;
00189   }
00190 
00191 
00192   template <class XV, class YV>
00193   forceinline
00194   NqBoolView<XV,YV>::NqBoolView(Space* home, bool share, NqBoolView<XV,YV>& p)
00195     : LinBoolView<XV,YV>(home,share,p) {}
00196 
00197   template <class XV, class YV>
00198   Actor*
00199   NqBoolView<XV,YV>::copy(Space* home, bool share) {
00200     return new (home) NqBoolView<XV,YV>(home,share,*this);
00201   }
00202 
00203 
00204   template <class XV, class YV>
00205   ExecStatus
00206   NqBoolView<XV,YV>::propagate(Space* home) {
00207     int n = x.size();
00208     for (int i = n; i--; )
00209       if (x[i].one()) {
00210         x[i]=x[--n]; c--;
00211       } else if (x[i].zero()) {
00212         x[i]=x[--n];
00213       }
00214     x.size(n);
00215     if ((n-c < y.min() ) || (-c > y.max()))
00216       return ES_SUBSUMED;
00217     if (n == 0) {
00218       GECODE_ME_CHECK(y.nq(home,-c));
00219       return ES_SUBSUMED;
00220     }
00221     if ((n == 1) && y.assigned()) {
00222       if (y.val()+c == 1) {
00223         x[0].t_zero_none(home);
00224       } else {
00225         assert(y.val()+c == 0);
00226         x[0].t_one_none(home);
00227       }
00228       return ES_SUBSUMED;
00229     }
00230     return ES_FIX;
00231   }
00232 
00233 
00234   /*
00235    * Greater or equal propagator
00236    *
00237    */
00238   template <class XV, class YV>
00239   forceinline
00240   GqBoolView<XV,YV>::GqBoolView(Space* home, ViewArray<XV>& x, YV y, int c)
00241     : LinBoolView<XV,YV>(home,x,y,c) {}
00242 
00243   template <class XV, class YV>
00244   ExecStatus
00245   GqBoolView<XV,YV>::post(Space* home, ViewArray<XV>& x, YV y, int c) {
00246     if (y.assigned())
00247       return GqBoolInt<XV>::post(home,x,y.val()+c);
00248     // Eliminate assigned views
00249     int n = x.size();
00250     for (int i = n; i--; )
00251       if (x[i].one()) {
00252         x[i]=x[--n]; c--;
00253       } else if (x[i].zero()) {
00254         x[i]=x[--n];
00255       }
00256     x.size(n);
00257     GECODE_ME_CHECK(y.lq(home,n-c));
00258     if (-c >= y.max())
00259       return ES_OK;
00260     if (y.min()+c == n) {
00261       for (int i = n; i--; )
00262         x[i].t_one_none(home);
00263       return ES_OK;
00264     }
00265     (void) new (home) GqBoolView<XV,YV>(home,x,y,c);
00266     return ES_OK;
00267   }
00268 
00269 
00270   template <class XV, class YV>
00271   forceinline
00272   GqBoolView<XV,YV>::GqBoolView(Space* home, bool share, GqBoolView<XV,YV>& p)
00273     : LinBoolView<XV,YV>(home,share,p) {}
00274 
00275   template <class XV, class YV>
00276   Actor*
00277   GqBoolView<XV,YV>::copy(Space* home, bool share) {
00278     return new (home) GqBoolView<XV,YV>(home,share,*this);
00279   }
00280 
00281 
00282   template <class XV, class YV>
00283   ExecStatus
00284   GqBoolView<XV,YV>::propagate(Space* home) {
00285     int n = x.size();
00286     for (int i = n; i--; )
00287       if (x[i].one()) {
00288         x[i]=x[--n]; c--;
00289       } else if (x[i].zero()) {
00290         x[i]=x[--n];
00291       }
00292     x.size(n);
00293     GECODE_ME_CHECK(y.lq(home,n-c));
00294     if (-c >= y.max())
00295       return ES_SUBSUMED;
00296     if (y.min()+c == n) {
00297       for (int i = n; i--; )
00298         x[i].t_one_none(home);
00299       return ES_SUBSUMED;
00300     }
00301     if (y.assigned()) {
00302       GECODE_ES_CHECK(GqBoolInt<XV>::post(home,x,y.val()+c));
00303       return ES_SUBSUMED;
00304     }
00305     return ES_FIX;
00306   }
00307 
00308 }}}
00309 
00310 // STATISTICS: int-prop
00311