Generated on Thu Jul 6 07:06:41 2006 for Gecode by doxygen 1.4.7

eq.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-04-03 15:23:30 +0200 (Mon, 03 Apr 2006) $ by $Author: tack $
00010  *     $Revision: 3150 $
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 namespace Gecode { namespace Int { namespace Rel {
00023 
00024   /*
00025    * Binary bounds consistent equality
00026    *
00027    */
00028 
00029   template <class View0, class View1>
00030   forceinline
00031   EqBnd<View0,View1>::EqBnd(Space* home, View0 x0, View1 x1)
00032     : InhomBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,x0,x1) {}
00033 
00034   template <class View0, class View1>
00035   ExecStatus
00036   EqBnd<View0,View1>::post(Space* home, View0 x0, View1 x1){
00037     if (x0.assigned()) {
00038       GECODE_ME_CHECK(x1.eq(home,x0.val()));
00039     } else if (x1.assigned()) {
00040       GECODE_ME_CHECK(x0.eq(home,x1.val()));
00041     } else if (!same(x0,x1)) {
00042       (void) new (home) EqBnd<View0,View1>(home,x0,x1);
00043     }
00044     return ES_OK;
00045   }
00046 
00047   template <class View0, class View1>
00048   forceinline
00049   EqBnd<View0,View1>::EqBnd(Space* home, bool share, EqBnd<View0,View1>& p)
00050     : InhomBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,share,p) {}
00051 
00052   template <class View0, class View1>
00053   forceinline
00054   EqBnd<View0,View1>::EqBnd(Space* home, bool share, Propagator& p,
00055                             View0 x0, View1 x1)
00056     : InhomBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,share,p,
00057                                                                x0,x1) {}
00058 
00059   template <class View0, class View1>
00060   Actor*
00061   EqBnd<View0,View1>::copy(Space* home, bool share) {
00062     return new (home) EqBnd<View0,View1>(home,share,*this);
00063   }
00064 
00065   template <class View0, class View1>
00066   ExecStatus
00067   EqBnd<View0,View1>::propagate(Space* home) {
00068     if (x0.assigned()) {
00069       GECODE_ME_CHECK(x1.eq(home,x0.val())); 
00070       return ES_SUBSUMED;
00071     }
00072     if (x1.assigned()) {
00073       GECODE_ME_CHECK(x0.eq(home,x1.val())); 
00074       return ES_SUBSUMED;
00075     }
00076     do {
00077       GECODE_ME_CHECK(x0.gq(home,x1.min()));
00078       GECODE_ME_CHECK(x1.gq(home,x0.min()));
00079     } while (x0.min() != x1.min());
00080     do {
00081       GECODE_ME_CHECK(x0.lq(home,x1.max()));
00082       GECODE_ME_CHECK(x1.lq(home,x0.max()));
00083     } while (x0.max() != x1.max());
00084     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00085   }
00086 
00087 
00088 
00089 
00090 
00091   /*
00092    * Binary domain consistent equality
00093    *
00094    */
00095 
00096   template <class View0, class View1>
00097   forceinline
00098   EqDom<View0,View1>::EqDom(Space* home, View0 x0, View1 x1)
00099     : InhomBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,x0,x1) {}
00100 
00101   template <class View0, class View1>
00102   ExecStatus
00103   EqDom<View0,View1>::post(Space* home, View0 x0, View1 x1){
00104     if (x0.assigned()) {
00105       GECODE_ME_CHECK(x1.eq(home,x0.val()));
00106     } else if (x1.assigned()) {
00107       GECODE_ME_CHECK(x0.eq(home,x1.val()));
00108     } else if (!same(x0,x1)) {
00109       (void) new (home) EqDom<View0,View1>(home,x0,x1);
00110     }
00111     return ES_OK;
00112   }
00113 
00114 
00115   template <class View0, class View1>
00116   forceinline
00117   EqDom<View0,View1>::EqDom(Space* home, bool share, EqDom<View0,View1>& p)
00118     : InhomBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,share,p) {}
00119 
00120   template <class View0, class View1>
00121   Actor*
00122   EqDom<View0,View1>::copy(Space* home, bool share) {
00123     return new (home) EqDom<View0,View1>(home,share,*this);
00124   }
00125 
00126 
00127   template <class View0, class View1>
00128   PropCost
00129   EqDom<View0,View1>::cost(void) const {
00130     if (View0::pme(this) == ME_INT_VAL || View1::pme(this) == ME_INT_VAL)
00131       return PC_UNARY_LO;
00132     if (View0::pme(this) == ME_INT_DOM || View1::pme(this) == ME_INT_DOM)
00133       return PC_BINARY_HI;
00134     return PC_BINARY_LO;
00135   }
00136 
00137   template <class View0, class View1>
00138   ExecStatus
00139   EqDom<View0,View1>::propagate(Space* home) {
00140     if (x0.assigned()) {
00141       GECODE_ME_CHECK(x1.eq(home,x0.val())); 
00142       return ES_SUBSUMED;
00143     }
00144     if (x1.assigned()) {
00145       GECODE_ME_CHECK(x0.eq(home,x1.val())); 
00146       return ES_SUBSUMED;
00147     }
00148     if (View0::pme(this) != ME_INT_DOM && View1::pme(this) != ME_INT_DOM) {
00149       do {
00150         GECODE_ME_CHECK(x0.gq(home,x1.min()));
00151         GECODE_ME_CHECK(x1.gq(home,x0.min()));
00152       } while (x0.min() != x1.min());
00153       do {
00154         GECODE_ME_CHECK(x0.lq(home,x1.max()));
00155         GECODE_ME_CHECK(x1.lq(home,x0.max()));
00156       } while (x0.max() != x1.max());
00157       if (x0.assigned())
00158         return ES_SUBSUMED;
00159       if (x0.range() && x1.range())
00160         return ES_FIX;
00161       return this->ES_FIX_PARTIAL(View0::pme(ME_INT_DOM));
00162     }
00163     ViewRanges<View0> r0(x0);
00164     GECODE_ME_CHECK(x1.inter(home,r0));
00165     ViewRanges<View1> r1(x1);
00166     GECODE_ME_CHECK(x0.narrow(home,r1));
00167     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00168   }
00169 
00170 
00171 
00172   /*
00173    * Nary domain consistent equality
00174    *
00175    */
00176 
00177   template <class View>
00178   forceinline
00179   NaryEqDom<View>::NaryEqDom(Space* home, ViewArray<View>& x)
00180     : NaryPropagator<View,PC_INT_DOM>(home,x) {}
00181 
00182   template <class View>
00183   ExecStatus
00184   NaryEqDom<View>::post(Space* home, ViewArray<View>& x) {
00185     x.unique();
00186     if (x.size() == 2)
00187       return EqDom<View,View>::post(home,x[0],x[1]);
00188     else if (x.size() > 2)
00189       (void) new (home) NaryEqDom<View>(home,x);
00190     return ES_OK;
00191   }
00192 
00193   template <class View>
00194   forceinline
00195   NaryEqDom<View>::NaryEqDom(Space* home, bool share, NaryEqDom<View>& p)
00196     : NaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00197 
00198   template <class View>
00199   Actor*
00200   NaryEqDom<View>::copy(Space* home, bool share) {
00201     return new (home) NaryEqDom<View>(home,share,*this);
00202   }
00203 
00204   template <class View>
00205   PropCost
00206   NaryEqDom<View>::cost(void) const {
00207     if (View::pme(this) == ME_INT_VAL)
00208       return PC_UNARY_LO;
00209     if (View::pme(this) == ME_INT_DOM)
00210       return cost_hi(x.size(),PC_LINEAR_HI);
00211     return cost_lo(x.size(),PC_LINEAR_LO);
00212   }
00213 
00214   template <class View>
00215   ExecStatus
00216   NaryEqDom<View>::propagate(Space* home) {
00217     assert(x.size() > 2);
00218 
00219     ModEvent me = View::pme(this);
00220     if (me == ME_INT_VAL) {
00221       // One of the variables is assigned
00222       for (int i = 0; ; i++)
00223         if (x[i].assigned()) {
00224           int n = x[i].val();
00225           x.move_lst(i);
00226           for (int i = x.size(); i--; )
00227             GECODE_ME_CHECK(x[i].eq(home,n));
00228           return ES_SUBSUMED;
00229         }
00230       assert(0);
00231       return ES_SUBSUMED;
00232     }
00233 
00234     if (me == ME_INT_BND) {
00235       {
00236         // One of the mins has changed
00237         int mn = x[0].min();
00238       restart_min:
00239         for (int i = x.size(); i--; ) {
00240           GECODE_ME_CHECK(x[i].gq(home,mn));
00241           if (mn < x[i].min()) {
00242             mn = x[i].min();
00243             goto restart_min;
00244           }
00245         }
00246       }
00247       {
00248         // One of the maxs has changed
00249         int mx = x[0].max();
00250       restart_max:
00251         for (int i = x.size(); i--; ) {
00252           GECODE_ME_CHECK(x[i].lq(home,mx));
00253           if (mx > x[i].max()) {
00254             mx = x[i].max();
00255             goto restart_max;
00256           }
00257         }
00258       }
00259       if (x[0].assigned())
00260         return ES_SUBSUMED;
00261       return this->ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00262     }
00263 
00264     int n = x.size();
00265 
00266     GECODE_AUTOARRAY(ViewRanges<View>, i_x, n);
00267     for (int i = n; i--; ) {
00268       ViewRanges<View> i_xi(x[i]);
00269       i_x[i] = i_xi;
00270     }
00271     Iter::Ranges::NaryInter<ViewRanges<View> > r(i_x,n);
00272     Iter::Ranges::Cache<Iter::Ranges::NaryInter<ViewRanges<View> > > rc(r);
00273 
00274     if (!rc())
00275       return ES_FAILED;
00276     ++rc;
00277     if (!rc()) {
00278       rc.reset();
00279       for (int i = n; i--; ) {
00280         GECODE_ME_CHECK(x[i].gq(home,rc.min()));
00281         GECODE_ME_CHECK(x[i].lq(home,rc.max()));
00282       }
00283     } else {
00284       for (int i = n; i--; ) {
00285         rc.reset();
00286         GECODE_ME_CHECK(x[i].narrow(home,rc));
00287       }
00288     }
00289     return ES_FIX;
00290   }
00291 
00292 
00293 
00294   /*
00295    * Nary bound consistent equality
00296    *
00297    */
00298 
00299   template <class View>
00300   forceinline
00301   NaryEqBnd<View>::NaryEqBnd(Space* home, ViewArray<View>& x)
00302     : NaryPropagator<View,PC_INT_BND>(home,x) {}
00303 
00304   template <class View>
00305   ExecStatus
00306   NaryEqBnd<View>::post(Space* home, ViewArray<View>& x) {
00307     if (x.size() == 2)
00308       return EqBnd<View,View>::post(home,x[0],x[1]);
00309     else if (x.size() > 2)
00310       (void) new (home) NaryEqBnd<View>(home,x);
00311     return ES_OK;
00312   }
00313 
00314   template <class View>
00315   forceinline
00316   NaryEqBnd<View>::NaryEqBnd(Space* home, bool share, NaryEqBnd<View>& p)
00317     : NaryPropagator<View,PC_INT_BND>(home,share,p) {}
00318 
00319   template <class View>
00320   Actor*
00321   NaryEqBnd<View>::copy(Space* home, bool share) {
00322     return new (home) NaryEqBnd<View>(home,share,*this);
00323   }
00324 
00325   template <class View>
00326   PropCost
00327   NaryEqBnd<View>::cost(void) const {
00328     if (View::pme(this) == ME_INT_VAL)
00329       return PC_UNARY_LO;
00330     return cost_lo(x.size(),PC_LINEAR_LO);
00331   }
00332 
00333   template <class View>
00334   ExecStatus
00335   NaryEqBnd<View>::propagate(Space* home) {
00336     assert(x.size() > 2);
00337 
00338     if (View::pme(this) == ME_INT_VAL) {
00339       // One of the variables is assigned
00340       for (int i = 0; ; i++)
00341         if (x[i].assigned()) {
00342           int n = x[i].val();
00343           x.move_lst(i);
00344           for (int i = x.size(); i--; )
00345             GECODE_ME_CHECK(x[i].eq(home,n));
00346           return ES_SUBSUMED;
00347         }
00348       assert(0);
00349       return ES_SUBSUMED;
00350     }
00351 
00352     int mn = x[0].min();
00353   restart_min:
00354     for (int i = x.size(); i--; ) {
00355       GECODE_ME_CHECK(x[i].gq(home,mn));
00356       if (mn < x[i].min()) {
00357         mn = x[i].min();
00358         goto restart_min;
00359       }
00360     }
00361     int mx = x[0].max();
00362   restart_max:
00363     for (int i = x.size(); i--; ) {
00364       GECODE_ME_CHECK(x[i].lq(home,mx));
00365       if (mx > x[i].max()) {
00366         mx = x[i].max();
00367         goto restart_max;
00368       }
00369     }
00370     return x[0].assigned() ? ES_SUBSUMED : ES_FIX;
00371   }
00372 
00373 
00374 
00375   /*
00376    * Refied domain-consistent equality
00377    *
00378    */
00379 
00380   template <class View, class CtrlView>
00381   forceinline
00382   ReEqDom<View,CtrlView>::ReEqDom(Space* home, View x0, View x1, CtrlView b)
00383     : ReBinaryPropagator<View,PC_INT_DOM,CtrlView>(home,x0,x1,b) {}
00384 
00385   template <class View, class CtrlView>
00386   ExecStatus
00387   ReEqDom<View,CtrlView>::post(Space* home, View x0, View x1, CtrlView b) {
00388     if (b.one())
00389       return EqDom<View,View>::post(home,x0,x1);
00390     if (b.zero())
00391       return Nq<View>::post(home,x0,x1);
00392     if (!same(x0,x1)) {
00393       (void) new (home) ReEqDom(home,x0,x1,b);
00394     } else {
00395       GECODE_ME_CHECK(b.t_one(home));
00396     }
00397     return ES_OK;
00398   }
00399 
00400 
00401   template <class View, class CtrlView>
00402   forceinline
00403   ReEqDom<View,CtrlView>::ReEqDom(Space* home, bool share, ReEqDom& p)
00404     : ReBinaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p) {}
00405 
00406   template <class View, class CtrlView>
00407   Actor*
00408   ReEqDom<View,CtrlView>::copy(Space* home, bool share) {
00409     return new (home) ReEqDom<View,CtrlView>(home,share,*this);
00410   }
00411 
00412 
00413   template <class View, class CtrlView>
00414   ExecStatus
00415   ReEqDom<View,CtrlView>::propagate(Space* home) {
00416     if (b.one()) {
00417       if (EqDom<View,View>::post(home,x0,x1) == ES_FAILED)
00418         return ES_FAILED;
00419       return ES_SUBSUMED;
00420     }
00421     if (b.zero()) {
00422       if (Nq<View>::post(home,x0,x1) == ES_FAILED)
00423         return ES_FAILED;
00424       return ES_SUBSUMED;
00425     }
00426     switch (rtest_eq_dom(x0,x1)) {
00427     case RT_TRUE:
00428       b.t_one_none(home);  return ES_SUBSUMED;
00429     case RT_FALSE:
00430       b.t_zero_none(home); return ES_SUBSUMED;
00431     default: ;
00432     }
00433     return ES_FIX;
00434   }
00435 
00436 
00437 
00438   /*
00439    * Refied bounds-consistent equality
00440    *
00441    */
00442 
00443   template <class View, class CtrlView>
00444   forceinline
00445   ReEqBnd<View,CtrlView>::ReEqBnd(Space* home, View x0, View x1, CtrlView b)
00446     : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {}
00447 
00448   template <class View, class CtrlView>
00449   ExecStatus
00450   ReEqBnd<View,CtrlView>::post(Space* home, View x0, View x1, CtrlView b){
00451     if (b.one())
00452       return EqBnd<View,View>::post(home,x0,x1);
00453     if (b.zero())
00454       return Nq<View>::post(home,x0,x1);
00455     if (!same(x0,x1)) {
00456       (void) new (home) ReEqBnd(home,x0,x1,b);
00457     } else {
00458       GECODE_ME_CHECK(b.t_one(home));
00459     }
00460     return ES_OK;
00461   }
00462 
00463 
00464   template <class View, class CtrlView>
00465   forceinline
00466   ReEqBnd<View,CtrlView>::ReEqBnd(Space* home, bool share, ReEqBnd& p)
00467     : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p) {}
00468 
00469   template <class View, class CtrlView>
00470   Actor*
00471   ReEqBnd<View,CtrlView>::copy(Space* home, bool share) {
00472     return new (home) ReEqBnd<View,CtrlView>(home,share,*this);
00473   }
00474 
00475 
00476   template <class View, class CtrlView>
00477   ExecStatus
00478   ReEqBnd<View,CtrlView>::propagate(Space* home) {
00479     if (b.one()) {
00480       if (EqBnd<View,View>::post(home,x0,x1) == ES_FAILED)
00481         return ES_FAILED;
00482       return ES_SUBSUMED;
00483     }
00484     if (b.zero()) {
00485       if (Nq<View>::post(home,x0,x1) == ES_FAILED)
00486         return ES_FAILED;
00487       return ES_SUBSUMED;
00488     }
00489     switch (rtest_eq_bnd(x0,x1)) {
00490     case RT_TRUE:
00491       b.t_one_none(home);  return ES_SUBSUMED;
00492     case RT_FALSE:
00493       b.t_zero_none(home); return ES_SUBSUMED;
00494     default: ;
00495     }
00496     return ES_FIX;
00497   }
00498 
00499 
00500 
00501 
00502   /*
00503    * Refied domain-consistent equality (one variable)
00504    *
00505    */
00506 
00507   template <class View, class CtrlView>
00508   forceinline
00509   ReEqDomInt<View,CtrlView>::ReEqDomInt
00510   (Space* home, View x, int c0, CtrlView b)
00511     : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,x,b), c(c0) {}
00512 
00513   template <class View, class CtrlView>
00514   ExecStatus
00515   ReEqDomInt<View,CtrlView>::post(Space* home, View x, int c, CtrlView b) {
00516     if (b.one()) {
00517       GECODE_ME_CHECK(x.eq(home,c));
00518     } else if (b.zero()) {
00519       GECODE_ME_CHECK(x.nq(home,c));
00520     } else if (x.assigned()) {
00521       assert(b.none());
00522       if (x.val() == c) {
00523         b.t_one_none(home);
00524       } else {
00525         b.t_zero_none(home);
00526       }
00527     } else {
00528       (void) new (home) ReEqDomInt(home,x,c,b); 
00529     }
00530     return ES_OK;
00531   }
00532 
00533 
00534   template <class View, class CtrlView>
00535   forceinline
00536   ReEqDomInt<View,CtrlView>::ReEqDomInt(Space* home, bool share, ReEqDomInt& p)
00537     : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p), c(p.c) {}
00538 
00539   template <class View, class CtrlView>
00540   Actor*
00541   ReEqDomInt<View,CtrlView>::copy(Space* home, bool share) {
00542     return new (home) ReEqDomInt<View,CtrlView>(home,share,*this);
00543   }
00544 
00545   template <class View, class CtrlView>
00546   ExecStatus
00547   ReEqDomInt<View,CtrlView>::propagate(Space* home) {
00548     if (b.one()) {
00549       GECODE_ME_CHECK(x0.eq(home,c)); return ES_SUBSUMED;
00550     }
00551     if (b.zero()) {
00552       GECODE_ME_CHECK(x0.nq(home,c)); return ES_SUBSUMED;
00553     }
00554     switch (rtest_eq_dom(x0,c)) {
00555     case RT_TRUE:
00556       b.t_one_none(home);  return ES_SUBSUMED;
00557     case RT_FALSE:
00558       b.t_zero_none(home); return ES_SUBSUMED;
00559     default: ;
00560     }
00561     return ES_FIX;
00562   }
00563 
00564 
00565 
00566 
00567   /*
00568    * Refied bounds-consistent equality (one variable)
00569    *
00570    */
00571 
00572   template <class View, class CtrlView>
00573   forceinline
00574   ReEqBndInt<View,CtrlView>::ReEqBndInt
00575   (Space* home, View x, int c0, CtrlView b)
00576     : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,x,b), c(c0) {}
00577 
00578   template <class View, class CtrlView>
00579   ExecStatus
00580   ReEqBndInt<View,CtrlView>::post(Space* home, View x, int c, CtrlView b) {
00581     if (b.one()) {
00582       GECODE_ME_CHECK(x.eq(home,c));
00583     } else if (b.zero()) {
00584       GECODE_ME_CHECK(x.nq(home,c));
00585     } else if (x.assigned()) {
00586       assert(b.none());
00587       if (x.val() == c) {
00588         b.t_one_none(home);
00589       } else {
00590         b.t_zero_none(home);
00591       }
00592     } else {
00593       (void) new (home) ReEqBndInt(home,x,c,b); 
00594     }
00595     return ES_OK;
00596   }
00597 
00598 
00599   template <class View, class CtrlView>
00600   forceinline
00601   ReEqBndInt<View,CtrlView>::ReEqBndInt(Space* home, bool share, ReEqBndInt& p)
00602     : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p), c(p.c) {}
00603 
00604   template <class View, class CtrlView>
00605   Actor*
00606   ReEqBndInt<View,CtrlView>::copy(Space* home, bool share) {
00607     return new (home) ReEqBndInt<View,CtrlView>(home,share,*this);
00608   }
00609 
00610   template <class View, class CtrlView>
00611   ExecStatus
00612   ReEqBndInt<View,CtrlView>::propagate(Space* home) {
00613     if (b.one()) {
00614       GECODE_ME_CHECK(x0.eq(home,c)); return ES_SUBSUMED;
00615     }
00616     if (b.zero()) {
00617       GECODE_ME_CHECK(x0.nq(home,c)); return ES_SUBSUMED;
00618     }
00619     switch (rtest_eq_bnd(x0,c)) {
00620     case RT_TRUE:
00621       b.t_one_none(home);  return ES_SUBSUMED;
00622     case RT_FALSE:
00623       b.t_zero_none(home); return ES_SUBSUMED;
00624     default: ;
00625     }
00626     return ES_FIX;
00627   }
00628 
00629 }}}
00630 
00631 // STATISTICS: int-prop
00632