Generated on Tue May 22 09:40:02 2018 for Gecode by doxygen 1.6.3

int-nary.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, 2003
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 #include <gecode/int/linear/int-noview.hpp>
00035 
00036 namespace Gecode { namespace Int { namespace Linear {
00037 
00042   template<class P, class N>
00043   forceinline bool
00044   isunit(ViewArray<P>&, ViewArray<N>&) { return false; }
00045   template<>
00046   forceinline bool
00047   isunit(ViewArray<IntView>&, ViewArray<IntView>&) { return true; }
00048   template<>
00049   forceinline bool
00050   isunit(ViewArray<IntView>&, ViewArray<NoView>&) { return true; }
00051   template<>
00052   forceinline bool
00053   isunit(ViewArray<NoView>&, ViewArray<IntView>&) { return true; }
00054 
00055   /*
00056    * Linear propagators
00057    *
00058    */
00059   template<class Val, class P, class N, PropCond pc>
00060   forceinline
00061   Lin<Val,P,N,pc>::Lin(Home home, ViewArray<P>& x0, ViewArray<N>& y0, Val c0)
00062     : Propagator(home), x(x0), y(y0), c(c0) {
00063     x.subscribe(home,*this,pc);
00064     y.subscribe(home,*this,pc);
00065   }
00066 
00067   template<class Val, class P, class N, PropCond pc>
00068   forceinline
00069   Lin<Val,P,N,pc>::Lin(Space& home, Lin<Val,P,N,pc>& p)
00070     : Propagator(home,p), c(p.c) {
00071     x.update(home,p.x);
00072     y.update(home,p.y);
00073   }
00074 
00075   template<class Val, class P, class N, PropCond pc>
00076   PropCost
00077   Lin<Val,P,N,pc>::cost(const Space&, const ModEventDelta&) const {
00078     return PropCost::linear(PropCost::LO, x.size()+y.size());
00079   }
00080 
00081   template<class Val, class P, class N, PropCond pc>
00082   void
00083   Lin<Val,P,N,pc>::reschedule(Space& home) {
00084     x.reschedule(home,*this,pc);
00085     y.reschedule(home,*this,pc);
00086   }
00087 
00088   template<class Val, class P, class N, PropCond pc>
00089   forceinline size_t
00090   Lin<Val,P,N,pc>::dispose(Space& home) {
00091     x.cancel(home,*this,pc);
00092     y.cancel(home,*this,pc);
00093     (void) Propagator::dispose(home);
00094     return sizeof(*this);
00095   }
00096 
00097   /*
00098    * Reified linear propagators
00099    *
00100    */
00101   template<class Val, class P, class N, PropCond pc, class Ctrl>
00102   forceinline
00103   ReLin<Val,P,N,pc,Ctrl>::ReLin
00104   (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b0)
00105     : Lin<Val,P,N,pc>(home,x,y,c), b(b0) {
00106     b.subscribe(home,*this,PC_INT_VAL);
00107   }
00108 
00109   template<class Val, class P, class N, PropCond pc, class Ctrl>
00110   forceinline
00111   ReLin<Val,P,N,pc,Ctrl>::ReLin
00112   (Space& home, ReLin<Val,P,N,pc,Ctrl>& p)
00113     : Lin<Val,P,N,pc>(home,p) {
00114     b.update(home,p.b);
00115   }
00116 
00117   template<class Val, class P, class N, PropCond pc, class Ctrl>
00118   void
00119   ReLin<Val,P,N,pc,Ctrl>::reschedule(Space& home) {
00120     x.reschedule(home,*this,pc);
00121     y.reschedule(home,*this,pc);
00122     b.reschedule(home,*this,PC_INT_VAL);
00123   }
00124 
00125   template<class Val, class P, class N, PropCond pc, class Ctrl>
00126   forceinline size_t
00127   ReLin<Val,P,N,pc,Ctrl>::dispose(Space& home) {
00128     b.cancel(home,*this,PC_BOOL_VAL);
00129     (void) Lin<Val,P,N,pc>::dispose(home);
00130     return sizeof(*this);
00131   }
00132 
00133   /*
00134    * Computing bounds
00135    *
00136    */
00137 
00138   template<class Val, class View>
00139   void
00140   bounds_p(ModEventDelta med, ViewArray<View>& x, Val& c, Val& sl, Val& su) {
00141     int n = x.size();
00142     if (IntView::me(med) == ME_INT_VAL) {
00143       for (int i = n; i--; ) {
00144         Val m = x[i].min();
00145         if (x[i].assigned()) {
00146           c -= m; x[i] = x[--n];
00147         } else {
00148           sl -= m; su -= x[i].max();
00149         }
00150       }
00151       x.size(n);
00152     } else {
00153       for (int i = n; i--; ) {
00154         sl -= x[i].min(); su -= x[i].max();
00155       }
00156     }
00157   }
00158 
00159   template<class Val, class View>
00160   void
00161   bounds_n(ModEventDelta med, ViewArray<View>& y, Val& c, Val& sl, Val& su) {
00162     int n = y.size();
00163     if (IntView::me(med) == ME_INT_VAL) {
00164       for (int i = n; i--; ) {
00165         Val m = y[i].max();
00166         if (y[i].assigned()) {
00167           c += m; y[i] = y[--n];
00168         } else {
00169           sl += m; su += y[i].min();
00170         }
00171       }
00172       y.size(n);
00173     } else {
00174       for (int i = n; i--; ) {
00175         sl += y[i].max(); su += y[i].min();
00176       }
00177     }
00178   }
00179 
00180 
00181   template<class Val, class P, class N>
00182   ExecStatus
00183   prop_bnd(Space& home, ModEventDelta med, Propagator& p,
00184            ViewArray<P>& x, ViewArray<N>& y, Val& c) {
00185     // Eliminate singletons
00186     Val sl = 0;
00187     Val su = 0;
00188 
00189     bounds_p<Val,P>(med, x, c, sl, su);
00190     bounds_n<Val,N>(med, y, c, sl, su);
00191 
00192     if ((IntView::me(med) == ME_INT_VAL) && ((x.size() + y.size()) <= 1)) {
00193       if (x.size() == 1) {
00194         GECODE_ME_CHECK(x[0].eq(home,c));
00195         return home.ES_SUBSUMED(p);
00196       }
00197       if (y.size() == 1) {
00198         GECODE_ME_CHECK(y[0].eq(home,-c));
00199         return home.ES_SUBSUMED(p);
00200       }
00201       return (c == static_cast<Val>(0)) ?
00202         home.ES_SUBSUMED(p) : ES_FAILED;
00203     }
00204 
00205     sl += c; su += c;
00206 
00207     const int mod_sl = 1;
00208     const int mod_su = 2;
00209 
00210     int mod = mod_sl | mod_su;
00211 
00212     do {
00213       if (mod & mod_sl) {
00214         mod -= mod_sl;
00215         // Propagate upper bound for positive variables
00216         for (int i = x.size(); i--; ) {
00217           const Val xi_max = x[i].max();
00218           ModEvent me = x[i].lq(home,sl + x[i].min());
00219           if (me_failed(me))
00220             return ES_FAILED;
00221           if (me_modified(me)) {
00222             su += xi_max - x[i].max();
00223             mod |= mod_su;
00224           }
00225         }
00226         // Propagate lower bound for negative variables
00227         for (int i = y.size(); i--; ) {
00228           const Val yi_min = y[i].min();
00229           ModEvent me = y[i].gq(home,y[i].max() - sl);
00230           if (me_failed(me))
00231             return ES_FAILED;
00232           if (me_modified(me)) {
00233             su += y[i].min() - yi_min;
00234             mod |= mod_su;
00235           }
00236         }
00237       }
00238       if (mod & mod_su) {
00239         mod -= mod_su;
00240         // Propagate lower bound for positive variables
00241         for (int i = x.size(); i--; ) {
00242           const Val xi_min = x[i].min();
00243           ModEvent me = x[i].gq(home,su + x[i].max());
00244           if (me_failed(me))
00245             return ES_FAILED;
00246           if (me_modified(me)) {
00247             sl += xi_min - x[i].min();
00248             mod |= mod_sl;
00249           }
00250         }
00251         // Propagate upper bound for negative variables
00252         for (int i = y.size(); i--; ) {
00253           const Val yi_max = y[i].max();
00254           ModEvent me = y[i].lq(home,y[i].min() - su);
00255           if (me_failed(me))
00256             return ES_FAILED;
00257           if (me_modified(me)) {
00258             sl += y[i].max() - yi_max;
00259             mod |= mod_sl;
00260           }
00261         }
00262       }
00263     } while (mod);
00264 
00265     return (sl == su) ? home.ES_SUBSUMED(p) : ES_FIX;
00266   }
00267 
00268   /*
00269    * Bound consistent linear equation
00270    *
00271    */
00272 
00273   template<class Val, class P, class N>
00274   forceinline
00275   Eq<Val,P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00276     : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00277 
00278   template<class Val, class P, class N>
00279   ExecStatus
00280   Eq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00281     ViewArray<NoView> nva;
00282     if (y.size() == 0) {
00283       (void) new (home) Eq<Val,P,NoView>(home,x,nva,c);
00284     } else if (x.size() == 0) {
00285       (void) new (home) Eq<Val,N,NoView>(home,y,nva,-c);
00286     } else {
00287       (void) new (home) Eq<Val,P,N>(home,x,y,c);
00288     }
00289     return ES_OK;
00290   }
00291 
00292 
00293   template<class Val, class P, class N>
00294   forceinline
00295   Eq<Val,P,N>::Eq(Space& home, Eq<Val,P,N>& p)
00296     : Lin<Val,P,N,PC_INT_BND>(home,p) {}
00297 
00302   template<class Val, class P, class N>
00303   forceinline Actor*
00304   eqtobin(Space&, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00305     return NULL;
00306   }
00307   template<class Val>
00308   forceinline Actor*
00309   eqtobin(Space& home, Propagator& p,
00310           ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00311     assert(x.size() == 2);
00312     return new (home) EqBin<Val,IntView,IntView>
00313       (home,p,x[0],x[1],c);
00314   }
00315   template<class Val>
00316   forceinline Actor*
00317   eqtobin(Space& home, Propagator& p,
00318           ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00319     assert(y.size() == 2);
00320     return new (home) EqBin<Val,IntView,IntView>
00321       (home,p,y[0],y[1],-c);
00322   }
00323   template<class Val>
00324   forceinline Actor*
00325   eqtobin(Space& home, Propagator& p,
00326           ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00327     if (x.size() == 2)
00328       return new (home) EqBin<Val,IntView,IntView>
00329         (home,p,x[0],x[1],c);
00330     if (x.size() == 1)
00331       return new (home) EqBin<Val,IntView,MinusView>
00332         (home,p,x[0],MinusView(y[0]),c);
00333     return new (home) EqBin<Val,IntView,IntView>
00334       (home,p,y[0],y[1],-c);
00335   }
00336 
00341   template<class Val, class P, class N>
00342   forceinline Actor*
00343   eqtoter(Space&, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00344     return NULL;
00345   }
00346   template<class Val>
00347   forceinline Actor*
00348   eqtoter(Space& home, Propagator& p,
00349           ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00350     assert(x.size() == 3);
00351     return new (home) EqTer<Val,IntView,IntView,IntView>
00352       (home,p,x[0],x[1],x[2],c);
00353   }
00354   template<class Val>
00355   forceinline Actor*
00356   eqtoter(Space& home, Propagator& p,
00357           ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00358     assert(y.size() == 3);
00359     return new (home) EqTer<Val,IntView,IntView,IntView>
00360       (home,p,y[0],y[1],y[2],-c);
00361   }
00362   template<class Val>
00363   forceinline Actor*
00364   eqtoter(Space& home, Propagator& p,
00365           ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00366     if (x.size() == 3)
00367       return new (home) EqTer<Val,IntView,IntView,IntView>
00368         (home,p,x[0],x[1],x[2],c);
00369     if (x.size() == 2)
00370       return new (home) EqTer<Val,IntView,IntView,MinusView>
00371         (home,p,x[0],x[1],MinusView(y[0]),c);
00372     if (x.size() == 1)
00373       return new (home) EqTer<Val,IntView,IntView,MinusView>
00374         (home,p,y[0],y[1],MinusView(x[0]),-c);
00375     return new (home) EqTer<Val,IntView,IntView,IntView>
00376       (home,p,y[0],y[1],y[2],-c);
00377   }
00378 
00379   template<class Val, class P, class N>
00380   Actor*
00381   Eq<Val,P,N>::copy(Space& home) {
00382     if (isunit(x,y)) {
00383       // Check whether rewriting is possible
00384       if (x.size() + y.size() == 2)
00385         return eqtobin(home,*this,x,y,c);
00386       if (x.size() + y.size() == 3)
00387         return eqtoter(home,*this,x,y,c);
00388     }
00389     return new (home) Eq<Val,P,N>(home,*this);
00390   }
00391 
00392   template<class Val, class P, class N>
00393   ExecStatus
00394   Eq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) {
00395     return prop_bnd<Val,P,N>(home,med,*this,x,y,c);
00396   }
00397 
00398   /*
00399    * Reified bound consistent linear equation
00400    *
00401    */
00402 
00403   template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00404   forceinline
00405   ReEq<Val,P,N,Ctrl,rm>::ReEq(Home home,
00406                               ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b)
00407     : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,x,y,c,b) {}
00408 
00409   template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00410   ExecStatus
00411   ReEq<Val,P,N,Ctrl,rm>::post(Home home,
00412                               ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) {
00413     ViewArray<NoView> nva;
00414     if (y.size() == 0) {
00415       (void) new (home) ReEq<Val,P,NoView,Ctrl,rm>(home,x,nva,c,b);
00416     } else if (x.size() == 0) {
00417       (void) new (home) ReEq<Val,N,NoView,Ctrl,rm>(home,y,nva,-c,b);
00418     } else {
00419       (void) new (home) ReEq<Val,P,N,Ctrl,rm>(home,x,y,c,b);
00420     }
00421     return ES_OK;
00422   }
00423 
00424 
00425   template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00426   forceinline
00427   ReEq<Val,P,N,Ctrl,rm>::ReEq(Space& home, ReEq<Val,P,N,Ctrl,rm>& p)
00428     : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,p) {}
00429 
00430   template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00431   Actor*
00432   ReEq<Val,P,N,Ctrl,rm>::copy(Space& home) {
00433     return new (home) ReEq<Val,P,N,Ctrl,rm>(home,*this);
00434   }
00435 
00436   template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00437   ExecStatus
00438   ReEq<Val,P,N,Ctrl,rm>::propagate(Space& home, const ModEventDelta& med) {
00439     if (b.zero()) {
00440       if (rm == RM_IMP)
00441         return home.ES_SUBSUMED(*this);
00442       GECODE_REWRITE(*this,(Nq<Val,P,N>::post(home(*this),x,y,c)));
00443     }
00444     if (b.one()) {
00445       if (rm == RM_PMI)
00446         return home.ES_SUBSUMED(*this);
00447       GECODE_REWRITE(*this,(Eq<Val,P,N>::post(home(*this),x,y,c)));
00448     }
00449 
00450     Val sl = 0;
00451     Val su = 0;
00452 
00453     bounds_p<Val,P>(med, x, c, sl, su);
00454     bounds_n<Val,N>(med, y, c, sl, su);
00455 
00456     if ((-sl == c) && (-su == c)) {
00457       if (rm != RM_IMP)
00458         GECODE_ME_CHECK(b.one_none(home));
00459       return home.ES_SUBSUMED(*this);
00460     }
00461     if ((-sl > c) || (-su < c)) {
00462       if (rm != RM_PMI)
00463         GECODE_ME_CHECK(b.zero_none(home));
00464       return home.ES_SUBSUMED(*this);
00465     }
00466     return ES_FIX;
00467   }
00468 
00469 
00470   /*
00471    * Domain consistent linear disequation
00472    *
00473    */
00474 
00475   template<class Val, class P, class N>
00476   forceinline
00477   Nq<Val,P,N>::Nq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00478     : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {}
00479 
00480   template<class Val, class P, class N>
00481   ExecStatus
00482   Nq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00483     ViewArray<NoView> nva;
00484     if (y.size() == 0) {
00485       (void) new (home) Nq<Val,P,NoView>(home,x,nva,c);
00486     } else if (x.size() == 0) {
00487       (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c);
00488     } else {
00489       (void) new (home) Nq<Val,P,N>(home,x,y,c);
00490     }
00491     return ES_OK;
00492   }
00493 
00494 
00495   template<class Val, class P, class N>
00496   forceinline
00497   Nq<Val,P,N>::Nq(Space& home, Nq<Val,P,N>& p)
00498     : Lin<Val,P,N,PC_INT_VAL>(home,p) {}
00499 
00504   template<class Val, class P, class N>
00505   forceinline Actor*
00506   nqtobin(Space&, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00507     return NULL;
00508   }
00509   template<class Val>
00510   forceinline Actor*
00511   nqtobin(Space& home, Propagator& p,
00512           ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00513     assert(x.size() == 2);
00514     return new (home) NqBin<Val,IntView,IntView>
00515       (home,p,x[0],x[1],c);
00516   }
00517   template<class Val>
00518   forceinline Actor*
00519   nqtobin(Space& home, Propagator& p,
00520           ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00521     assert(y.size() == 2);
00522     return new (home) NqBin<Val,IntView,IntView>
00523       (home,p,y[0],y[1],-c);
00524   }
00525   template<class Val>
00526   forceinline Actor*
00527   nqtobin(Space& home, Propagator& p,
00528           ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00529     if (x.size() == 2)
00530       return new (home) NqBin<Val,IntView,IntView>
00531         (home,p,x[0],x[1],c);
00532     if (x.size() == 1)
00533       return new (home) NqBin<Val,IntView,MinusView>
00534         (home,p,x[0],MinusView(y[0]),c);
00535     return new (home) NqBin<Val,IntView,IntView>
00536       (home,p,y[0],y[1],-c);
00537   }
00538 
00543   template<class Val, class P, class N>
00544   forceinline Actor*
00545   nqtoter(Space&, Propagator&,ViewArray<P>&, ViewArray<N>&, Val) {
00546     return NULL;
00547   }
00548   template<class Val>
00549   forceinline Actor*
00550   nqtoter(Space& home, Propagator& p,
00551           ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00552     assert(x.size() == 3);
00553     return new (home) NqTer<Val,IntView,IntView,IntView>
00554       (home,p,x[0],x[1],x[2],c);
00555   }
00556   template<class Val>
00557   forceinline Actor*
00558   nqtoter(Space& home, Propagator& p,
00559           ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00560     assert(y.size() == 3);
00561     return new (home) NqTer<Val,IntView,IntView,IntView>
00562       (home,p,y[0],y[1],y[2],-c);
00563   }
00564   template<class Val>
00565   forceinline Actor*
00566   nqtoter(Space& home, Propagator& p,
00567           ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00568     if (x.size() == 3)
00569       return new (home) NqTer<Val,IntView,IntView,IntView>
00570         (home,p,x[0],x[1],x[2],c);
00571     if (x.size() == 2)
00572       return new (home) NqTer<Val,IntView,IntView,MinusView>
00573         (home,p,x[0],x[1],MinusView(y[0]),c);
00574     if (x.size() == 1)
00575       return new (home) NqTer<Val,IntView,IntView,MinusView>
00576         (home,p,y[0],y[1],MinusView(x[0]),-c);
00577     return new (home) NqTer<Val,IntView,IntView,IntView>
00578       (home,p,y[0],y[1],y[2],-c);
00579   }
00580 
00581   template<class Val, class P, class N>
00582   Actor*
00583   Nq<Val,P,N>::copy(Space& home) {
00584     if (isunit(x,y)) {
00585       // Check whether rewriting is possible
00586       if (x.size() + y.size() == 2)
00587         return nqtobin(home,*this,x,y,c);
00588       if (x.size() + y.size() == 3)
00589         return nqtoter(home,*this,x,y,c);
00590     }
00591     return new (home) Nq<Val,P,N>(home,*this);
00592   }
00593 
00594   template<class Val, class P, class N>
00595   ExecStatus
00596   Nq<Val,P,N>::propagate(Space& home, const ModEventDelta&) {
00597     for (int i = x.size(); i--; )
00598       if (x[i].assigned()) {
00599         c -= x[i].val();  x.move_lst(i);
00600       }
00601     for (int i = y.size(); i--; )
00602       if (y[i].assigned()) {
00603         c += y[i].val();  y.move_lst(i);
00604       }
00605     if (x.size() + y.size() <= 1) {
00606       if (x.size() == 1) {
00607         GECODE_ME_CHECK(x[0].nq(home,c)); return home.ES_SUBSUMED(*this);
00608       }
00609       if (y.size() == 1) {
00610         GECODE_ME_CHECK(y[0].nq(home,-c)); return home.ES_SUBSUMED(*this);
00611       }
00612       return (c == static_cast<Val>(0)) ?
00613         ES_FAILED : home.ES_SUBSUMED(*this);
00614     }
00615     return ES_FIX;
00616   }
00617 
00618 
00619   /*
00620    * Bound consistent linear inequation
00621    *
00622    */
00623 
00624   template<class Val, class P, class N>
00625   forceinline
00626   Lq<Val,P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00627     : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00628 
00629   template<class Val, class P, class N>
00630   ExecStatus
00631   Lq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00632     ViewArray<NoView> nva;
00633     if (y.size() == 0) {
00634       (void) new (home) Lq<Val,P,NoView>(home,x,nva,c);
00635     } else if (x.size() == 0) {
00636       (void) new (home) Lq<Val,NoView,N>(home,nva,y,c);
00637     } else {
00638       (void) new (home) Lq<Val,P,N>(home,x,y,c);
00639     }
00640     return ES_OK;
00641   }
00642 
00643 
00644   template<class Val, class P, class N>
00645   forceinline
00646   Lq<Val,P,N>::Lq(Space& home, Lq<Val,P,N>& p)
00647     : Lin<Val,P,N,PC_INT_BND>(home,p) {}
00648 
00653   template<class Val, class P, class N>
00654   forceinline Actor*
00655   lqtobin(Space&, Propagator&,ViewArray<P>&, ViewArray<N>&, Val) {
00656     return NULL;
00657   }
00658   template<class Val>
00659   forceinline Actor*
00660   lqtobin(Space& home, Propagator& p,
00661           ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00662     assert(x.size() == 2);
00663     return new (home) LqBin<Val,IntView,IntView>
00664       (home,p,x[0],x[1],c);
00665   }
00666   template<class Val>
00667   forceinline Actor*
00668   lqtobin(Space& home, Propagator& p,
00669           ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00670     assert(y.size() == 2);
00671     return new (home) LqBin<Val,MinusView,MinusView>
00672       (home,p,MinusView(y[0]),MinusView(y[1]),c);
00673   }
00674   template<class Val>
00675   forceinline Actor*
00676   lqtobin(Space& home, Propagator& p,
00677           ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00678     if (x.size() == 2)
00679       return new (home) LqBin<Val,IntView,IntView>
00680         (home,p,x[0],x[1],c);
00681     if (x.size() == 1)
00682       return new (home) LqBin<Val,IntView,MinusView>
00683         (home,p,x[0],MinusView(y[0]),c);
00684     return new (home) LqBin<Val,MinusView,MinusView>
00685       (home,p,MinusView(y[0]),MinusView(y[1]),c);
00686   }
00687 
00692   template<class Val, class P, class N>
00693   forceinline Actor*
00694   lqtoter(Space&, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00695     return NULL;
00696   }
00697   template<class Val>
00698   forceinline Actor*
00699   lqtoter(Space& home, Propagator& p,
00700           ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00701     assert(x.size() == 3);
00702     return new (home) LqTer<Val,IntView,IntView,IntView>
00703       (home,p,x[0],x[1],x[2],c);
00704   }
00705   template<class Val>
00706   forceinline Actor*
00707   lqtoter(Space& home, Propagator& p,
00708           ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00709     assert(y.size() == 3);
00710     return new (home) LqTer<Val,MinusView,MinusView,MinusView>
00711       (home,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
00712   }
00713   template<class Val>
00714   forceinline Actor*
00715   lqtoter(Space& home, Propagator& p,
00716           ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00717     if (x.size() == 3)
00718       return new (home) LqTer<Val,IntView,IntView,IntView>
00719         (home,p,x[0],x[1],x[2],c);
00720     if (x.size() == 2)
00721       return new (home) LqTer<Val,IntView,IntView,MinusView>
00722         (home,p,x[0],x[1],MinusView(y[0]),c);
00723     if (x.size() == 1)
00724       return new (home) LqTer<Val,IntView,MinusView,MinusView>
00725         (home,p,x[0],MinusView(y[0]),MinusView(y[1]),c);
00726     return new (home) LqTer<Val,MinusView,MinusView,MinusView>
00727       (home,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
00728   }
00729 
00730   template<class Val, class P, class N>
00731   Actor*
00732   Lq<Val,P,N>::copy(Space& home) {
00733     if (isunit(x,y)) {
00734       // Check whether rewriting is possible
00735       if (x.size() + y.size() == 2)
00736         return lqtobin(home,*this,x,y,c);
00737       if (x.size() + y.size() == 3)
00738         return lqtoter(home,*this,x,y,c);
00739     }
00740     return new (home) Lq<Val,P,N>(home,*this);
00741   }
00742 
00743   template<class Val, class P, class N>
00744   ExecStatus
00745   Lq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) {
00746     // Eliminate singletons
00747     Val sl = 0;
00748 
00749     if (IntView::me(med) == ME_INT_VAL) {
00750       for (int i = x.size(); i--; ) {
00751         Val m = x[i].min();
00752         if (x[i].assigned()) {
00753           c  -= m;  x.move_lst(i);
00754         } else {
00755           sl -= m;
00756         }
00757       }
00758       for (int i = y.size(); i--; ) {
00759         Val m = y[i].max();
00760         if (y[i].assigned()) {
00761           c  += m;  y.move_lst(i);
00762         } else {
00763           sl += m;
00764         }
00765       }
00766       if ((x.size() + y.size()) <= 1) {
00767         if (x.size() == 1) {
00768           GECODE_ME_CHECK(x[0].lq(home,c));
00769           return home.ES_SUBSUMED(*this);
00770         }
00771         if (y.size() == 1) {
00772           GECODE_ME_CHECK(y[0].gq(home,-c));
00773           return home.ES_SUBSUMED(*this);
00774         }
00775         return (c >= static_cast<Val>(0)) ?
00776           home.ES_SUBSUMED(*this) : ES_FAILED;
00777       }
00778     } else {
00779       for (int i = x.size(); i--; )
00780         sl -= x[i].min();
00781       for (int i = y.size(); i--; )
00782         sl += y[i].max();
00783     }
00784 
00785     sl += c;
00786 
00787     ExecStatus es = ES_FIX;
00788     bool assigned = true;
00789     for (int i = x.size(); i--; ) {
00790       assert(!x[i].assigned());
00791       Val slx = sl + x[i].min();
00792       ModEvent me = x[i].lq(home,slx);
00793       if (me == ME_INT_FAILED)
00794         return ES_FAILED;
00795       if (me != ME_INT_VAL)
00796         assigned = false;
00797       if (me_modified(me) && (slx != x[i].max()))
00798         es = ES_NOFIX;
00799     }
00800 
00801     for (int i = y.size(); i--; ) {
00802       assert(!y[i].assigned());
00803       Val sly = y[i].max() - sl;
00804       ModEvent me = y[i].gq(home,sly);
00805       if (me == ME_INT_FAILED)
00806         return ES_FAILED;
00807       if (me != ME_INT_VAL)
00808         assigned = false;
00809       if (me_modified(me) && (sly != y[i].min()))
00810         es = ES_NOFIX;
00811     }
00812     return assigned ? home.ES_SUBSUMED(*this) : es;
00813   }
00814 
00815   /*
00816    * Reified bound consistent linear inequation
00817    *
00818    */
00819 
00820   template<class Val, class P, class N, ReifyMode rm>
00821   forceinline
00822   ReLq<Val,P,N,rm>::ReLq(Home home,
00823                       ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b)
00824     : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {}
00825 
00826   template<class Val, class P, class N, ReifyMode rm>
00827   ExecStatus
00828   ReLq<Val,P,N,rm>::post(Home home,
00829                          ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) {
00830     ViewArray<NoView> nva;
00831     if (y.size() == 0) {
00832       (void) new (home) ReLq<Val,P,NoView,rm>(home,x,nva,c,b);
00833     } else if (x.size() == 0) {
00834       (void) new (home) ReLq<Val,NoView,N,rm>(home,nva,y,c,b);
00835     } else {
00836       (void) new (home) ReLq<Val,P,N,rm>(home,x,y,c,b);
00837     }
00838     return ES_OK;
00839   }
00840 
00841 
00842   template<class Val, class P, class N, ReifyMode rm>
00843   forceinline
00844   ReLq<Val,P,N,rm>::ReLq(Space& home, ReLq<Val,P,N,rm>& p)
00845     : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,p) {}
00846 
00847   template<class Val, class P, class N, ReifyMode rm>
00848   Actor*
00849   ReLq<Val,P,N,rm>::copy(Space& home) {
00850     return new (home) ReLq<Val,P,N,rm>(home,*this);
00851   }
00852 
00853   template<class Val, class P, class N, ReifyMode rm>
00854   ExecStatus
00855   ReLq<Val,P,N,rm>::propagate(Space& home, const ModEventDelta& med) {
00856     if (b.zero()) {
00857       if (rm == RM_IMP)
00858         return home.ES_SUBSUMED(*this);
00859       GECODE_REWRITE(*this,(Lq<Val,N,P>::post(home(*this),y,x,-c-1)));
00860     }
00861     if (b.one()) {
00862       if (rm == RM_PMI)
00863         return home.ES_SUBSUMED(*this);
00864       GECODE_REWRITE(*this,(Lq<Val,P,N>::post(home(*this),x,y,c)));
00865     }
00866 
00867     // Eliminate singletons
00868     Val sl = 0;
00869     Val su = 0;
00870 
00871     bounds_p<Val,P>(med,x,c,sl,su);
00872     bounds_n<Val,N>(med,y,c,sl,su);
00873 
00874     if (-sl > c) {
00875       if (rm != RM_PMI)
00876         GECODE_ME_CHECK(b.zero_none(home));
00877       return home.ES_SUBSUMED(*this);
00878     }
00879     if (-su <= c) {
00880       if (rm != RM_IMP)
00881         GECODE_ME_CHECK(b.one_none(home));
00882       return home.ES_SUBSUMED(*this);
00883     }
00884 
00885     return ES_FIX;
00886   }
00887 
00888 }}}
00889 
00890 // STATISTICS: int-prop
00891