Generated on Mon May 10 06:46:35 2010 for Gecode by doxygen 1.6.3

view.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00011  *     $Revision: 10364 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Int { namespace Count {
00039 
00040   /*
00041    * General baseclass
00042    *
00043    */
00044 
00045   template<class VX, class VY, class VZ, bool shr>
00046   forceinline
00047   BaseView<VX,VY,VZ,shr>::BaseView(Home home,
00048                                    ViewArray<VX>& x0, VY y0, VZ z0, int c0)
00049     : Propagator(home), x(x0), y(y0), z(z0), c(c0) {
00050     x.subscribe(home,*this,PC_INT_DOM);
00051     y.subscribe(home,*this,PC_INT_DOM);
00052     z.subscribe(home,*this,PC_INT_BND);
00053   }
00054 
00055   template<class VX, class VY, class VZ, bool shr>
00056   forceinline
00057   BaseView<VX,VY,VZ,shr>::BaseView(Space& home, bool share,
00058                                    BaseView<VX,VY,VZ,shr>& p)
00059     : Propagator(home,shr,p), c(p.c) {
00060     x.update(home,share,p.x);
00061     y.update(home,share,p.y);
00062     z.update(home,share,p.z);
00063   }
00064 
00065   template<class VX, class VY, class VZ, bool shr>
00066   PropCost
00067   BaseView<VX,VY,VZ,shr>::cost(const Space&, const ModEventDelta&) const {
00068     return PropCost::linear(PropCost::LO,x.size()+1);
00069   }
00070 
00071   template<class VX, class VY, class VZ, bool shr>
00072   forceinline size_t
00073   BaseView<VX,VY,VZ,shr>::dispose(Space& home) {
00074     x.cancel(home,*this,PC_INT_DOM);
00075     y.cancel(home,*this,PC_INT_DOM);
00076     z.cancel(home,*this,PC_INT_BND);
00077     (void) Propagator::dispose(home);
00078     return sizeof(*this);
00079   }
00080 
00081   template<class VX, class VY, class VZ, bool shr>
00082   forceinline void
00083   BaseView<VX,VY,VZ,shr>::count(Space& home) {
00084     int n = x.size();
00085     for (int i=n; i--; )
00086       switch (holds(x[i],y)) {
00087       case RT_FALSE:
00088         x[i].cancel(home,*this,PC_INT_DOM); x[i]=x[--n];
00089         break;
00090       case RT_TRUE:
00091         x[i].cancel(home,*this,PC_INT_DOM); x[i]=x[--n];
00092         c--;
00093         break;
00094       case RT_MAYBE:
00095         break;
00096       default:
00097         GECODE_NEVER;
00098       }
00099     x.size(n);
00100   }
00101 
00102   template<class VX, class VY, class VZ, bool shr>
00103   forceinline int
00104   BaseView<VX,VY,VZ,shr>::atleast(void) const {
00105     return -c;
00106   }
00107 
00108   template<class VX, class VY, class VZ, bool shr>
00109   forceinline int
00110   BaseView<VX,VY,VZ,shr>::atmost(void) const {
00111     return x.size()-c;
00112   }
00113 
00114   template<class VX, class VY, class VZ, bool shr>
00115   forceinline bool
00116   BaseView<VX,VY,VZ,shr>::sharing(const ViewArray<VX>& x,
00117                                   const VY& y, const VZ& z) {
00118     if (shared(y,z))
00119       return true;
00120     for (int i = x.size(); i--; )
00121       if (shared(x[i],z))
00122         return true;
00123     return false;
00124   }
00125 
00126   /*
00127    * Equality
00128    *
00129    */
00130 
00131   template<class VX, class VY, class VZ, bool shr>
00132   forceinline
00133   EqView<VX,VY,VZ,shr>::EqView(Home home,
00134                                ViewArray<VX>& x, VY y, VZ z, int c)
00135     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00136 
00137   template<class VX, class VY, class VZ, bool shr>
00138   ExecStatus
00139   EqView<VX,VY,VZ,shr>::post(Home home,
00140                              ViewArray<VX>& x, VY y, VZ z, int c) {
00141     if (z.assigned())
00142       return EqInt<VX,VY>::post(home,x,y,z.val()+c);
00143     if (sharing(x,y,z))
00144       (void) new (home) EqView<VX,VY,VZ,true>(home,x,y,z,c);
00145     else
00146       (void) new (home) EqView<VX,VY,VZ,false>(home,x,y,z,c);
00147     return ES_OK;
00148   }
00149 
00150   template<class VX, class VY, class VZ, bool shr>
00151   forceinline
00152   EqView<VX,VY,VZ,shr>::EqView(Space& home, bool share,
00153                                EqView<VX,VY,VZ,shr>& p)
00154     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00155 
00156   template<class VX, class VY, class VZ, bool shr>
00157   Actor*
00158   EqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00159     return new (home) EqView<VX,VY,VZ,shr>(home,share,*this);
00160   }
00161 
00162   template<class VX, class VY, class VZ, bool shr>
00163   ExecStatus
00164   EqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00165     count(home);
00166 
00167     GECODE_ME_CHECK(z.gq(home,atleast()));
00168     GECODE_ME_CHECK(z.lq(home,atmost()));
00169 
00170     if (z.assigned()) {
00171       if (z.val() == atleast())
00172         return post_false(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00173       if (z.val() == atmost())
00174         return post_true(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00175       GECODE_REWRITE(*this,(EqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00176     }
00177     return shr ? ES_NOFIX : ES_FIX;
00178   }
00179 
00180 
00181 
00182 
00183   /*
00184    * Disequality
00185    *
00186    */
00187 
00188   template<class VX, class VY, class VZ, bool shr>
00189   forceinline
00190   NqView<VX,VY,VZ,shr>::NqView(Home home,
00191                                ViewArray<VX>& x, VY y, VZ z, int c)
00192     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00193 
00194   template<class VX, class VY, class VZ, bool shr>
00195   ExecStatus
00196   NqView<VX,VY,VZ,shr>::post(Home home,
00197                              ViewArray<VX>& x, VY y, VZ z, int c) {
00198     if (z.assigned())
00199       return NqInt<VX,VY>::post(home,x,y,z.val()+c);
00200     (void) new (home) NqView<VX,VY,VZ,shr>(home,x,y,z,c);
00201     return ES_OK;
00202   }
00203 
00204   template<class VX, class VY, class VZ, bool shr>
00205   forceinline
00206   NqView<VX,VY,VZ,shr>::NqView(Space& home, bool share,
00207                                NqView<VX,VY,VZ,shr>& p)
00208     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00209 
00210   template<class VX, class VY, class VZ, bool shr>
00211   Actor*
00212   NqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00213     return new (home) NqView<VX,VY,VZ,shr>(home,share,*this);
00214   }
00215 
00216   template<class VX, class VY, class VZ, bool shr>
00217   ExecStatus
00218   NqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00219     count(home);
00220     if (atleast() == atmost()) {
00221       GECODE_ME_CHECK(z.nq(home,atleast()));
00222       return home.ES_SUBSUMED(*this);
00223     }
00224     if (z.max() < atleast())
00225       return home.ES_SUBSUMED(*this);
00226     if (z.min() > atmost())
00227       return home.ES_SUBSUMED(*this);
00228     if (z.assigned())
00229       GECODE_REWRITE(*this,(NqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00230     return ES_FIX;
00231   }
00232 
00233 
00234 
00235   /*
00236    * Less or equal
00237    *
00238    */
00239 
00240   template<class VX, class VY, class VZ, bool shr>
00241   forceinline
00242   LqView<VX,VY,VZ,shr>::LqView(Home home, ViewArray<VX>& x,
00243                                VY y, VZ z, int c)
00244     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00245 
00246   template<class VX, class VY, class VZ, bool shr>
00247   ExecStatus
00248   LqView<VX,VY,VZ,shr>::post(Home home, ViewArray<VX>& x,
00249                              VY y, VZ z, int c) {
00250     if (z.assigned())
00251       return LqInt<VX,VY>::post(home,x,y,z.val()+c);
00252     if (sharing(x,y,z))
00253       (void) new (home) LqView<VX,VY,VZ,true>(home,x,y,z,c);
00254     else
00255       (void) new (home) LqView<VX,VY,VZ,false>(home,x,y,z,c);
00256     return ES_OK;
00257   }
00258 
00259   template<class VX, class VY, class VZ, bool shr>
00260   forceinline
00261   LqView<VX,VY,VZ,shr>::LqView(Space& home, bool share,
00262                                LqView<VX,VY,VZ,shr>& p)
00263     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00264 
00265   template<class VX, class VY, class VZ, bool shr>
00266   Actor*
00267   LqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00268     return new (home) LqView<VX,VY,VZ,shr>(home,share,*this);
00269   }
00270 
00271   template<class VX, class VY, class VZ, bool shr>
00272   ExecStatus
00273   LqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00274     count(home);
00275     GECODE_ME_CHECK(z.gq(home,atleast()));
00276     if (z.max() == atleast())
00277       return post_false(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00278     if (x.size() == 0)
00279       return home.ES_SUBSUMED(*this);
00280     if (z.assigned())
00281       GECODE_REWRITE(*this,(LqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00282     return shr ? ES_NOFIX : ES_FIX;
00283   }
00284 
00285 
00286 
00287   /*
00288    * Greater or equal
00289    *
00290    */
00291 
00292   template<class VX, class VY, class VZ, bool shr>
00293   forceinline
00294   GqView<VX,VY,VZ,shr>::GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c)
00295     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00296 
00297   template<class VX, class VY, class VZ, bool shr>
00298   ExecStatus
00299   GqView<VX,VY,VZ,shr>::post(Home home,
00300                              ViewArray<VX>& x, VY y, VZ z, int c) {
00301     if (z.assigned())
00302       return GqInt<VX,VY>::post(home,x,y,z.val()+c);
00303     if (sharing(x,y,z))
00304       (void) new (home) GqView<VX,VY,VZ,true>(home,x,y,z,c);
00305     else
00306       (void) new (home) GqView<VX,VY,VZ,false>(home,x,y,z,c);
00307     return ES_OK;
00308   }
00309 
00310   template<class VX, class VY, class VZ, bool shr>
00311   forceinline
00312   GqView<VX,VY,VZ,shr>::GqView(Space& home, bool share,
00313                                GqView<VX,VY,VZ,shr>& p)
00314     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00315 
00316   template<class VX, class VY, class VZ, bool shr>
00317   Actor*
00318   GqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00319     return new (home) GqView<VX,VY,VZ,shr>(home,share,*this);
00320   }
00321 
00322   template<class VX, class VY, class VZ, bool shr>
00323   ExecStatus
00324   GqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00325     count(home);
00326 
00327     GECODE_ME_CHECK(z.lq(home,atmost()));
00328 
00329     if (z.min() == atmost())
00330       return post_true(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00331     if (x.size() == 0)
00332       return home.ES_SUBSUMED(*this);
00333     if (z.assigned())
00334       GECODE_REWRITE(*this,(GqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00335     return shr ? ES_NOFIX : ES_FIX;
00336   }
00337 
00338 }}}
00339 
00340 // STATISTICS: int-prop
00341