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

abs.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  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2004
00009  *     Guido Tack, 2006
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 #include <algorithm>
00037 
00038 namespace Gecode { namespace Int { namespace Arithmetic {
00039 
00040   template<class View, template<class View0,class View1> class Eq>
00041   ExecStatus
00042   prop_abs_bnd(Space& home, Propagator& p, View x0, View x1) {
00043     if (x0.assigned()) {
00044       GECODE_ME_CHECK(x1.eq(home,(x0.val() < 0) ? -x0.val() : x0.val()));
00045       return home.ES_SUBSUMED(p);
00046     }
00047 
00048     if (x1.assigned()) {
00049       if (x0.min() >= 0) {
00050         GECODE_ME_CHECK(x0.eq(home,x1.val()));
00051         return home.ES_SUBSUMED(p);
00052       } else if (x0.max() <= 0) {
00053         GECODE_ME_CHECK(x0.eq(home,-x1.val()));
00054         return home.ES_SUBSUMED(p);
00055       } else if (x1.val() == 0) {
00056         GECODE_ME_CHECK(x0.eq(home,0));
00057         return home.ES_SUBSUMED(p);
00058       } else {
00059         int mp[2] = {-x1.val(),x1.val()};
00060         Iter::Values::Array i(mp,2);
00061         GECODE_ME_CHECK(x0.inter_v(home,i,false));
00062         return home.ES_SUBSUMED(p);
00063       }
00064     }
00065 
00066     if (x0.min() >= 0)
00067       GECODE_REWRITE(p,(Eq<View,View>::post(home(p),x0,x1)));
00068 
00069     if (x0.max() <= 0)
00070       GECODE_REWRITE(p,(Eq<MinusView,View>::post(home(p),MinusView(x0),x1)));
00071 
00072 
00073     GECODE_ME_CHECK(x1.lq(home,std::max(x0.max(),-x0.min())));
00074     GECODE_ME_CHECK(x0.gq(home,-x1.max()));
00075     GECODE_ME_CHECK(x0.lq(home,x1.max()));
00076     if (x1.min() > 0) {
00077       if (-x1.min() < x0.min()) {
00078         GECODE_ME_CHECK(x0.gq(home,x1.min()));
00079       } else if (x0.max() < x1.min()) {
00080         GECODE_ME_CHECK(x0.lq(home,-x1.min()));
00081       }
00082     }
00083     return ES_NOFIX;
00084   }
00085 
00086   template<class View>
00087   forceinline
00088   AbsBnd<View>::AbsBnd(Home home, View x0, View x1)
00089     : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00090 
00091   template<class View>
00092   ExecStatus
00093   AbsBnd<View>::post(Home home, View x0, View x1) {
00094     if (x0.min() >= 0) {
00095       return Rel::EqBnd<View,View>::post(home,x0,x1);
00096     } else if (x0.max() <= 0) {
00097       return Rel::EqBnd<MinusView,View>::post(home,MinusView(x0),x1);
00098     } else {
00099       assert(!x0.assigned());
00100       GECODE_ME_CHECK(x1.gq(home,0));
00101       if (x1.assigned()) {
00102         int mp[2] = {-x1.val(),x1.val()};
00103         Iter::Values::Array i(mp,2);
00104         GECODE_ME_CHECK(x0.inter_v(home,i,false));
00105       } else if (x0 != x1) {
00106         GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
00107         (void) new (home) AbsBnd<View>(home,x0,x1);
00108       }
00109     }
00110     return ES_OK;
00111   }
00112 
00113   template<class View>
00114   forceinline
00115   AbsBnd<View>::AbsBnd(Space& home, AbsBnd<View>& p)
00116     : BinaryPropagator<View,PC_INT_BND>(home,p) {}
00117 
00118   template<class View>
00119   Actor*
00120   AbsBnd<View>::copy(Space& home) {
00121     return new (home) AbsBnd<View>(home,*this);
00122   }
00123 
00124   template<class View>
00125   PropCost
00126   AbsBnd<View>::cost(const Space&, const ModEventDelta& med) const {
00127     if (View::me(med) == ME_INT_VAL)
00128       return PropCost::unary(PropCost::LO);
00129     else
00130       return PropCost::binary(PropCost::LO);
00131   }
00132 
00133   template<class View>
00134   ExecStatus
00135   AbsBnd<View>::propagate(Space& home, const ModEventDelta&) {
00136     return prop_abs_bnd<View,Rel::EqBnd>(home, *this, x0, x1);
00137   }
00138 
00139 
00140 
00141   template<class View>
00142   forceinline
00143   AbsDom<View>::AbsDom(Home home, View x0, View x1)
00144     : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
00145 
00146   template<class View>
00147   ExecStatus
00148   AbsDom<View>::post(Home home, View x0, View x1) {
00149     if (x0.min() >= 0) {
00150       return Rel::EqDom<View,View>::post(home,x0,x1);
00151     } else if (x0.max() <= 0) {
00152       return Rel::EqDom<MinusView,View>::post(home,MinusView(x0),x1);
00153     } else {
00154       assert(!x0.assigned());
00155       GECODE_ME_CHECK(x1.gq(home,0));
00156       if (x1.assigned()) {
00157         int mp[2] = {-x1.val(),x1.val()};
00158         Iter::Values::Array i(mp,2);
00159         GECODE_ME_CHECK(x0.inter_v(home,i,false));
00160       } else if (x0 != x1) {
00161         GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
00162         (void) new (home) AbsDom<View>(home,x0,x1);
00163       }
00164     }
00165     return ES_OK;
00166   }
00167 
00168   template<class View>
00169   forceinline
00170   AbsDom<View>::AbsDom(Space& home, AbsDom<View>& p)
00171     : BinaryPropagator<View,PC_INT_DOM>(home,p) {}
00172 
00173   template<class View>
00174   Actor*
00175   AbsDom<View>::copy(Space& home) {
00176     return new (home) AbsDom<View>(home,*this);
00177   }
00178 
00179   template<class View>
00180   PropCost
00181   AbsDom<View>::cost(const Space&, const ModEventDelta& med) const {
00182     if (View::me(med) == ME_INT_VAL)
00183       return PropCost::unary(PropCost::LO);
00184     else
00185       return PropCost::binary((View::me(med) == ME_INT_DOM) ?
00186                               PropCost::HI : PropCost::LO);
00187   }
00188 
00189   template<class View>
00190   ExecStatus
00191   AbsDom<View>::propagate(Space& home, const ModEventDelta& med) {
00192     if (View::me(med) != ME_INT_DOM) {
00193       GECODE_ES_CHECK((prop_abs_bnd<View,Rel::EqDom>(home, *this, x0, x1)));
00194       return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00195     }
00196 
00197     Region r;
00198 
00199     {
00200       ViewRanges<View> i(x0), j(x0);
00201 
00202       using namespace Iter::Ranges;
00203       Positive<ViewRanges<View> > p(i);
00204       Negative<ViewRanges<View> > n(j);
00205 
00206       Minus m(r,n);
00207 
00208       Union<Positive<ViewRanges<View> >,Minus> u(p,m);
00209 
00210       GECODE_ME_CHECK(x1.inter_r(home,u,false));
00211 
00212     }
00213 
00214     {
00215       ViewRanges<View> i(x1), j(x1);
00216 
00217       using namespace Iter::Ranges;
00218       Minus m(r,j);
00219 
00220       Union<ViewRanges<View>,Minus> u(i,m);
00221 
00222       GECODE_ME_CHECK(x0.inter_r(home,u,false));
00223     }
00224 
00225     if (x1.assigned())
00226       return home.ES_SUBSUMED(*this);
00227 
00228     if (x0.min() >= 0)
00229       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x1)));
00230 
00231     if (x0.max() <= 0) {
00232       MinusView mx0(x0);
00233       GECODE_REWRITE(*this,(Rel::EqDom<MinusView,View>::post(home(*this),mx0,x1)));
00234     }
00235 
00236     return ES_FIX;
00237   }
00238 
00239 }}}
00240 
00241 // STATISTICS: int-prop
00242