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

count.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-05-29 09:42:21 +0200 (Mon, 29 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3246 $
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 Count {
00023 
00024   /*
00025    * General baseclass
00026    *
00027    */
00028 
00029   template <class VX, class VY, class VZ, class Rel, bool shr>
00030   Base<VX,VY,VZ,Rel,shr>::Base(Space* home, 
00031                                ViewArray<VX>& x0, VY y0, VZ z0, int c0)
00032     : Propagator(home), x(x0), y(y0), z(z0), c(c0) {
00033     x.subscribe(home,this,r.cond());
00034     y.subscribe(home,this,r.cond());
00035     z.subscribe(home,this,PC_INT_BND);
00036   }
00037 
00038   template <class VX, class VY, class VZ, class Rel, bool shr>
00039   inline
00040   Base<VX,VY,VZ,Rel,shr>::Base(Space* home, bool share,
00041                                Base<VX,VY,VZ,Rel,shr>& p)
00042     : Propagator(home,shr,p), c(p.c) {
00043     x.update(home,share,p.x);
00044     y.update(home,share,p.y);
00045     z.update(home,share,p.z);
00046   }
00047 
00048   template <class VX, class VY, class VZ, class Rel, bool shr>
00049   PropCost
00050   Base<VX,VY,VZ,Rel,shr>::cost(void) const {
00051     return cost_lo(x.size()+1, PC_LINEAR_LO);
00052   }
00053 
00054   template <class VX, class VY, class VZ, class Rel, bool shr>
00055   size_t
00056   Base<VX,VY,VZ,Rel,shr>::dispose(Space* home) {
00057     assert(!home->failed());
00058     x.cancel(home,this,r.cond());
00059     y.cancel(home,this,r.cond());
00060     z.cancel(home,this,PC_INT_BND);
00061     (void) Propagator::dispose(home);
00062     return sizeof(*this);
00063   }
00064 
00065   template <class VX, class VY, class VZ, class Rel, bool shr>
00066   forceinline int
00067   Base<VX,VY,VZ,Rel,shr>::atleast(void) const {
00068     return c;
00069   }
00070 
00071   template <class VX, class VY, class VZ, class Rel, bool shr>
00072   forceinline int
00073   Base<VX,VY,VZ,Rel,shr>::atmost(void) const {
00074     return c+x.size();
00075   }
00076 
00077   template <class VX, class VY, class VZ, class Rel, bool shr>
00078   inline bool
00079   Base<VX,VY,VZ,Rel,shr>::sharing(const ViewArray<VX>& x,
00080                                     const VY& y, const VZ& z) {
00081     if (shared(y,z))
00082       return true;
00083     for (int i = x.size(); i--; )
00084       if (shared(x[i],z))
00085         return true;
00086     return false;
00087   }
00088 
00089   /*
00090    * Equality
00091    *
00092    */
00093 
00094   template <class VX, class VY, class VZ, class Rel, bool shr>
00095   forceinline
00096   Eq<VX,VY,VZ,Rel,shr>::Eq(Space* home, 
00097                                ViewArray<VX>& x, VY y, VZ z, int c)
00098     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00099 
00100   template <class VX, class VY, class VZ, class Rel, bool shr>
00101   ExecStatus
00102   Eq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00103                                 ViewArray<VX>& x, VY y, VZ z, int c) {
00104     if (sharing(x,y,z))
00105       (void) new (home) Eq<VX,VY,VZ,Rel,true>(home,x,y,z,c);
00106     else
00107       (void) new (home) Eq<VX,VY,VZ,Rel,false>(home,x,y,z,c);
00108     return ES_OK;
00109   }
00110 
00111   template <class VX, class VY, class VZ, class Rel, bool shr>
00112   forceinline
00113   Eq<VX,VY,VZ,Rel,shr>::Eq(Space* home, bool share,
00114                                Eq<VX,VY,VZ,Rel,shr>& p)
00115     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00116 
00117   template <class VX, class VY, class VZ, class Rel, bool shr>
00118   Actor*
00119   Eq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00120     return new (home) Eq<VX,VY,VZ,Rel,shr>(home,share,*this);
00121   }
00122 
00123   template <class VX, class VY, class VZ, class Rel, bool shr>
00124   ExecStatus
00125   Eq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00126     for (int i = x.size(); i--; )
00127       switch (r.holds(x[i],y)) {
00128       case RT_FALSE:
00129         x.move_lst(i,home,this,r.cond());
00130         if (z.min() == atmost()) goto decided;
00131         break;
00132       case RT_TRUE:
00133         x.move_lst(i,home,this,r.cond()); c++;
00134         if (z.max() == atleast()) goto decided;
00135         break;
00136       default: ;
00137       }
00138   decided:
00139     GECODE_ME_CHECK(z.gq(home,atleast()));
00140     GECODE_ME_CHECK(z.lq(home,atmost()));
00141 
00142     if (z.assigned()) {
00143       if (z.val() == atleast()) 
00144         return r.post_false(home,x,y);
00145       if (z.val() == atmost())  
00146         return r.post_true(home,x,y);
00147     }
00148     return shr ? ES_NOFIX : ES_FIX;
00149   }
00150 
00151 
00152 
00153 
00154   /*
00155    * Disequality
00156    *
00157    */
00158 
00159   template <class VX, class VY, class VZ, class Rel, bool shr>
00160   forceinline
00161   Nq<VX,VY,VZ,Rel,shr>::Nq(Space* home, 
00162                                ViewArray<VX>& x, VY y, VZ z, int c)
00163     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00164 
00165   template <class VX, class VY, class VZ, class Rel, bool shr>
00166   ExecStatus
00167   Nq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00168                              ViewArray<VX>& x, VY y, VZ z, int c) {
00169     (void) new (home) Nq<VX,VY,VZ,Rel,shr>(home,x,y,z,c);
00170     return ES_OK;
00171   }
00172 
00173   template <class VX, class VY, class VZ, class Rel, bool shr>
00174   forceinline
00175   Nq<VX,VY,VZ,Rel,shr>::Nq(Space* home, bool share,
00176                                Nq<VX,VY,VZ,Rel,shr>& p)
00177     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00178 
00179   template <class VX, class VY, class VZ, class Rel, bool shr>
00180   Actor*
00181   Nq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00182     return new (home) Nq<VX,VY,VZ,Rel,shr>(home,share,*this);
00183   }
00184 
00185   template <class VX, class VY, class VZ, class Rel, bool shr>
00186   ExecStatus
00187   Nq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00188     for (int i = x.size(); i--; )
00189       switch (r.holds(x[i],y)) {
00190       case RT_FALSE:
00191         x.move_lst(i,home,this,r.cond()); break;
00192       case RT_TRUE:
00193         x.move_lst(i,home,this,r.cond()); c++; break;
00194       default: ;
00195       }
00196     if (atleast() == atmost()) {
00197       GECODE_ME_CHECK(z.nq(home,atleast()));
00198       return ES_SUBSUMED;
00199     }
00200     if (z.max() < atleast())
00201       return ES_SUBSUMED;
00202     if (z.min() > atmost())
00203       return ES_SUBSUMED;
00204     return ES_FIX;
00205   }
00206 
00207 
00208 
00209   /*
00210    * Less or equal
00211    *
00212    */
00213 
00214   template <class VX, class VY, class VZ, class Rel, bool shr>
00215   forceinline
00216   Lq<VX,VY,VZ,Rel,shr>::Lq(Space* home, 
00217                                ViewArray<VX>& x, VY y, VZ z, int c)
00218     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00219 
00220   template <class VX, class VY, class VZ, class Rel, bool shr>
00221   ExecStatus
00222   Lq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00223                              ViewArray<VX>& x, VY y, VZ z, int c) {
00224     if (sharing(x,y,z))
00225       (void) new (home) Lq<VX,VY,VZ,Rel,true>(home,x,y,z,c);
00226     else
00227       (void) new (home) Lq<VX,VY,VZ,Rel,false>(home,x,y,z,c);
00228     return ES_OK;
00229   }
00230   
00231   template <class VX, class VY, class VZ, class Rel, bool shr>
00232   forceinline
00233   Lq<VX,VY,VZ,Rel,shr>::Lq(Space* home, bool share,
00234                                Lq<VX,VY,VZ,Rel,shr>& p)
00235     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00236   
00237   template <class VX, class VY, class VZ, class Rel, bool shr>
00238   Actor*
00239   Lq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00240     return new (home) Lq<VX,VY,VZ,Rel,shr>(home,share,*this);
00241   }
00242 
00243   template <class VX, class VY, class VZ, class Rel, bool shr>
00244   ExecStatus
00245   Lq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00246     for (int i = x.size(); i--; )
00247       switch (r.holds(x[i],y)) {
00248       case RT_FALSE:
00249         x.move_lst(i,home,this,r.cond()); break;
00250       case RT_TRUE:
00251         x.move_lst(i,home,this,r.cond()); c++;
00252         if (z.max() == atleast()) goto decided;
00253         break;
00254       default: ;
00255       }
00256   decided:
00257     GECODE_ME_CHECK(z.gq(home,atleast()));
00258     if (z.max() == atleast())
00259       return r.post_false(home,x,y);
00260     if (x.size() == 0)
00261       return ES_SUBSUMED;
00262     return shr ? ES_NOFIX : ES_FIX;
00263   }
00264 
00265 
00266 
00267   /*
00268    * Greater or equal
00269    *
00270    */
00271 
00272   template <class VX, class VY, class VZ, class Rel, bool shr>
00273   forceinline
00274   Gq<VX,VY,VZ,Rel,shr>::Gq(Space* home, 
00275                                ViewArray<VX>& x, VY y, VZ z, int c)
00276     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00277 
00278   template <class VX, class VY, class VZ, class Rel, bool shr>
00279   ExecStatus
00280   Gq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00281                              ViewArray<VX>& x, VY y, VZ z, int c) {
00282     if (sharing(x,y,z))
00283       (void) new (home) Gq<VX,VY,VZ,Rel,true>(home,x,y,z,c);
00284     else
00285       (void) new (home) Gq<VX,VY,VZ,Rel,false>(home,x,y,z,c);
00286     return ES_OK;
00287   }
00288 
00289   template <class VX, class VY, class VZ, class Rel, bool shr>
00290   forceinline
00291   Gq<VX,VY,VZ,Rel,shr>::Gq(Space* home, bool share,
00292                                Gq<VX,VY,VZ,Rel,shr>& p)
00293     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00294 
00295   template <class VX, class VY, class VZ, class Rel, bool shr>
00296   Actor*
00297   Gq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00298     return new (home) Gq<VX,VY,VZ,Rel,shr>(home,share,*this);
00299   }
00300 
00301   template <class VX, class VY, class VZ, class Rel, bool shr>
00302   ExecStatus
00303   Gq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00304     for (int i = x.size(); i--; )
00305       switch (r.holds(x[i],y)) {
00306       case RT_FALSE:
00307         x.move_lst(i,home,this,r.cond());
00308         if (z.min() == atmost()) goto decided;
00309         break;
00310       case RT_TRUE:
00311         x.move_lst(i,home,this,r.cond()); c++;
00312         break;
00313       default: ;
00314       }
00315   decided:
00316     GECODE_ME_CHECK(z.lq(home,atmost()));
00317 
00318     if (z.min() == atmost())
00319       return r.post_true(home,x,y);
00320     if (x.size() == 0)
00321       return ES_SUBSUMED;
00322     return shr ? ES_NOFIX : ES_FIX;
00323   }
00324 
00325 }}}
00326 
00327 // STATISTICS: int-prop
00328