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

bool-scale.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, 2006
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    * Array of scale Boolean views
00038    *
00039    */
00040   forceinline
00041   ScaleBoolArray::ScaleBoolArray(void) {}
00042   forceinline
00043   ScaleBoolArray::ScaleBoolArray(Space& home, int n) {
00044     if (n > 0) {
00045       _fst = home.alloc<ScaleBool>(n);
00046       _lst = _fst+n;
00047     } else {
00048       _fst = _lst = NULL;
00049     }
00050   }
00051   forceinline void
00052   ScaleBoolArray::subscribe(Space& home, Propagator& p) {
00053     for (ScaleBool* f = _fst; f < _lst; f++)
00054       f->x.subscribe(home,p,PC_BOOL_VAL);
00055   }
00056   forceinline void
00057   ScaleBoolArray::cancel(Space& home, Propagator& p) {
00058     for (ScaleBool* f = _fst; f < _lst; f++)
00059       f->x.cancel(home,p,PC_BOOL_VAL);
00060   }
00061   forceinline void
00062   ScaleBoolArray::reschedule(Space& home, Propagator& p) {
00063     for (ScaleBool* f = _fst; f < _lst; f++)
00064       f->x.reschedule(home,p,PC_BOOL_VAL);
00065   }
00066   forceinline void
00067   ScaleBoolArray::update(Space& home, ScaleBoolArray& sba) {
00068     int n = static_cast<int>(sba._lst - sba._fst);
00069     if (n > 0) {
00070       _fst = home.alloc<ScaleBool>(n);
00071       _lst = _fst+n;
00072       for (int i=0; i<n; i++) {
00073         _fst[i].a = sba._fst[i].a;
00074         _fst[i].x.update(home,sba._fst[i].x);
00075       }
00076     } else {
00077       _fst = _lst = NULL;
00078     }
00079   }
00080   forceinline ScaleBool*
00081   ScaleBoolArray::fst(void) const {
00082     return _fst;
00083   }
00084   forceinline ScaleBool*
00085   ScaleBoolArray::lst(void) const {
00086     return _lst;
00087   }
00088   forceinline void
00089   ScaleBoolArray::fst(ScaleBool* f) {
00090     _fst = f;
00091   }
00092   forceinline void
00093   ScaleBoolArray::lst(ScaleBool* l) {
00094     _lst = l;
00095   }
00096   forceinline bool
00097   ScaleBoolArray::empty(void) const {
00098     return _fst == _lst;
00099   }
00100   forceinline int
00101   ScaleBoolArray::size(void) const {
00102     return static_cast<int>(_lst - _fst);
00103   }
00104   forceinline bool
00105   ScaleBoolArray::ScaleDec::operator ()(const ScaleBool& x,
00106                                        const ScaleBool& y) {
00107     return x.a > y.a;
00108   }
00109 
00110   inline void
00111   ScaleBoolArray::sort(void) {
00112     ScaleDec scale_dec;
00113     Support::quicksort<ScaleBool,ScaleDec>(fst(), size(), scale_dec);
00114   }
00115 
00116 
00117   /*
00118    * Empty array of scale Boolean views
00119    *
00120    */
00121   forceinline
00122   EmptyScaleBoolArray::EmptyScaleBoolArray(void) {}
00123   forceinline
00124   EmptyScaleBoolArray::EmptyScaleBoolArray(Space&, int) {}
00125   forceinline void
00126   EmptyScaleBoolArray::subscribe(Space&, Propagator&) {}
00127   forceinline void
00128   EmptyScaleBoolArray::cancel(Space&, Propagator&) {}
00129   forceinline void
00130   EmptyScaleBoolArray::reschedule(Space&, Propagator&) {}
00131   forceinline void
00132   EmptyScaleBoolArray::update(Space&, EmptyScaleBoolArray&) {}
00133   forceinline ScaleBool*
00134   EmptyScaleBoolArray::fst(void) const { return NULL; }
00135   forceinline ScaleBool*
00136   EmptyScaleBoolArray::lst(void) const { return NULL; }
00137   forceinline void
00138   EmptyScaleBoolArray::fst(ScaleBool*) {}
00139   forceinline void
00140   EmptyScaleBoolArray::lst(ScaleBool*) {}
00141   forceinline bool
00142   EmptyScaleBoolArray::empty(void) const { return true; }
00143   forceinline int
00144   EmptyScaleBoolArray::size(void) const { return 0; }
00145   forceinline void
00146   EmptyScaleBoolArray::sort(void) {}
00147 
00148 
00149   /*
00150    * Base-class for Boolean constraints with coefficients
00151    *
00152    */
00153 
00154   template<class SBAP, class SBAN, class VX, PropCond pcx>
00155   forceinline
00156   LinBoolScale<SBAP,SBAN,VX,pcx>::LinBoolScale(Home home,
00157                                                SBAP& p0, SBAN& n0,
00158                                                VX x0, int c0)
00159     : Propagator(home), p(p0), n(n0), x(x0), c(c0) {
00160     x.subscribe(home,*this,pcx);
00161     p.subscribe(home,*this);
00162     n.subscribe(home,*this);
00163   }
00164 
00165   template<class SBAP, class SBAN, class VX, PropCond pcx>
00166   PropCost
00167   LinBoolScale<SBAP,SBAN,VX,pcx>::cost(const Space&,
00168                                        const ModEventDelta&) const {
00169     return PropCost::linear(PropCost::LO, p.size() + n.size());
00170   }
00171 
00172   template<class SBAP, class SBAN, class VX, PropCond pcx>
00173   void
00174   LinBoolScale<SBAP,SBAN,VX,pcx>::reschedule(Space& home) {
00175     x.reschedule(home,*this,pcx);
00176     p.reschedule(home,*this);
00177     n.reschedule(home,*this);
00178   }
00179 
00180   template<class SBAP, class SBAN, class VX, PropCond pcx>
00181   forceinline size_t
00182   LinBoolScale<SBAP,SBAN,VX,pcx>::dispose(Space& home) {
00183     x.cancel(home,*this,pcx);
00184     p.cancel(home,*this);
00185     n.cancel(home,*this);
00186     (void) Propagator::dispose(home);
00187     return sizeof(*this);
00188   }
00189 
00190   template<class SBAP, class SBAN, class VX, PropCond pcx>
00191   forceinline
00192   LinBoolScale<SBAP,SBAN,VX,pcx>::LinBoolScale(Space& home,
00193                                                Propagator& pr,
00194                                                SBAP& p0, SBAN& n0,
00195                                                VX x0, int c0)
00196     : Propagator(home,pr), c(c0) {
00197     x.update(home,x0);
00198     p.update(home,p0);
00199     n.update(home,n0);
00200   }
00201 
00202   /*
00203    * Boolean equality with coefficients
00204    *
00205    */
00206 
00207   template<class SBAP, class SBAN, class VX>
00208   forceinline
00209   EqBoolScale<SBAP,SBAN,VX>::EqBoolScale(Home home,
00210                                          SBAP& p, SBAN& n,
00211                                          VX x, int c)
00212     : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,p,n,x,c) {}
00213 
00214   template<class SBAP, class SBAN, class VX>
00215   forceinline
00216   EqBoolScale<SBAP,SBAN,VX>::EqBoolScale(Space& home,
00217                                          Propagator& pr,
00218                                          SBAP& p, SBAN& n,
00219                                          VX x, int c)
00220     : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,pr,p,n,x,c) {}
00221 
00222   template<class SBAP, class SBAN, class VX>
00223   Actor*
00224   EqBoolScale<SBAP,SBAN,VX>::copy(Space& home) {
00225     if (p.empty()) {
00226       EmptyScaleBoolArray ep;
00227       if (x.assigned()) {
00228         ZeroIntView z;
00229         return new (home) EqBoolScale<EmptyScaleBoolArray,SBAN,ZeroIntView>
00230           (home,*this,ep,n,z,c+x.val());
00231       } else {
00232         return new (home) EqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00233           (home,*this,ep,n,x,c);
00234       }
00235     } else if (n.empty()) {
00236       EmptyScaleBoolArray en;
00237       if (x.assigned()) {
00238         ZeroIntView z;
00239         return new (home) EqBoolScale<SBAP,EmptyScaleBoolArray,ZeroIntView>
00240           (home,*this,p,en,z,c+x.val());
00241       } else {
00242         return new (home) EqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00243           (home,*this,p,en,x,c);
00244       }
00245     } else {
00246       return new (home) EqBoolScale<SBAP,SBAN,VX>(home,*this,p,n,x,c);
00247     }
00248   }
00249 
00250   template<class SBAP, class SBAN, class VX>
00251   ExecStatus
00252   EqBoolScale<SBAP,SBAN,VX>::propagate(Space& home, const ModEventDelta& med) {
00253     int sl_p = 0; // Lower bound, computed positive
00254     int su_n = 0; // Upper bound, computed negative
00255     if (BoolView::me(med) == ME_BOOL_VAL) {
00256       // Eliminate assigned positive views while keeping order
00257       {
00258         // Skip not assigned views
00259         ScaleBool* f = p.fst();
00260         ScaleBool* l = p.lst();
00261         while ((f < l) && f->x.none()) {
00262           su_n += f->a; f++;
00263         }
00264         // Copy unassigned views to t
00265         ScaleBool* t = f;
00266         while (f < l) {
00267           if (f->x.one()) {
00268             c -= f->a;
00269           } else if (f->x.none()) {
00270             su_n += f->a; *t = *f; t++;
00271           }
00272           f++;
00273         }
00274         p.lst(t);
00275       }
00276       // Eliminate assigned negative views while keeping order
00277       {
00278         // Skip not assigned views
00279         ScaleBool* f = n.fst();
00280         ScaleBool* l = n.lst();
00281         while ((f < l) && f->x.none()) {
00282           sl_p += f->a; f++;
00283         }
00284         // Copy unassigned views to t
00285         ScaleBool* t = f;
00286         while (f < l) {
00287           if (f->x.one()) {
00288             c += f->a;
00289           } else if (f->x.none()) {
00290             sl_p += f->a; *t = *f; t++;
00291           }
00292           f++;
00293         }
00294         n.lst(t);
00295       }
00296     } else {
00297       for (ScaleBool* f=p.fst(); f<p.lst(); f++)
00298         su_n += f->a;
00299       for (ScaleBool* f=n.fst(); f<n.lst(); f++)
00300         sl_p += f->a;
00301     }
00302 
00303     if (p.empty() && n.empty()) {
00304       GECODE_ME_CHECK(x.eq(home,-c));
00305       return home.ES_SUBSUMED(*this);
00306     }
00307 
00308     sl_p += x.max() + c;
00309     su_n -= x.min() + c;
00310 
00311     const int MOD_SL = 1 << 0;
00312     const int MOD_SU = 1 << 1;
00313 
00314     int mod = MOD_SL | MOD_SU;
00315 
00316     do {
00317       if ((mod & MOD_SL) != 0) {
00318         mod -= MOD_SL;
00319         // Propagate lower bound for positive Boolean views
00320         {
00321           ScaleBool* f=p.fst();
00322           for (ScaleBool* l=p.lst(); (f < l) && (f->a > sl_p); f++) {
00323             GECODE_ME_CHECK(f->x.zero_none(home));
00324             su_n -= f->a;
00325           }
00326           if (f > p.fst()) {
00327             p.fst(f); mod |= MOD_SU;
00328           }
00329         }
00330         // Propagate lower bound for negative Boolean views
00331         {
00332           ScaleBool* f=n.fst();
00333           for (ScaleBool* l=n.lst(); (f < l) && (f->a > sl_p); f++) {
00334             GECODE_ME_CHECK(f->x.one_none(home)); c += f->a;
00335             su_n -= f->a;
00336           }
00337           if (f > n.fst()) {
00338             n.fst(f); mod |= MOD_SU;
00339           }
00340         }
00341         // Propagate lower bound for integer view
00342         {
00343           const int x_min = x.min();
00344           ModEvent me = x.gq(home,x.max() - sl_p);
00345           if (me_failed(me))
00346             return ES_FAILED;
00347           if (me_modified(me)) {
00348             su_n -= x.min() - x_min;
00349             mod |= MOD_SU;
00350           }
00351         }
00352       }
00353       if ((mod & MOD_SU) != 0) {
00354         mod -= MOD_SU;
00355         // Propagate upper bound for positive Boolean views
00356         {
00357           ScaleBool* f=p.fst();
00358           for (ScaleBool* l=p.lst(); (f < l) && (f->a > su_n); f++) {
00359             GECODE_ME_CHECK(f->x.one_none(home)); c -= f->a;
00360             sl_p -= f->a;
00361           }
00362           if (f > p.fst()) {
00363             p.fst(f); mod |= MOD_SL;;
00364           }
00365         }
00366         // Propagate upper bound for negative Boolean views
00367         {
00368           ScaleBool* f=n.fst();
00369           for (ScaleBool* l=n.lst(); (f < l) && (f->a > su_n); f++) {
00370             GECODE_ME_CHECK(f->x.zero_none(home));
00371             sl_p -= f->a;
00372           }
00373           if (f > n.fst()) {
00374             n.fst(f); mod |= MOD_SL;;
00375           }
00376         }
00377         // Propagate upper bound for integer view
00378         {
00379           const int x_max = x.max();
00380           ModEvent me = x.lq(home,x.min() + su_n);
00381           if (me_failed(me))
00382             return ES_FAILED;
00383           if (me_modified(me)) {
00384             sl_p += x.max() - x_max;
00385             mod |= MOD_SL;;
00386           }
00387         }
00388       }
00389     } while (mod != 0);
00390 
00391     return (sl_p == -su_n) ? home.ES_SUBSUMED(*this) : ES_FIX;
00392   }
00393 
00394 
00395 
00396   template<class SBAP, class SBAN, class VX>
00397   ExecStatus
00398   EqBoolScale<SBAP,SBAN,VX>::post(Home home,
00399                                   SBAP& p, SBAN& n, VX x, int c) {
00400     p.sort(); n.sort();
00401     if (p.empty()) {
00402       EmptyScaleBoolArray ep;
00403       (void) new (home) EqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00404         (home,ep,n,x,c);
00405     } else if (n.empty()) {
00406       EmptyScaleBoolArray en;
00407       (void) new (home) EqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00408         (home,p,en,x,c);
00409     } else {
00410       (void) new (home) EqBoolScale<SBAP,SBAN,VX>
00411         (home,p,n,x,c);
00412     }
00413     return ES_OK;
00414   }
00415 
00416 
00417   /*
00418    * Boolean inequality with coefficients
00419    *
00420    */
00421 
00422   template<class SBAP, class SBAN, class VX>
00423   forceinline
00424   LqBoolScale<SBAP,SBAN,VX>::LqBoolScale(Home home,
00425                                          SBAP& p, SBAN& n,
00426                                          VX x, int c)
00427     : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,p,n,x,c) {}
00428 
00429   template<class SBAP, class SBAN, class VX>
00430   forceinline
00431   LqBoolScale<SBAP,SBAN,VX>::LqBoolScale(Space& home,
00432                                          Propagator& pr,
00433                                          SBAP& p, SBAN& n,
00434                                          VX x, int c)
00435     : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,pr,p,n,x,c) {}
00436 
00437   template<class SBAP, class SBAN, class VX>
00438   Actor*
00439   LqBoolScale<SBAP,SBAN,VX>::copy(Space& home) {
00440     if (p.empty()) {
00441       EmptyScaleBoolArray ep;
00442       if (x.assigned()) {
00443         ZeroIntView z;
00444         return new (home) LqBoolScale<EmptyScaleBoolArray,SBAN,ZeroIntView>
00445           (home,*this,ep,n,z,c+x.val());
00446       } else {
00447         return new (home) LqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00448           (home,*this,ep,n,x,c);
00449       }
00450     } else if (n.empty()) {
00451       EmptyScaleBoolArray en;
00452       if (x.assigned()) {
00453         ZeroIntView z;
00454         return new (home) LqBoolScale<SBAP,EmptyScaleBoolArray,ZeroIntView>
00455           (home,*this,p,en,z,c+x.val());
00456       } else {
00457         return new (home) LqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00458           (home,*this,p,en,x,c);
00459       }
00460     } else {
00461       return new (home) LqBoolScale<SBAP,SBAN,VX>(home,*this,p,n,x,c);
00462     }
00463   }
00464 
00465   template<class SBAP, class SBAN, class VX>
00466   ExecStatus
00467   LqBoolScale<SBAP,SBAN,VX>::propagate(Space& home, const ModEventDelta& med) {
00468     int sl = 0;
00469     if (BoolView::me(med) == ME_BOOL_VAL) {
00470       // Eliminate assigned positive views while keeping order
00471       {
00472         // Skip not assigned views
00473         ScaleBool* f = p.fst();
00474         ScaleBool* l = p.lst();
00475         while ((f < l) && f->x.none())
00476           f++;
00477         // Copy unassigned views to t
00478         ScaleBool* t = f;
00479         while (f < l) {
00480           if (f->x.one()) {
00481             c -= f->a;
00482           } else if (f->x.none()) {
00483             *t = *f; t++;
00484           }
00485           f++;
00486         }
00487         p.lst(t);
00488       }
00489       // Eliminate assigned negative views while keeping order
00490       {
00491         // Skip not assigned views
00492         ScaleBool* f = n.fst();
00493         ScaleBool* l = n.lst();
00494         while ((f < l) && f->x.none()) {
00495           sl += f->a; f++;
00496         }
00497         // Copy unassigned views to t
00498         ScaleBool* t = f;
00499         while (f < l) {
00500           if (f->x.one()) {
00501             c += f->a;
00502           } else if (f->x.none()) {
00503             sl += f->a; *t = *f; t++;
00504           }
00505           f++;
00506         }
00507         n.lst(t);
00508       }
00509     } else {
00510       for (ScaleBool* f=n.fst(); f<n.lst(); f++)
00511         sl += f->a;
00512     }
00513 
00514     sl += x.max() + c;
00515 
00516     // Propagate upper bound for positive Boolean views
00517     {
00518       ScaleBool* f=p.fst();
00519       for (ScaleBool* l=p.lst(); (f < l) && (f->a > sl); f++)
00520         GECODE_ME_CHECK(f->x.zero_none(home));
00521       p.fst(f);
00522     }
00523     // Propagate lower bound for negative Boolean views
00524     {
00525       ScaleBool* f=n.fst();
00526       for (ScaleBool* l=n.lst(); (f < l) && (f->a > sl); f++) {
00527         c += f->a;
00528         GECODE_ME_CHECK(f->x.one_none(home));
00529       }
00530       n.fst(f);
00531     }
00532     ExecStatus es = ES_FIX;
00533     // Propagate lower bound for integer view
00534     {
00535       const int slx = x.max() - sl;
00536       ModEvent me = x.gq(home,slx);
00537       if (me_failed(me))
00538         return ES_FAILED;
00539       if (me_modified(me) && (slx != x.min()))
00540         es = ES_NOFIX;
00541     }
00542 
00543     if (p.empty() && n.empty())
00544       return home.ES_SUBSUMED(*this);
00545 
00546     return es;
00547   }
00548 
00549 
00550 
00551   template<class SBAP, class SBAN, class VX>
00552   ExecStatus
00553   LqBoolScale<SBAP,SBAN,VX>::post(Home home,
00554                                   SBAP& p, SBAN& n, VX x, int c) {
00555     p.sort(); n.sort();
00556     if (p.empty()) {
00557       EmptyScaleBoolArray ep;
00558       (void) new (home) LqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00559         (home,ep,n,x,c);
00560     } else if (n.empty()) {
00561       EmptyScaleBoolArray en;
00562       (void) new (home) LqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00563         (home,p,en,x,c);
00564     } else {
00565       (void) new (home) LqBoolScale<SBAP,SBAN,VX>
00566         (home,p,n,x,c);
00567     }
00568     return ES_OK;
00569   }
00570 
00571   /*
00572    * Boolean disequality with coefficients
00573    *
00574    */
00575 
00576   template<class SBAP, class SBAN, class VX>
00577   forceinline
00578   NqBoolScale<SBAP,SBAN,VX>::NqBoolScale(Home home,
00579                                          SBAP& p, SBAN& n,
00580                                          VX x, int c)
00581     : LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>(home,p,n,x,c) {}
00582 
00583   template<class SBAP, class SBAN, class VX>
00584   forceinline
00585   NqBoolScale<SBAP,SBAN,VX>::NqBoolScale(Space& home,
00586                                          Propagator& pr,
00587                                          SBAP& p, SBAN& n,
00588                                          VX x, int c)
00589     : LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>(home,pr,p,n,x,c) {}
00590 
00591   template<class SBAP, class SBAN, class VX>
00592   Actor*
00593   NqBoolScale<SBAP,SBAN,VX>::copy(Space& home) {
00594     if (p.empty()) {
00595       EmptyScaleBoolArray ep;
00596       if (x.assigned()) {
00597         ZeroIntView z;
00598         return new (home) NqBoolScale<EmptyScaleBoolArray,SBAN,ZeroIntView>
00599           (home,*this,ep,n,z,c+x.val());
00600       } else {
00601         return new (home) NqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00602           (home,*this,ep,n,x,c);
00603       }
00604     } else if (n.empty()) {
00605       EmptyScaleBoolArray en;
00606       if (x.assigned()) {
00607         ZeroIntView z;
00608         return new (home) NqBoolScale<SBAP,EmptyScaleBoolArray,ZeroIntView>
00609           (home,*this,p,en,z,c+x.val());
00610       } else {
00611         return new (home) NqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00612           (home,*this,p,en,x,c);
00613       }
00614     } else {
00615       return new (home) NqBoolScale<SBAP,SBAN,VX>(home,*this,p,n,x,c);
00616     }
00617   }
00618 
00619   template<class SBAP, class SBAN, class VX>
00620   ExecStatus
00621   NqBoolScale<SBAP,SBAN,VX>::propagate(Space& home, const ModEventDelta& med) {
00622     if (BoolView::me(med) == ME_BOOL_VAL) {
00623       // Eliminate assigned positive views
00624       {
00625         ScaleBool* f = p.fst();
00626         ScaleBool* t = f;
00627         ScaleBool* l = p.lst();
00628         while (f < l) {
00629           if (f->x.one()) {
00630             c -= f->a; *f = *(t++);
00631           } else if (f->x.zero()) {
00632             *f = *(t++);
00633           }
00634           f++;
00635         }
00636         p.fst(t);
00637       }
00638       // Eliminate assigned negative views
00639       {
00640         ScaleBool* f = n.fst();
00641         ScaleBool* t = f;
00642         ScaleBool* l = n.lst();
00643         while (f < l) {
00644           if (f->x.one()) {
00645             c += f->a; *f = *(t++);
00646           } else if (f->x.zero()) {
00647             *f = *(t++);
00648           }
00649           f++;
00650         }
00651         n.fst(t);
00652       }
00653     }
00654 
00655     if (p.empty() && n.empty()) {
00656       GECODE_ME_CHECK(x.nq(home,-c));
00657       return home.ES_SUBSUMED(*this);
00658     }
00659 
00660     if (x.assigned()) {
00661       int r = x.val()+c;
00662       if (p.empty() && (n.size() == 1)) {
00663         if (r == -n.fst()->a) {
00664           GECODE_ME_CHECK(n.fst()->x.zero_none(home));
00665         } else if (r == 0) {
00666           GECODE_ME_CHECK(n.fst()->x.one_none(home));
00667         }
00668         return home.ES_SUBSUMED(*this);
00669       }
00670       if ((p.size() == 1) && n.empty()) {
00671         if (r == p.fst()->a) {
00672           GECODE_ME_CHECK(p.fst()->x.zero_none(home));
00673         } else if (r == 0) {
00674           GECODE_ME_CHECK(p.fst()->x.one_none(home));
00675         }
00676         return home.ES_SUBSUMED(*this);
00677       }
00678     }
00679     return ES_FIX;
00680   }
00681 
00682 
00683 
00684   template<class SBAP, class SBAN, class VX>
00685   ExecStatus
00686   NqBoolScale<SBAP,SBAN,VX>::post(Home home,
00687                                   SBAP& p, SBAN& n, VX x, int c) {
00688     if (p.empty()) {
00689       EmptyScaleBoolArray ep;
00690       (void) new (home) NqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00691         (home,ep,n,x,c);
00692     } else if (n.empty()) {
00693       EmptyScaleBoolArray en;
00694       (void) new (home) NqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00695         (home,p,en,x,c);
00696     } else {
00697       (void) new (home) NqBoolScale<SBAP,SBAN,VX>
00698         (home,p,n,x,c);
00699     }
00700     return ES_OK;
00701   }
00702 
00703 }}}
00704 
00705 // STATISTICS: int-prop
00706