eq.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
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 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       GECODE_NEVER;
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       GECODE_NEVER;
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     case RT_MAYBE:
00432       break;
00433     default: GECODE_NEVER;
00434     }
00435     return ES_FIX;
00436   }
00437 
00438 
00439 
00440   /*
00441    * Refied bounds-consistent equality
00442    *
00443    */
00444 
00445   template <class View, class CtrlView>
00446   forceinline
00447   ReEqBnd<View,CtrlView>::ReEqBnd(Space* home, View x0, View x1, CtrlView b)
00448     : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {}
00449 
00450   template <class View, class CtrlView>
00451   ExecStatus
00452   ReEqBnd<View,CtrlView>::post(Space* home, View x0, View x1, CtrlView b){
00453     if (b.one())
00454       return EqBnd<View,View>::post(home,x0,x1);
00455     if (b.zero())
00456       return Nq<View>::post(home,x0,x1);
00457     if (!same(x0,x1)) {
00458       (void) new (home) ReEqBnd(home,x0,x1,b);
00459     } else {
00460       GECODE_ME_CHECK(b.t_one(home));
00461     }
00462     return ES_OK;
00463   }
00464 
00465 
00466   template <class View, class CtrlView>
00467   forceinline
00468   ReEqBnd<View,CtrlView>::ReEqBnd(Space* home, bool share, ReEqBnd& p)
00469     : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p) {}
00470 
00471   template <class View, class CtrlView>
00472   Actor*
00473   ReEqBnd<View,CtrlView>::copy(Space* home, bool share) {
00474     return new (home) ReEqBnd<View,CtrlView>(home,share,*this);
00475   }
00476 
00477 
00478   template <class View, class CtrlView>
00479   ExecStatus
00480   ReEqBnd<View,CtrlView>::propagate(Space* home) {
00481     if (b.one()) {
00482       if (EqBnd<View,View>::post(home,x0,x1) == ES_FAILED)
00483         return ES_FAILED;
00484       return ES_SUBSUMED;
00485     }
00486     if (b.zero()) {
00487       if (Nq<View>::post(home,x0,x1) == ES_FAILED)
00488         return ES_FAILED;
00489       return ES_SUBSUMED;
00490     }
00491     switch (rtest_eq_bnd(x0,x1)) {
00492     case RT_TRUE:
00493       b.t_one_none(home);  return ES_SUBSUMED;
00494     case RT_FALSE:
00495       b.t_zero_none(home); return ES_SUBSUMED;
00496     case RT_MAYBE:
00497       break;
00498     default: GECODE_NEVER;
00499     }
00500     return ES_FIX;
00501   }
00502 
00503 
00504 
00505 
00506   /*
00507    * Refied domain-consistent equality (one variable)
00508    *
00509    */
00510 
00511   template <class View, class CtrlView>
00512   forceinline
00513   ReEqDomInt<View,CtrlView>::ReEqDomInt
00514   (Space* home, View x, int c0, CtrlView b)
00515     : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,x,b), c(c0) {}
00516 
00517   template <class View, class CtrlView>
00518   ExecStatus
00519   ReEqDomInt<View,CtrlView>::post(Space* home, View x, int c, CtrlView b) {
00520     if (b.one()) {
00521       GECODE_ME_CHECK(x.eq(home,c));
00522     } else if (b.zero()) {
00523       GECODE_ME_CHECK(x.nq(home,c));
00524     } else if (x.assigned()) {
00525       assert(b.none());
00526       if (x.val() == c) {
00527         b.t_one_none(home);
00528       } else {
00529         b.t_zero_none(home);
00530       }
00531     } else {
00532       (void) new (home) ReEqDomInt(home,x,c,b); 
00533     }
00534     return ES_OK;
00535   }
00536 
00537 
00538   template <class View, class CtrlView>
00539   forceinline
00540   ReEqDomInt<View,CtrlView>::ReEqDomInt(Space* home, bool share, ReEqDomInt& p)
00541     : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p), c(p.c) {}
00542 
00543   template <class View, class CtrlView>
00544   Actor*
00545   ReEqDomInt<View,CtrlView>::copy(Space* home, bool share) {
00546     return new (home) ReEqDomInt<View,CtrlView>(home,share,*this);
00547   }
00548 
00549   template <class View, class CtrlView>
00550   ExecStatus
00551   ReEqDomInt<View,CtrlView>::propagate(Space* home) {
00552     if (b.one()) {
00553       GECODE_ME_CHECK(x0.eq(home,c)); return ES_SUBSUMED;
00554     }
00555     if (b.zero()) {
00556       GECODE_ME_CHECK(x0.nq(home,c)); return ES_SUBSUMED;
00557     }
00558     switch (rtest_eq_dom(x0,c)) {
00559     case RT_TRUE:
00560       b.t_one_none(home);  return ES_SUBSUMED;
00561     case RT_FALSE:
00562       b.t_zero_none(home); return ES_SUBSUMED;
00563     case RT_MAYBE:
00564       break;
00565     default: GECODE_NEVER;
00566     }
00567     return ES_FIX;
00568   }
00569 
00570 
00571 
00572 
00573   /*
00574    * Refied bounds-consistent equality (one variable)
00575    *
00576    */
00577 
00578   template <class View, class CtrlView>
00579   forceinline
00580   ReEqBndInt<View,CtrlView>::ReEqBndInt
00581   (Space* home, View x, int c0, CtrlView b)
00582     : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,x,b), c(c0) {}
00583 
00584   template <class View, class CtrlView>
00585   ExecStatus
00586   ReEqBndInt<View,CtrlView>::post(Space* home, View x, int c, CtrlView b) {
00587     if (b.one()) {
00588       GECODE_ME_CHECK(x.eq(home,c));
00589     } else if (b.zero()) {
00590       GECODE_ME_CHECK(x.nq(home,c));
00591     } else if (x.assigned()) {
00592       assert(b.none());
00593       if (x.val() == c) {
00594         b.t_one_none(home);
00595       } else {
00596         b.t_zero_none(home);
00597       }
00598     } else {
00599       (void) new (home) ReEqBndInt(home,x,c,b); 
00600     }
00601     return ES_OK;
00602   }
00603 
00604 
00605   template <class View, class CtrlView>
00606   forceinline
00607   ReEqBndInt<View,CtrlView>::ReEqBndInt(Space* home, bool share, ReEqBndInt& p)
00608     : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p), c(p.c) {}
00609 
00610   template <class View, class CtrlView>
00611   Actor*
00612   ReEqBndInt<View,CtrlView>::copy(Space* home, bool share) {
00613     return new (home) ReEqBndInt<View,CtrlView>(home,share,*this);
00614   }
00615 
00616   template <class View, class CtrlView>
00617   ExecStatus
00618   ReEqBndInt<View,CtrlView>::propagate(Space* home) {
00619     if (b.one()) {
00620       GECODE_ME_CHECK(x0.eq(home,c)); return ES_SUBSUMED;
00621     }
00622     if (b.zero()) {
00623       GECODE_ME_CHECK(x0.nq(home,c)); return ES_SUBSUMED;
00624     }
00625     switch (rtest_eq_bnd(x0,c)) {
00626     case RT_TRUE:
00627       b.t_one_none(home);  return ES_SUBSUMED;
00628     case RT_FALSE:
00629       b.t_zero_none(home); return ES_SUBSUMED;
00630     case RT_MAYBE:
00631       break;
00632     default: GECODE_NEVER;
00633     }
00634     return ES_FIX;
00635   }
00636 
00637 }}}
00638 
00639 // STATISTICS: int-prop
00640