gecode » int » count
view.hpp

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: 2009-10-14 12:19:49 +0200 (Wed, 14 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9909 $
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     assert(!home.failed());
00075     x.cancel(home,*this,PC_INT_DOM);
00076     y.cancel(home,*this,PC_INT_DOM);
00077     z.cancel(home,*this,PC_INT_BND);
00078     (void) Propagator::dispose(home);
00079     return sizeof(*this);
00080   }
00081 
00082   template<class VX, class VY, class VZ, bool shr>
00083   forceinline void
00084   BaseView<VX,VY,VZ,shr>::count(Space& home) {
00085     int n = x.size();
00086     for (int i=n; i--; )
00087       switch (holds(x[i],y)) {
00088       case RT_FALSE:
00089         x[i].cancel(home,*this,PC_INT_DOM); x[i]=x[--n];
00090         break;
00091       case RT_TRUE:
00092         x[i].cancel(home,*this,PC_INT_DOM); x[i]=x[--n];
00093         c--;
00094         break;
00095       case RT_MAYBE:
00096         break;
00097       default:
00098         GECODE_NEVER;
00099       }
00100     x.size(n);
00101   }
00102 
00103   template<class VX, class VY, class VZ, bool shr>
00104   forceinline int
00105   BaseView<VX,VY,VZ,shr>::atleast(void) const {
00106     return -c;
00107   }
00108 
00109   template<class VX, class VY, class VZ, bool shr>
00110   forceinline int
00111   BaseView<VX,VY,VZ,shr>::atmost(void) const {
00112     return x.size()-c;
00113   }
00114 
00115   template<class VX, class VY, class VZ, bool shr>
00116   forceinline bool
00117   BaseView<VX,VY,VZ,shr>::sharing(const ViewArray<VX>& x,
00118                                   const VY& y, const VZ& z) {
00119     if (shared(y,z))
00120       return true;
00121     for (int i = x.size(); i--; )
00122       if (shared(x[i],z))
00123         return true;
00124     return false;
00125   }
00126 
00127   /*
00128    * Equality
00129    *
00130    */
00131 
00132   template<class VX, class VY, class VZ, bool shr>
00133   forceinline
00134   EqView<VX,VY,VZ,shr>::EqView(Home home,
00135                                ViewArray<VX>& x, VY y, VZ z, int c)
00136     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00137 
00138   template<class VX, class VY, class VZ, bool shr>
00139   ExecStatus
00140   EqView<VX,VY,VZ,shr>::post(Home home,
00141                              ViewArray<VX>& x, VY y, VZ z, int c) {
00142     if (z.assigned())
00143       return EqInt<VX,VY>::post(home,x,y,z.val()+c);
00144     if (sharing(x,y,z))
00145       (void) new (home) EqView<VX,VY,VZ,true>(home,x,y,z,c);
00146     else
00147       (void) new (home) EqView<VX,VY,VZ,false>(home,x,y,z,c);
00148     return ES_OK;
00149   }
00150 
00151   template<class VX, class VY, class VZ, bool shr>
00152   forceinline
00153   EqView<VX,VY,VZ,shr>::EqView(Space& home, bool share,
00154                                EqView<VX,VY,VZ,shr>& p)
00155     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00156 
00157   template<class VX, class VY, class VZ, bool shr>
00158   Actor*
00159   EqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00160     return new (home) EqView<VX,VY,VZ,shr>(home,share,*this);
00161   }
00162 
00163   template<class VX, class VY, class VZ, bool shr>
00164   ExecStatus
00165   EqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00166     count(home);
00167 
00168     GECODE_ME_CHECK(z.gq(home,atleast()));
00169     GECODE_ME_CHECK(z.lq(home,atmost()));
00170 
00171     if (z.assigned()) {
00172       if (z.val() == atleast())
00173         return post_false(home,x,y) ? ES_FAILED : ES_SUBSUMED(*this,home);
00174       if (z.val() == atmost())
00175         return post_true(home,x,y) ? ES_FAILED : ES_SUBSUMED(*this,home);
00176       GECODE_REWRITE(*this,(EqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00177     }
00178     return shr ? ES_NOFIX : ES_FIX;
00179   }
00180 
00181 
00182 
00183 
00184   /*
00185    * Disequality
00186    *
00187    */
00188 
00189   template<class VX, class VY, class VZ, bool shr>
00190   forceinline
00191   NqView<VX,VY,VZ,shr>::NqView(Home home,
00192                                ViewArray<VX>& x, VY y, VZ z, int c)
00193     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00194 
00195   template<class VX, class VY, class VZ, bool shr>
00196   ExecStatus
00197   NqView<VX,VY,VZ,shr>::post(Home home,
00198                              ViewArray<VX>& x, VY y, VZ z, int c) {
00199     if (z.assigned())
00200       return NqInt<VX,VY>::post(home,x,y,z.val()+c);
00201     (void) new (home) NqView<VX,VY,VZ,shr>(home,x,y,z,c);
00202     return ES_OK;
00203   }
00204 
00205   template<class VX, class VY, class VZ, bool shr>
00206   forceinline
00207   NqView<VX,VY,VZ,shr>::NqView(Space& home, bool share,
00208                                NqView<VX,VY,VZ,shr>& p)
00209     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00210 
00211   template<class VX, class VY, class VZ, bool shr>
00212   Actor*
00213   NqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00214     return new (home) NqView<VX,VY,VZ,shr>(home,share,*this);
00215   }
00216 
00217   template<class VX, class VY, class VZ, bool shr>
00218   ExecStatus
00219   NqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00220     count(home);
00221     if (atleast() == atmost()) {
00222       GECODE_ME_CHECK(z.nq(home,atleast()));
00223       return ES_SUBSUMED(*this,home);
00224     }
00225     if (z.max() < atleast())
00226       return ES_SUBSUMED(*this,home);
00227     if (z.min() > atmost())
00228       return ES_SUBSUMED(*this,home);
00229     if (z.assigned())
00230       GECODE_REWRITE(*this,(NqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00231     return ES_FIX;
00232   }
00233 
00234 
00235 
00236   /*
00237    * Less or equal
00238    *
00239    */
00240 
00241   template<class VX, class VY, class VZ, bool shr>
00242   forceinline
00243   LqView<VX,VY,VZ,shr>::LqView(Home home, ViewArray<VX>& x,
00244                                VY y, VZ z, int c)
00245     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00246 
00247   template<class VX, class VY, class VZ, bool shr>
00248   ExecStatus
00249   LqView<VX,VY,VZ,shr>::post(Home home, ViewArray<VX>& x,
00250                              VY y, VZ z, int c) {
00251     if (z.assigned())
00252       return LqInt<VX,VY>::post(home,x,y,z.val()+c);
00253     if (sharing(x,y,z))
00254       (void) new (home) LqView<VX,VY,VZ,true>(home,x,y,z,c);
00255     else
00256       (void) new (home) LqView<VX,VY,VZ,false>(home,x,y,z,c);
00257     return ES_OK;
00258   }
00259 
00260   template<class VX, class VY, class VZ, bool shr>
00261   forceinline
00262   LqView<VX,VY,VZ,shr>::LqView(Space& home, bool share,
00263                                LqView<VX,VY,VZ,shr>& p)
00264     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00265 
00266   template<class VX, class VY, class VZ, bool shr>
00267   Actor*
00268   LqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00269     return new (home) LqView<VX,VY,VZ,shr>(home,share,*this);
00270   }
00271 
00272   template<class VX, class VY, class VZ, bool shr>
00273   ExecStatus
00274   LqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00275     count(home);
00276     GECODE_ME_CHECK(z.gq(home,atleast()));
00277     if (z.max() == atleast())
00278       return post_false(home,x,y) ? ES_FAILED : ES_SUBSUMED(*this,home);
00279     if (x.size() == 0)
00280       return ES_SUBSUMED(*this,home);
00281     if (z.assigned())
00282       GECODE_REWRITE(*this,(LqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00283     return shr ? ES_NOFIX : ES_FIX;
00284   }
00285 
00286 
00287 
00288   /*
00289    * Greater or equal
00290    *
00291    */
00292 
00293   template<class VX, class VY, class VZ, bool shr>
00294   forceinline
00295   GqView<VX,VY,VZ,shr>::GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c)
00296     : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {}
00297 
00298   template<class VX, class VY, class VZ, bool shr>
00299   ExecStatus
00300   GqView<VX,VY,VZ,shr>::post(Home home,
00301                              ViewArray<VX>& x, VY y, VZ z, int c) {
00302     if (z.assigned())
00303       return GqInt<VX,VY>::post(home,x,y,z.val()+c);
00304     if (sharing(x,y,z))
00305       (void) new (home) GqView<VX,VY,VZ,true>(home,x,y,z,c);
00306     else
00307       (void) new (home) GqView<VX,VY,VZ,false>(home,x,y,z,c);
00308     return ES_OK;
00309   }
00310 
00311   template<class VX, class VY, class VZ, bool shr>
00312   forceinline
00313   GqView<VX,VY,VZ,shr>::GqView(Space& home, bool share,
00314                                GqView<VX,VY,VZ,shr>& p)
00315     : BaseView<VX,VY,VZ,shr>(home,share,p) {}
00316 
00317   template<class VX, class VY, class VZ, bool shr>
00318   Actor*
00319   GqView<VX,VY,VZ,shr>::copy(Space& home, bool share) {
00320     return new (home) GqView<VX,VY,VZ,shr>(home,share,*this);
00321   }
00322 
00323   template<class VX, class VY, class VZ, bool shr>
00324   ExecStatus
00325   GqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) {
00326     count(home);
00327 
00328     GECODE_ME_CHECK(z.lq(home,atmost()));
00329 
00330     if (z.min() == atmost())
00331       return post_true(home,x,y) ? ES_FAILED : ES_SUBSUMED(*this,home);
00332     if (x.size() == 0)
00333       return ES_SUBSUMED(*this,home);
00334     if (z.assigned())
00335       GECODE_REWRITE(*this,(GqInt<VX,VY>::post(home(*this),x,y,z.val()+c)));
00336     return shr ? ES_NOFIX : ES_FIX;
00337   }
00338 
00339 }}}
00340 
00341 // STATISTICS: int-prop
00342