Generated on Thu Apr 11 13:59:10 2019 for Gecode by doxygen 1.6.3

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