Generated on Wed Jan 4 17:49:08 2006 for Gecode by doxygen 1.4.6

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