Generated on Fri Oct 19 11:24:56 2018 for Gecode by doxygen 1.6.3

eq.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Vincent Barichard <Vincent.Barichard@univ-angers.fr>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2004
00009  *     Vincent Barichard, 2012
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 namespace Gecode { namespace Float { namespace Rel {
00037 
00038   /*
00039    * Binary bounds consistent equality
00040    *
00041    */
00042 
00043   template<class View0, class View1>
00044   forceinline
00045   Eq<View0,View1>::Eq(Home home, View0 x0, View1 x1)
00046     : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,x0,x1) {}
00047 
00048   template<class View0, class View1>
00049   ExecStatus
00050   Eq<View0,View1>::post(Home home, View0 x0, View1 x1){
00051     if (x0.assigned()) {
00052       GECODE_ME_CHECK(x1.eq(home,x0.val()));
00053     } else if (x1.assigned()) {
00054       GECODE_ME_CHECK(x0.eq(home,x1.val()));
00055     } else if (x0 != x1) {
00056       GECODE_ME_CHECK(x0.lq(home,x1.max()));
00057       GECODE_ME_CHECK(x1.lq(home,x0.max()));
00058       GECODE_ME_CHECK(x0.gq(home,x1.min()));
00059       GECODE_ME_CHECK(x1.gq(home,x0.min()));
00060       (void) new (home) Eq<View0,View1>(home,x0,x1);
00061     }
00062     return ES_OK;
00063   }
00064 
00065   template<class View0, class View1>
00066   forceinline
00067   Eq<View0,View1>::Eq(Space& home, Eq<View0,View1>& p)
00068     : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,p) {}
00069 
00070   template<class View0, class View1>
00071   forceinline
00072   Eq<View0,View1>::Eq(Space& home, Propagator& p,
00073                       View0 x0, View1 x1)
00074     : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,p,
00075                                                                  x0,x1) {}
00076 
00077   template<class View0, class View1>
00078   Actor*
00079   Eq<View0,View1>::copy(Space& home) {
00080     return new (home) Eq<View0,View1>(home,*this);
00081   }
00082 
00083   template<class View0, class View1>
00084   ExecStatus
00085   Eq<View0,View1>::propagate(Space& home, const ModEventDelta&) {
00086     if (x0.assigned()) {
00087       GECODE_ME_CHECK(x1.eq(home,x0.val()));
00088     } else if (x1.assigned()) {
00089       GECODE_ME_CHECK(x0.eq(home,x1.val()));
00090     } else {
00091       do {
00092         GECODE_ME_CHECK(x0.gq(home,x1.min()));
00093         GECODE_ME_CHECK(x1.gq(home,x0.min()));
00094       } while (x0.min() != x1.min());
00095       do {
00096         GECODE_ME_CHECK(x0.lq(home,x1.max()));
00097         GECODE_ME_CHECK(x1.lq(home,x0.max()));
00098       } while (x0.max() != x1.max());
00099       if (!x0.assigned())
00100         return ES_FIX;
00101     }
00102     assert(x0.assigned() && x1.assigned());
00103     return home.ES_SUBSUMED(*this);
00104   }
00105 
00106 
00107   /*
00108    * Nary bound consistent equality
00109    *
00110    */
00111 
00112   template<class View>
00113   forceinline
00114   NaryEq<View>::NaryEq(Home home, ViewArray<View>& x)
00115     : NaryPropagator<View,PC_FLOAT_BND>(home,x) {}
00116 
00117   template<class View>
00118   ExecStatus
00119   NaryEq<View>::post(Home home, ViewArray<View>& x) {
00120     x.unique(home);
00121     if (x.size() == 2) {
00122       return Eq<View,View>::post(home,x[0],x[1]);
00123     } else if (x.size() > 2) {
00124       FloatNum l = x[0].min();
00125       FloatNum u = x[0].max();
00126       for (int i=x.size(); i-- > 1; ) {
00127         l = std::max(l,x[i].min());
00128         u = std::min(u,x[i].max());
00129       }
00130       for (int i=x.size(); i--; ) {
00131         GECODE_ME_CHECK(x[i].gq(home,l));
00132         GECODE_ME_CHECK(x[i].lq(home,u));
00133       }
00134       (void) new (home) NaryEq<View>(home,x);
00135     }
00136     return ES_OK;
00137   }
00138 
00139   template<class View>
00140   forceinline
00141   NaryEq<View>::NaryEq(Space& home, NaryEq<View>& p)
00142     : NaryPropagator<View,PC_FLOAT_BND>(home,p) {}
00143 
00144   template<class View>
00145   Actor*
00146   NaryEq<View>::copy(Space& home) {
00147     return new (home) NaryEq<View>(home,*this);
00148   }
00149 
00150   template<class View>
00151   PropCost
00152   NaryEq<View>::cost(const Space&, const ModEventDelta& med) const {
00153     if (View::me(med) == ME_FLOAT_VAL)
00154       return PropCost::unary(PropCost::LO);
00155     else
00156       return PropCost::linear(PropCost::LO, x.size());
00157   }
00158 
00159   template<class View>
00160   ExecStatus
00161   NaryEq<View>::propagate(Space& home, const ModEventDelta& med) {
00162     assert(x.size() > 2);
00163     if (View::me(med) == ME_FLOAT_VAL) {
00164       // One of the variables is assigned
00165       for (int i = 0; ; i++)
00166         if (x[i].assigned()) {
00167           FloatVal n = x[i].val();
00168           x.move_lst(i);
00169           for (int j = x.size(); j--; )
00170             GECODE_ME_CHECK(x[j].eq(home,n));
00171           return home.ES_SUBSUMED(*this);
00172         }
00173       GECODE_NEVER;
00174     }
00175 
00176     FloatNum mn = x[0].min();
00177   restart_min:
00178     for (int i = x.size(); i--; ) {
00179       GECODE_ME_CHECK(x[i].gq(home,mn));
00180       if (mn < x[i].min()) {
00181         mn = x[i].min();
00182         goto restart_min;
00183       }
00184     }
00185     FloatNum mx = x[0].max();
00186   restart_max:
00187     for (int i = x.size(); i--; ) {
00188       GECODE_ME_CHECK(x[i].lq(home,mx));
00189       if (mx > x[i].max()) {
00190         mx = x[i].max();
00191         goto restart_max;
00192       }
00193     }
00194     return x[0].assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00195   }
00196 
00197 
00198 
00199   /*
00200    * Reified bounds consistent equality
00201    *
00202    */
00203 
00204   template<class View, class CtrlView, ReifyMode rm>
00205   forceinline
00206   ReEq<View,CtrlView,rm>::ReEq(Home home, View x0, View x1, CtrlView b)
00207     : Int::ReBinaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,x0,x1,b) {}
00208 
00209   template<class View, class CtrlView, ReifyMode rm>
00210   ExecStatus
00211   ReEq<View,CtrlView,rm>::post(Home home, View x0, View x1, CtrlView b){
00212     if (b.one()) {
00213       if (rm == RM_PMI)
00214         return ES_OK;
00215       return Eq<View,View>::post(home,x0,x1);
00216     }
00217     if (b.zero()) {
00218       if (rm == RM_IMP)
00219         return ES_OK;
00220       return Nq<View,View>::post(home,x0,x1);
00221     }
00222     if (x0 != x1) {
00223       (void) new (home) ReEq(home,x0,x1,b);
00224     } else if (rm != RM_IMP) {
00225       GECODE_ME_CHECK(b.one(home));
00226     }
00227     return ES_OK;
00228   }
00229 
00230 
00231   template<class View, class CtrlView, ReifyMode rm>
00232   forceinline
00233   ReEq<View,CtrlView,rm>::ReEq(Space& home, ReEq& p)
00234     : Int::ReBinaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,p) {}
00235 
00236   template<class View, class CtrlView, ReifyMode rm>
00237   Actor*
00238   ReEq<View,CtrlView,rm>::copy(Space& home) {
00239     return new (home) ReEq<View,CtrlView,rm>(home,*this);
00240   }
00241 
00242   template<class View, class CtrlView, ReifyMode rm>
00243   ExecStatus
00244   ReEq<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
00245     if (b.one()) {
00246       if (rm == RM_PMI)
00247         return home.ES_SUBSUMED(*this);
00248       GECODE_REWRITE(*this,(Eq<View,View>::post(home(*this),x0,x1)));
00249     }
00250     if (b.zero()) {
00251       if (rm == RM_IMP)
00252         return home.ES_SUBSUMED(*this);
00253       GECODE_REWRITE(*this,(Nq<View,View>::post(home(*this),x0,x1)));
00254     }
00255     switch (rtest_eq(x0,x1)) {
00256     case RT_TRUE:
00257       if (rm != RM_IMP)
00258         GECODE_ME_CHECK(b.one_none(home));
00259       break;
00260     case RT_FALSE:
00261       if (rm != RM_PMI)
00262         GECODE_ME_CHECK(b.zero_none(home));
00263       break;
00264     case RT_MAYBE:
00265       return ES_FIX;
00266     default: GECODE_NEVER;
00267     }
00268     return home.ES_SUBSUMED(*this);
00269   }
00270 
00271 
00272   /*
00273    * Reified bounds consistent equality (one variable)
00274    *
00275    */
00276 
00277   template<class View, class CtrlView, ReifyMode rm>
00278   forceinline
00279   ReEqFloat<View,CtrlView,rm>::ReEqFloat
00280   (Home home, View x, FloatVal c0, CtrlView b)
00281     : Int::ReUnaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,x,b), c(c0) {}
00282 
00283   template<class View, class CtrlView, ReifyMode rm>
00284   ExecStatus
00285   ReEqFloat<View,CtrlView,rm>::post(Home home, View x, FloatVal c, CtrlView b) {
00286     if (b.one()) {
00287       if (rm != RM_PMI)
00288         GECODE_ME_CHECK(x.eq(home,c));
00289     } else if (x.assigned()) {
00290       if (overlap(x.val(),c)) {
00291         if (rm != RM_IMP)
00292           GECODE_ME_CHECK(b.one(home));
00293       } else {
00294         if (rm != RM_PMI)
00295           GECODE_ME_CHECK(b.zero(home));
00296       }
00297     } else {
00298       (void) new (home) ReEqFloat(home,x,c,b);
00299     }
00300     return ES_OK;
00301   }
00302 
00303 
00304   template<class View, class CtrlView, ReifyMode rm>
00305   forceinline
00306   ReEqFloat<View,CtrlView,rm>::ReEqFloat(Space& home, ReEqFloat& p)
00307     : Int::ReUnaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,p), c(p.c) {}
00308 
00309   template<class View, class CtrlView, ReifyMode rm>
00310   Actor*
00311   ReEqFloat<View,CtrlView,rm>::copy(Space& home) {
00312     return new (home) ReEqFloat<View,CtrlView,rm>(home,*this);
00313   }
00314 
00315   template<class View, class CtrlView, ReifyMode rm>
00316   ExecStatus
00317   ReEqFloat<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
00318     if (b.one()) {
00319       if (rm != RM_PMI)
00320         GECODE_ME_CHECK(x0.eq(home,c));
00321     } else {
00322       switch (rtest_eq(x0,c)) {
00323       case RT_TRUE:
00324         if (rm != RM_IMP)
00325           GECODE_ME_CHECK(b.one(home));
00326         break;
00327       case RT_FALSE:
00328         if (rm != RM_PMI)
00329           GECODE_ME_CHECK(b.zero(home));
00330         break;
00331       case RT_MAYBE:
00332         return ES_FIX;
00333       default: GECODE_NEVER;
00334       }
00335     }
00336     return home.ES_SUBSUMED(*this);
00337   }
00338 
00339 
00340 }}}
00341 
00342 // STATISTICS: float-prop