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