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