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

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: 2005-11-04 13:56:04 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2497 $
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   inline
00056   Base<VX,VY,VZ,Rel,shr>::~Base(void) {
00057     x.cancel(this,r.cond());
00058     y.cancel(this,r.cond());
00059     z.cancel(this,PC_INT_BND);
00060   }
00061 
00062   template <class VX, class VY, class VZ, class Rel, bool shr>
00063   forceinline int
00064   Base<VX,VY,VZ,Rel,shr>::atleast(void) const {
00065     return c;
00066   }
00067 
00068   template <class VX, class VY, class VZ, class Rel, bool shr>
00069   forceinline int
00070   Base<VX,VY,VZ,Rel,shr>::atmost(void) const {
00071     return c+x.size();
00072   }
00073 
00074   template <class VX, class VY, class VZ, class Rel, bool shr>
00075   inline bool
00076   Base<VX,VY,VZ,Rel,shr>::sharing(const ViewArray<VX>& x,
00077                                     const VY& y, const VZ& z) {
00078     if (shared(y,z))
00079       return true;
00080     for (int i = x.size(); i--; )
00081       if (shared(x[i],z))
00082         return true;
00083     return false;
00084   }
00085 
00086   /*
00087    * Equality
00088    *
00089    */
00090 
00091   template <class VX, class VY, class VZ, class Rel, bool shr>
00092   forceinline
00093   Eq<VX,VY,VZ,Rel,shr>::Eq(Space* home, 
00094                                ViewArray<VX>& x, VY y, VZ z, int c)
00095     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00096 
00097   template <class VX, class VY, class VZ, class Rel, bool shr>
00098   ExecStatus
00099   Eq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00100                                 ViewArray<VX>& x, VY y, VZ z, int c) {
00101     if (sharing(x,y,z))
00102       (void) new (home) Eq<VX,VY,VZ,Rel,true>(home,x,y,z,c);
00103     else
00104       (void) new (home) Eq<VX,VY,VZ,Rel,false>(home,x,y,z,c);
00105     return ES_OK;
00106   }
00107 
00108   template <class VX, class VY, class VZ, class Rel, bool shr>
00109   forceinline
00110   Eq<VX,VY,VZ,Rel,shr>::Eq(Space* home, bool share,
00111                                Eq<VX,VY,VZ,Rel,shr>& p)
00112     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00113 
00114   template <class VX, class VY, class VZ, class Rel, bool shr>
00115   Actor*
00116   Eq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00117     return new (home) Eq<VX,VY,VZ,Rel,shr>(home,share,*this);
00118   }
00119 
00120   template <class VX, class VY, class VZ, class Rel, bool shr>
00121   ExecStatus
00122   Eq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00123     for (int i = x.size(); i--; )
00124       switch (r.holds(x[i],y)) {
00125       case RT_FALSE:
00126         x.move_lst(i,this,r.cond());
00127         if (z.min() == atmost()) goto decided;
00128         break;
00129       case RT_TRUE:
00130         x.move_lst(i,this,r.cond()); c++;
00131         if (z.max() == atleast()) goto decided;
00132         break;
00133       default: ;
00134       }
00135   decided:
00136     GECODE_ME_CHECK(z.gq(home,atleast()));
00137     GECODE_ME_CHECK(z.lq(home,atmost()));
00138 
00139     if (z.assigned()) {
00140       if (z.val() == atleast()) 
00141         return r.post_false(home,x,y);
00142       if (z.val() == atmost())  
00143         return r.post_true(home,x,y);
00144     }
00145     return shr ? ES_NOFIX : ES_FIX;
00146   }
00147 
00148 
00149 
00150 
00151   /*
00152    * Disequality
00153    *
00154    */
00155 
00156   template <class VX, class VY, class VZ, class Rel, bool shr>
00157   forceinline
00158   Nq<VX,VY,VZ,Rel,shr>::Nq(Space* home, 
00159                                ViewArray<VX>& x, VY y, VZ z, int c)
00160     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00161 
00162   template <class VX, class VY, class VZ, class Rel, bool shr>
00163   ExecStatus
00164   Nq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00165                              ViewArray<VX>& x, VY y, VZ z, int c) {
00166     (void) new (home) Nq<VX,VY,VZ,Rel,shr>(home,x,y,z,c);
00167     return ES_OK;
00168   }
00169 
00170   template <class VX, class VY, class VZ, class Rel, bool shr>
00171   forceinline
00172   Nq<VX,VY,VZ,Rel,shr>::Nq(Space* home, bool share,
00173                                Nq<VX,VY,VZ,Rel,shr>& p)
00174     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00175 
00176   template <class VX, class VY, class VZ, class Rel, bool shr>
00177   Actor*
00178   Nq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00179     return new (home) Nq<VX,VY,VZ,Rel,shr>(home,share,*this);
00180   }
00181 
00182   template <class VX, class VY, class VZ, class Rel, bool shr>
00183   ExecStatus
00184   Nq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00185     for (int i = x.size(); i--; )
00186       switch (r.holds(x[i],y)) {
00187       case RT_FALSE:
00188         x.move_lst(i,this,r.cond()); break;
00189       case RT_TRUE:
00190         x.move_lst(i,this,r.cond()); c++; break;
00191       default: ;
00192       }
00193     if (atleast() == atmost()) {
00194       GECODE_ME_CHECK(z.nq(home,atleast()));
00195       return ES_SUBSUMED;
00196     }
00197     if (z.max() < atleast())
00198       return ES_SUBSUMED;
00199     if (z.min() > atmost())
00200       return ES_SUBSUMED;
00201     return ES_FIX;
00202   }
00203 
00204 
00205 
00206   /*
00207    * Less or equal
00208    *
00209    */
00210 
00211   template <class VX, class VY, class VZ, class Rel, bool shr>
00212   forceinline
00213   Lq<VX,VY,VZ,Rel,shr>::Lq(Space* home, 
00214                                ViewArray<VX>& x, VY y, VZ z, int c)
00215     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00216 
00217   template <class VX, class VY, class VZ, class Rel, bool shr>
00218   ExecStatus
00219   Lq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00220                              ViewArray<VX>& x, VY y, VZ z, int c) {
00221     if (sharing(x,y,z))
00222       (void) new (home) Lq<VX,VY,VZ,Rel,true>(home,x,y,z,c);
00223     else
00224       (void) new (home) Lq<VX,VY,VZ,Rel,false>(home,x,y,z,c);
00225     return ES_OK;
00226   }
00227   
00228   template <class VX, class VY, class VZ, class Rel, bool shr>
00229   forceinline
00230   Lq<VX,VY,VZ,Rel,shr>::Lq(Space* home, bool share,
00231                                Lq<VX,VY,VZ,Rel,shr>& p)
00232     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00233   
00234   template <class VX, class VY, class VZ, class Rel, bool shr>
00235   Actor*
00236   Lq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00237     return new (home) Lq<VX,VY,VZ,Rel,shr>(home,share,*this);
00238   }
00239 
00240   template <class VX, class VY, class VZ, class Rel, bool shr>
00241   ExecStatus
00242   Lq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00243     for (int i = x.size(); i--; )
00244       switch (r.holds(x[i],y)) {
00245       case RT_FALSE:
00246         x.move_lst(i,this,r.cond()); break;
00247       case RT_TRUE:
00248         x.move_lst(i,this,r.cond()); c++;
00249         if (z.max() == atleast()) goto decided;
00250         break;
00251       default: ;
00252       }
00253   decided:
00254     GECODE_ME_CHECK(z.gq(home,atleast()));
00255     if (z.max() == atleast())
00256       return r.post_false(home,x,y);
00257     if (x.size() == 0)
00258       return ES_SUBSUMED;
00259     return shr ? ES_NOFIX : ES_FIX;
00260   }
00261 
00262 
00263 
00264   /*
00265    * Greater or equal
00266    *
00267    */
00268 
00269   template <class VX, class VY, class VZ, class Rel, bool shr>
00270   forceinline
00271   Gq<VX,VY,VZ,Rel,shr>::Gq(Space* home, 
00272                                ViewArray<VX>& x, VY y, VZ z, int c)
00273     : Base<VX,VY,VZ,Rel,shr>(home,x,y,z,c) {}
00274 
00275   template <class VX, class VY, class VZ, class Rel, bool shr>
00276   ExecStatus
00277   Gq<VX,VY,VZ,Rel,shr>::post(Space* home, 
00278                              ViewArray<VX>& x, VY y, VZ z, int c) {
00279     if (sharing(x,y,z))
00280       (void) new (home) Gq<VX,VY,VZ,Rel,true>(home,x,y,z,c);
00281     else
00282       (void) new (home) Gq<VX,VY,VZ,Rel,false>(home,x,y,z,c);
00283     return ES_OK;
00284   }
00285 
00286   template <class VX, class VY, class VZ, class Rel, bool shr>
00287   forceinline
00288   Gq<VX,VY,VZ,Rel,shr>::Gq(Space* home, bool share,
00289                                Gq<VX,VY,VZ,Rel,shr>& p)
00290     : Base<VX,VY,VZ,Rel,shr>(home,share,p) {}
00291 
00292   template <class VX, class VY, class VZ, class Rel, bool shr>
00293   Actor*
00294   Gq<VX,VY,VZ,Rel,shr>::copy(Space* home, bool share) {
00295     return new (home) Gq<VX,VY,VZ,Rel,shr>(home,share,*this);
00296   }
00297 
00298   template <class VX, class VY, class VZ, class Rel, bool shr>
00299   ExecStatus
00300   Gq<VX,VY,VZ,Rel,shr>::propagate(Space* home) {
00301     for (int i = x.size(); i--; )
00302       switch (r.holds(x[i],y)) {
00303       case RT_FALSE:
00304         x.move_lst(i,this,r.cond());
00305         if (z.min() == atmost()) goto decided;
00306         break;
00307       case RT_TRUE:
00308         x.move_lst(i,this,r.cond()); c++;
00309         break;
00310       default: ;
00311       }
00312   decided:
00313     GECODE_ME_CHECK(z.lq(home,atmost()));
00314 
00315     if (z.min() == atmost())
00316       return r.post_true(home,x,y);
00317     if (x.size() == 0)
00318       return ES_SUBSUMED;
00319     return shr ? ES_NOFIX : ES_FIX;
00320   }
00321 
00322 }}}
00323 
00324 // STATISTICS: int-prop
00325