Generated on Wed Nov 1 15:04:36 2006 for Gecode by doxygen 1.4.5

nary.icc

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