gecode » int » linear
bool-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, 2004
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 Linear {
00039 
00040   /*
00041    * Base-class
00042    *
00043    */
00044   template<class XV, class YV>
00045   LinBoolView<XV,YV>::LinBoolView(Home home,
00046                                   ViewArray<XV>& x0, YV y0, int c0)
00047     :  Propagator(home), x(x0), y(y0), c(c0) {
00048     x.subscribe(home,*this,PC_INT_VAL);
00049     y.subscribe(home,*this,PC_INT_BND);
00050   }
00051 
00052   template<class XV, class YV>
00053   forceinline size_t
00054   LinBoolView<XV,YV>::dispose(Space& home) {
00055     assert(!home.failed());
00056     x.cancel(home,*this,PC_INT_VAL);
00057     y.cancel(home,*this,PC_INT_BND);
00058     (void) Propagator::dispose(home);
00059     return sizeof(*this);
00060   }
00061 
00062   template<class XV, class YV>
00063   forceinline
00064   LinBoolView<XV,YV>::LinBoolView(Space& home, bool share, LinBoolView& p)
00065     : Propagator(home,share,p), c(p.c) {
00066     x.update(home,share,p.x);
00067     y.update(home,share,p.y);
00068   }
00069 
00070   template<class XV, class YV>
00071   PropCost
00072   LinBoolView<XV,YV>::cost(const Space&, const ModEventDelta&) const {
00073     return PropCost::linear(PropCost::LO, x.size());
00074   }
00075 
00076 
00077   /*
00078    * Equality propagator
00079    *
00080    */
00081   template<class XV, class YV>
00082   forceinline
00083   EqBoolView<XV,YV>::EqBoolView(Home home, ViewArray<XV>& x, YV y, int c)
00084     : LinBoolView<XV,YV>(home,x,y,c) {}
00085 
00086   template<class XV, class YV>
00087   ExecStatus
00088   EqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) {
00089     if (y.assigned())
00090       return EqBoolInt<XV>::post(home,x,y.val()+c);
00091     int n = x.size();
00092     for (int i = n; i--; )
00093       if (x[i].one()) {
00094         x[i]=x[--n]; c--;
00095       } else if (x[i].zero()) {
00096         x[i]=x[--n];
00097       }
00098     x.size(n);
00099     GECODE_ME_CHECK(y.lq(home,n-c));
00100     GECODE_ME_CHECK(y.gq(home,-c));
00101     if (n == 0)
00102       return ES_OK;
00103     if (y.min()+c == n) {
00104       assert(y.assigned());
00105       for (int i = n; i--; )
00106         GECODE_ME_CHECK(x[i].one_none(home));
00107       return ES_OK;
00108     }
00109     if (y.max()+c == 0) {
00110       assert(y.assigned());
00111       for (int i = n; i--; )
00112         GECODE_ME_CHECK(x[i].zero_none(home));
00113       return ES_OK;
00114     }
00115     (void) new (home) EqBoolView<XV,YV>(home,x,y,c);
00116     return ES_OK;
00117   }
00118 
00119   template<class XV, class YV>
00120   forceinline
00121   EqBoolView<XV,YV>::EqBoolView(Space& home, bool share, EqBoolView<XV,YV>& p)
00122     : LinBoolView<XV,YV>(home,share,p) {}
00123 
00124   template<class XV, class YV>
00125   Actor*
00126   EqBoolView<XV,YV>::copy(Space& home, bool share) {
00127     return new (home) EqBoolView<XV,YV>(home,share,*this);
00128   }
00129 
00130   template<class XV, class YV>
00131   ExecStatus
00132   EqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) {
00133     int n = x.size();
00134     for (int i = n; i--; )
00135       if (x[i].one()) {
00136         x[i]=x[--n]; c--;
00137       } else if (x[i].zero()) {
00138         x[i]=x[--n];
00139       }
00140     x.size(n);
00141     GECODE_ME_CHECK(y.lq(home,n-c));
00142     GECODE_ME_CHECK(y.gq(home,-c));
00143     if (n == 0)
00144       return ES_SUBSUMED(*this,sizeof(*this));
00145     if (y.min()+c == n) {
00146       assert(y.assigned());
00147       for (int i = n; i--; )
00148         GECODE_ME_CHECK(x[i].one_none(home));
00149       return ES_SUBSUMED(*this,sizeof(*this));
00150     }
00151     if (y.max()+c == 0) {
00152       assert(y.assigned());
00153       for (int i = n; i--; )
00154         GECODE_ME_CHECK(x[i].zero_none(home));
00155       return ES_SUBSUMED(*this,sizeof(*this));
00156     }
00157     if (y.assigned())
00158       GECODE_REWRITE(*this,EqBoolInt<XV>::post(home(*this),x,y.val()+c));
00159     return ES_FIX;
00160   }
00161 
00162 
00163   /*
00164    * Disequality propagator
00165    *
00166    */
00167   template<class XV, class YV>
00168   forceinline
00169   NqBoolView<XV,YV>::NqBoolView(Home home, ViewArray<XV>& x, YV y, int c)
00170     : LinBoolView<XV,YV>(home,x,y,c) {}
00171 
00172   template<class XV, class YV>
00173   ExecStatus
00174   NqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) {
00175     if (y.assigned())
00176       return NqBoolInt<XV>::post(home,x,y.val()+c);
00177     int n = x.size();
00178     for (int i = n; i--; )
00179       if (x[i].one()) {
00180         x[i]=x[--n]; c--;
00181       } else if (x[i].zero()) {
00182         x[i]=x[--n];
00183       }
00184     x.size(n);
00185     if ((n-c < y.min() ) || (-c > y.max()))
00186       return ES_OK;
00187     if (n == 0) {
00188       GECODE_ME_CHECK(y.nq(home,-c));
00189       return ES_OK;
00190     }
00191     if ((n == 1) && y.assigned()) {
00192       if (y.val()+c == 1) {
00193         GECODE_ME_CHECK(x[0].zero_none(home));
00194       } else {
00195         assert(y.val()+c == 0);
00196         GECODE_ME_CHECK(x[0].one_none(home));
00197       }
00198       return ES_OK;
00199     }
00200     (void) new (home) NqBoolView<XV,YV>(home,x,y,c);
00201     return ES_OK;
00202   }
00203 
00204 
00205   template<class XV, class YV>
00206   forceinline
00207   NqBoolView<XV,YV>::NqBoolView(Space& home, bool share, NqBoolView<XV,YV>& p)
00208     : LinBoolView<XV,YV>(home,share,p) {}
00209 
00210   template<class XV, class YV>
00211   Actor*
00212   NqBoolView<XV,YV>::copy(Space& home, bool share) {
00213     return new (home) NqBoolView<XV,YV>(home,share,*this);
00214   }
00215 
00216   template<class XV, class YV>
00217   ExecStatus
00218   NqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) {
00219     int n = x.size();
00220     for (int i = n; i--; )
00221       if (x[i].one()) {
00222         x[i]=x[--n]; c--;
00223       } else if (x[i].zero()) {
00224         x[i]=x[--n];
00225       }
00226     x.size(n);
00227     if ((n-c < y.min() ) || (-c > y.max()))
00228       return ES_SUBSUMED(*this,home);
00229     if (n == 0) {
00230       GECODE_ME_CHECK(y.nq(home,-c));
00231       return ES_SUBSUMED(*this,home);
00232     }
00233     if ((n == 1) && y.assigned()) {
00234       if (y.val()+c == 1) {
00235         GECODE_ME_CHECK(x[0].zero_none(home));
00236       } else {
00237         assert(y.val()+c == 0);
00238         GECODE_ME_CHECK(x[0].one_none(home));
00239       }
00240       return ES_SUBSUMED(*this,sizeof(*this));
00241     }
00242     return ES_FIX;
00243   }
00244 
00245 
00246   /*
00247    * Greater or equal propagator
00248    *
00249    */
00250   template<class XV, class YV>
00251   forceinline
00252   GqBoolView<XV,YV>::GqBoolView(Home home, ViewArray<XV>& x, YV y, int c)
00253     : LinBoolView<XV,YV>(home,x,y,c) {}
00254 
00255   template<class XV, class YV>
00256   ExecStatus
00257   GqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) {
00258     if (y.assigned())
00259       return GqBoolInt<XV>::post(home,x,y.val()+c);
00260     // Eliminate assigned views
00261     int n = x.size();
00262     for (int i = n; i--; )
00263       if (x[i].one()) {
00264         x[i]=x[--n]; c--;
00265       } else if (x[i].zero()) {
00266         x[i]=x[--n];
00267       }
00268     x.size(n);
00269     GECODE_ME_CHECK(y.lq(home,n-c));
00270     if (-c >= y.max())
00271       return ES_OK;
00272     if (y.min()+c == n) {
00273       for (int i = n; i--; )
00274         GECODE_ME_CHECK(x[i].one_none(home));
00275       return ES_OK;
00276     }
00277     (void) new (home) GqBoolView<XV,YV>(home,x,y,c);
00278     return ES_OK;
00279   }
00280 
00281 
00282   template<class XV, class YV>
00283   forceinline
00284   GqBoolView<XV,YV>::GqBoolView(Space& home, bool share, GqBoolView<XV,YV>& p)
00285     : LinBoolView<XV,YV>(home,share,p) {}
00286 
00287   template<class XV, class YV>
00288   Actor*
00289   GqBoolView<XV,YV>::copy(Space& home, bool share) {
00290     return new (home) GqBoolView<XV,YV>(home,share,*this);
00291   }
00292 
00293   template<class XV, class YV>
00294   ExecStatus
00295   GqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) {
00296     int n = x.size();
00297     for (int i = n; i--; )
00298       if (x[i].one()) {
00299         x[i]=x[--n]; c--;
00300       } else if (x[i].zero()) {
00301         x[i]=x[--n];
00302       }
00303     x.size(n);
00304     GECODE_ME_CHECK(y.lq(home,n-c));
00305     if (-c >= y.max())
00306       return ES_SUBSUMED(*this,home);
00307     if (y.min()+c == n) {
00308       for (int i = n; i--; )
00309         GECODE_ME_CHECK(x[i].one_none(home));
00310       return ES_SUBSUMED(*this,home);
00311     }
00312     if (y.assigned())
00313       GECODE_REWRITE(*this,GqBoolInt<XV>::post(home(*this),x,y.val()+c));
00314     return ES_FIX;
00315   }
00316 
00317 }}}
00318 
00319 // STATISTICS: int-prop
00320