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

min-max.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 #include <cmath>
00037 
00038 namespace Gecode { namespace Float { namespace Arithmetic {
00039 
00040   /*
00041    * Bounds consistent min propagator
00042    *
00043    */
00044   template<class A, class B, class C>
00045   forceinline
00046   Min<A,B,C>::Min(Home home, A x0, B x1, C x2)
00047     : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,x0,x1,x2) {}
00048 
00049   template<class A, class B, class C>
00050   forceinline
00051   Min<A,B,C>::Min(Space& home, Min<A,B,C>& p)
00052     : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,p) {}
00053 
00054   template<class A, class B, class C>
00055   forceinline
00056   Min<A,B,C>::Min(Space& home, Propagator& p,
00057                   A x0, B x1, C x2)
00058     : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,p,x0,x1,x2) {}
00059 
00060   template<class A, class B, class C>
00061   Actor*
00062   Min<A,B,C>::copy(Space& home) {
00063     return new (home) Min<A,B,C>(home,*this);
00064   }
00065 
00066   template<class A, class B, class C>
00067   ExecStatus
00068   Min<A,B,C>::post(Home home, A x0, B x1, C x2) {
00069     GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
00070     GECODE_ME_CHECK(x0.gq(home,x2.min()));
00071     GECODE_ME_CHECK(x1.gq(home,x2.min()));
00072     (void) new (home) Min<A,B,C>(home,x0,x1,x2);
00073     return ES_OK;
00074   }
00075 
00076   template<class A, class B, class C>
00077   ExecStatus
00078   Min<A,B,C>::propagate(Space& home, const ModEventDelta&) {
00079     GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
00080     GECODE_ME_CHECK(x0.gq(home,x2.min()));
00081     GECODE_ME_CHECK(x1.gq(home,x2.min()));
00082     if (x0 == x1) {
00083       GECODE_ME_CHECK(x0.lq(home,x2.max()));
00084     } else {
00085       if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.lq(home,x2.max()));
00086       if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.lq(home,x2.max()));
00087     }
00088     return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00089   }
00090 
00091   /*
00092    * Bounds consistent max propagator
00093    *
00094    */
00095 
00096   template<class A, class B, class C>
00097   forceinline
00098   Max<A,B,C>::Max(Home home, A x0, B x1, C x2)
00099     : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,x0,x1,x2) {}
00100 
00101   template<class A, class B, class C>
00102   forceinline
00103   Max<A,B,C>::Max(Space& home, Max<A,B,C>& p)
00104     : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,p) {}
00105 
00106   template<class A, class B, class C>
00107   forceinline
00108   Max<A,B,C>::Max(Space& home, Propagator& p,
00109                   A x0, B x1, C x2)
00110     : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,p,x0,x1,x2) {}
00111 
00112   template<class A, class B, class C>
00113   Actor*
00114   Max<A,B,C>::copy(Space& home) {
00115     return new (home) Max<A,B,C>(home,*this);
00116   }
00117 
00118   template<class A, class B, class C>
00119   ExecStatus
00120   Max<A,B,C>::post(Home home, A x0, B x1, C x2) {
00121     GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
00122     GECODE_ME_CHECK(x0.lq(home,x2.max()));
00123     GECODE_ME_CHECK(x1.lq(home,x2.max()));
00124     (void) new (home) Max<A,B,C>(home,x0,x1,x2);
00125     return ES_OK;
00126   }
00127 
00128   template<class A, class B, class C>
00129   ExecStatus
00130   Max<A,B,C>::propagate(Space& home, const ModEventDelta&) {
00131     GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
00132     GECODE_ME_CHECK(x0.lq(home,x2.max()));
00133     GECODE_ME_CHECK(x1.lq(home,x2.max()));
00134     if (x0 == x1) {
00135       GECODE_ME_CHECK(x0.gq(home,x2.min()));
00136     } else {
00137       if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.gq(home,x2.min()));
00138       if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.gq(home,x2.min()));
00139     }
00140     return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00141   }
00142 
00143   /*
00144    * Nary bounds consistent maximum
00145    *
00146    */
00147 
00148   template<class View>
00149   forceinline
00150   NaryMax<View>::NaryMax(Home home, ViewArray<View>& x, View y)
00151     : NaryOnePropagator<View,PC_FLOAT_BND>(home,x,y) {}
00152 
00153   template<class View>
00154   ExecStatus
00155   NaryMax<View>::post(Home home, ViewArray<View>& x, View y) {
00156     assert(x.size() > 0);
00157     x.unique();
00158     if (x.size() == 1)
00159       return Rel::Eq<View,View>::post(home,x[0],y);
00160     if (x.size() == 2)
00161       return Max<View,View,View>::post(home,x[0],x[1],y);
00162     FloatNum l = Float::Limits::min;
00163     FloatNum u = Float::Limits::min;
00164     for (int i=x.size(); i--; ) {
00165       l = std::max(l,x[i].min());
00166       u = std::max(u,x[i].max());
00167     }
00168     GECODE_ME_CHECK(y.gq(home,l));
00169     GECODE_ME_CHECK(y.lq(home,u));
00170     if (x.same(y)) {
00171       // Check whether y occurs in x
00172       for (int i=x.size(); i--; )
00173         GECODE_ES_CHECK((Rel::Lq<View>::post(home,x[i],y)));
00174     } else {
00175       (void) new (home) NaryMax<View>(home,x,y);
00176     }
00177     return ES_OK;
00178   }
00179 
00180   template<class View>
00181   forceinline
00182   NaryMax<View>::NaryMax(Space& home, NaryMax<View>& p)
00183     : NaryOnePropagator<View,PC_FLOAT_BND>(home,p) {}
00184 
00185   template<class View>
00186   Actor*
00187   NaryMax<View>::copy(Space& home) {
00188     if (x.size() == 1)
00189       return new (home) Rel::Eq<View,View>(home,*this,x[0],y);
00190     if (x.size() == 2)
00191       return new (home) Max<View,View,View>(home,*this,x[0],x[1],y);
00192     return new (home) NaryMax<View>(home,*this);
00193   }
00194 
00196   enum MaxPropStatus {
00197     MPS_ASSIGNED  = 1<<0, 
00198     MPS_REMOVED   = 1<<1, 
00199     MPS_NEW_BOUND = 1<<2  
00200   };
00201 
00202   template<class View>
00203   forceinline ExecStatus
00204   prop_nary_max(Space& home, Propagator& p,
00205                 ViewArray<View>& x, View y, PropCond pc) {
00206   rerun:
00207     assert(x.size() > 0);
00208     FloatNum maxmax = x[x.size()-1].max();
00209     FloatNum maxmin = x[x.size()-1].min();
00210     for (int i = x.size()-1; i--; ) {
00211       maxmax = std::max(x[i].max(),maxmax);
00212       maxmin = std::max(x[i].min(),maxmin);
00213     }
00214     GECODE_ME_CHECK(y.lq(home,maxmax));
00215     GECODE_ME_CHECK(y.gq(home,maxmin));
00216     maxmin = y.min();
00217     maxmax = y.max();
00218     int status = MPS_ASSIGNED;
00219     for (int i = x.size(); i--; ) {
00220       ModEvent me = x[i].lq(home,maxmax);
00221       if (me == ME_FLOAT_FAILED)
00222         return ES_FAILED;
00223       if (me_modified(me) && (x[i].max() != maxmax))
00224         status |= MPS_NEW_BOUND;
00225       if (x[i].max() < maxmin) {
00226         x.move_lst(i,home,p,pc);
00227         status |= MPS_REMOVED;
00228       } else if (!x[i].assigned())
00229         status &= ~MPS_ASSIGNED;
00230     }
00231     if (x.size() == 0)
00232       return ES_FAILED;
00233     if ((status & MPS_REMOVED) != 0)
00234       goto rerun;
00235     if (((status & MPS_ASSIGNED) != 0) && y.assigned())
00236       return home.ES_SUBSUMED(p);
00237     return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
00238   }
00239 
00240   template<class View>
00241   ExecStatus
00242   NaryMax<View>::propagate(Space& home, const ModEventDelta&) {
00243     return prop_nary_max(home,*this,x,y,PC_FLOAT_BND);
00244   }
00245 
00246 }}}
00247 
00248 // STATISTICS: float-prop
00249