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