max.hpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
00011  *     $Revision: 15253 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/int/rel.hh>
00039 
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041 
00042   /*
00043    * Ternary bounds consistent maximum
00044    *
00045    */
00046 
00047   template<class View>
00048   forceinline ExecStatus
00049   prop_max_bnd(Space& home, View x0, View x1, View x2) {
00050     bool mod = false;
00051     do {
00052       mod = false;
00053       {
00054         ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
00055         if (me_failed(me)) return ES_FAILED;
00056         mod |= me_modified(me);
00057       }
00058       {
00059         ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
00060         if (me_failed(me)) return ES_FAILED;
00061         mod |= me_modified(me);
00062       }
00063       {
00064         ModEvent me = x0.lq(home,x2.max());
00065         if (me_failed(me)) return ES_FAILED;
00066         mod |= me_modified(me);
00067       }
00068       {
00069         ModEvent me = x1.lq(home,x2.max());
00070         if (me_failed(me)) return ES_FAILED;
00071         mod |= me_modified(me);
00072       }
00073     } while (mod);
00074     return ES_OK;
00075   }
00076 
00077   template<class View>
00078   forceinline
00079   MaxBnd<View>::MaxBnd(Home home, View x0, View x1, View x2)
00080     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00081 
00082   template<class View>
00083   ExecStatus
00084   MaxBnd<View>::post(Home home, View x0, View x1, View x2) {
00085     GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
00086     GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
00087     if (same(x0,x1))
00088       return Rel::EqBnd<View,View>::post(home,x0,x2);
00089     if (same(x0,x2))
00090       return Rel::Lq<View,View>::post(home,x1,x2);
00091     if (same(x1,x2))
00092       return Rel::Lq<View,View>::post(home,x0,x2);
00093     (void) new (home) MaxBnd<View>(home,x0,x1,x2);
00094     return ES_OK;
00095   }
00096 
00097   template<class View>
00098   forceinline
00099   MaxBnd<View>::MaxBnd(Space& home, bool share, MaxBnd<View>& p)
00100     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00101 
00102   template<class View>
00103   forceinline
00104   MaxBnd<View>::MaxBnd(Space& home, bool share, Propagator& p,
00105                  View x0, View x1, View x2)
00106     : TernaryPropagator<View,PC_INT_BND>(home,share,p,x0,x1,x2) {}
00107 
00108   template<class View>
00109   Actor*
00110   MaxBnd<View>::copy(Space& home, bool share) {
00111     return new (home) MaxBnd<View>(home,share,*this);
00112   }
00113 
00114   template<class View>
00115   ExecStatus
00116   MaxBnd<View>::propagate(Space& home, const ModEventDelta&) {
00117     GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
00118     if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
00119       GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x1,x2)));
00120     if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
00121       GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x0,x2)));
00122     return x0.assigned() && x1.assigned() && x2.assigned() ?
00123       home.ES_SUBSUMED(*this) : ES_FIX;
00124   }
00125 
00126   /*
00127    * Nary bounds consistent maximum
00128    *
00129    */
00130 
00131   template<class View>
00132   forceinline
00133   NaryMaxBnd<View>::NaryMaxBnd(Home home, ViewArray<View>& x, View y)
00134     : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
00135 
00136   template<class View>
00137   ExecStatus
00138   NaryMaxBnd<View>::post(Home home, ViewArray<View>& x, View y) {
00139     assert(x.size() > 0);
00140     x.unique(home);
00141     if (x.size() == 1)
00142       return Rel::EqBnd<View,View>::post(home,x[0],y);
00143     if (x.size() == 2)
00144       return MaxBnd<View>::post(home,x[0],x[1],y);
00145     int l = Int::Limits::min;
00146     int u = Int::Limits::min;
00147     for (int i=x.size(); i--; ) {
00148       l = std::max(l,x[i].min());
00149       u = std::max(u,x[i].max());
00150     }
00151     GECODE_ME_CHECK(y.gq(home,l));
00152     GECODE_ME_CHECK(y.lq(home,u));
00153     if (x.same(home,y)) {
00154       // Check whether y occurs in x
00155       for (int i=x.size(); i--; )
00156         GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y)));
00157     } else {
00158       (void) new (home) NaryMaxBnd<View>(home,x,y);
00159     }
00160     return ES_OK;
00161   }
00162 
00163   template<class View>
00164   forceinline
00165   NaryMaxBnd<View>::NaryMaxBnd(Space& home, bool share, NaryMaxBnd<View>& p)
00166     : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
00167 
00168   template<class View>
00169   Actor*
00170   NaryMaxBnd<View>::copy(Space& home, bool share) {
00171     if (x.size() == 1)
00172       return new (home) Rel::EqBnd<View,View>(home,share,*this,x[0],y);
00173     if (x.size() == 2)
00174       return new (home) MaxBnd<View>(home,share,*this,x[0],x[1],y);
00175     return new (home) NaryMaxBnd<View>(home,share,*this);
00176   }
00177 
00179   enum MaxPropStatus {
00180     MPS_ASSIGNED  = 1<<0, 
00181     MPS_REMOVED   = 1<<1, 
00182     MPS_NEW_BOUND = 1<<2  
00183   };
00184 
00185   template<class View>
00186   forceinline ExecStatus
00187   prop_nary_max_bnd(Space& home, Propagator& p,
00188                     ViewArray<View>& x, View y, PropCond pc) {
00189   rerun:
00190     assert(x.size() > 0);
00191     int maxmax = x[x.size()-1].max();
00192     int maxmin = x[x.size()-1].min();
00193     for (int i = x.size()-1; i--; ) {
00194       maxmax = std::max(x[i].max(),maxmax);
00195       maxmin = std::max(x[i].min(),maxmin);
00196     }
00197     GECODE_ME_CHECK(y.lq(home,maxmax));
00198     GECODE_ME_CHECK(y.gq(home,maxmin));
00199     maxmin = y.min();
00200     maxmax = y.max();
00201     int status = MPS_ASSIGNED;
00202     for (int i = x.size(); i--; ) {
00203       ModEvent me = x[i].lq(home,maxmax);
00204       if (me == ME_INT_FAILED)
00205         return ES_FAILED;
00206       if (me_modified(me) && (x[i].max() != maxmax))
00207         status |= MPS_NEW_BOUND;
00208       if (x[i].max() < maxmin) {
00209         x.move_lst(i,home,p,pc);
00210         status |= MPS_REMOVED;
00211       } else if (!x[i].assigned())
00212         status &= ~MPS_ASSIGNED;
00213     }
00214     if (x.size() == 0)
00215       return ES_FAILED;
00216     if ((status & MPS_REMOVED) != 0)
00217       goto rerun;
00218     if (((status & MPS_ASSIGNED) != 0) && y.assigned())
00219       return home.ES_SUBSUMED(p);
00220     return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
00221   }
00222 
00223   template<class View>
00224   ExecStatus
00225   NaryMaxBnd<View>::propagate(Space& home, const ModEventDelta&) {
00226     ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_BND);
00227     GECODE_ES_CHECK(es);
00228     if (x.size() == 1)
00229       GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x[0],y)));
00230     return es;
00231   }
00232 
00233 
00234   /*
00235    * Ternary domain consistent maximum
00236    *
00237    */
00238 
00239   template<class View>
00240   forceinline
00241   MaxDom<View>::MaxDom(Home home, View x0, View x1, View x2)
00242     : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {}
00243 
00244   template<class View>
00245   ExecStatus
00246   MaxDom<View>::post(Home home, View x0, View x1, View x2) {
00247     GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
00248     GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
00249     if (same(x0,x1))
00250       return Rel::EqDom<View,View>::post(home,x0,x2);
00251     if (same(x0,x2))
00252       return Rel::Lq<View,View>::post(home,x1,x2);
00253     if (same(x1,x2))
00254       return Rel::Lq<View,View>::post(home,x0,x2);
00255     (void) new (home) MaxDom<View>(home,x0,x1,x2);
00256     return ES_OK;
00257   }
00258 
00259   template<class View>
00260   forceinline
00261   MaxDom<View>::MaxDom(Space& home, bool share, MaxDom<View>& p)
00262     : TernaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00263 
00264   template<class View>
00265   forceinline
00266   MaxDom<View>::MaxDom(Space& home, bool share, Propagator& p,
00267                        View x0, View x1, View x2)
00268     : TernaryPropagator<View,PC_INT_DOM>(home,share,p,x0,x1,x2) {}
00269 
00270   template<class View>
00271   Actor*
00272   MaxDom<View>::copy(Space& home, bool share) {
00273     return new (home) MaxDom<View>(home,share,*this);
00274   }
00275 
00276   template<class View>
00277   PropCost
00278   MaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
00279     return PropCost::ternary((View::me(med) == ME_INT_DOM) ?
00280                              PropCost::HI : PropCost::LO);
00281   }
00282 
00283   template<class View>
00284   ExecStatus
00285   MaxDom<View>::propagate(Space& home, const ModEventDelta& med) {
00286     if (View::me(med) != ME_INT_DOM) {
00287       GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
00288       if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
00289         GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
00290       if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
00291         GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
00292       return x0.assigned() && x1.assigned() && x2.assigned() ?
00293         home.ES_SUBSUMED(*this) :
00294         home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00295     }
00296     ViewRanges<View> r0(x0), r1(x1);
00297     Iter::Ranges::Union<ViewRanges<View>,ViewRanges<View> > u(r0,r1);
00298     GECODE_ME_CHECK(x2.inter_r(home,u,false));
00299     if (rtest_nq_dom(x0,x2) == RT_TRUE) {
00300       GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x0,x2)));
00301       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
00302     }
00303     if (rtest_nq_dom(x1,x2) == RT_TRUE) {
00304       GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x1,x2)));
00305       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
00306     }
00307     return ES_FIX;
00308   }
00309 
00310   /*
00311    * Nary domain consistent maximum
00312    *
00313    */
00314 
00315   template<class View>
00316   forceinline
00317   NaryMaxDom<View>::NaryMaxDom(Home home, ViewArray<View>& x, View y)
00318     : NaryOnePropagator<View,PC_INT_DOM>(home,x,y) {}
00319 
00320   template<class View>
00321   ExecStatus
00322   NaryMaxDom<View>::post(Home home, ViewArray<View>& x, View y) {
00323     assert(x.size() > 0);
00324     x.unique(home);
00325     if (x.size() == 1)
00326       return Rel::EqDom<View,View>::post(home,x[0],y);
00327     if (x.size() == 2)
00328       return MaxDom<View>::post(home,x[0],x[1],y);
00329     int l = Int::Limits::min;
00330     int u = Int::Limits::min;
00331     for (int i=x.size(); i--; ) {
00332       l = std::max(l,x[i].min());
00333       u = std::max(u,x[i].max());
00334     }
00335     GECODE_ME_CHECK(y.gq(home,l));
00336     GECODE_ME_CHECK(y.lq(home,u));
00337     if (x.same(home,y)) {
00338       // Check whether y occurs in x
00339       for (int i=x.size(); i--; )
00340         GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y)));
00341     } else {
00342       (void) new (home) NaryMaxDom<View>(home,x,y);
00343     }
00344     return ES_OK;
00345   }
00346 
00347   template<class View>
00348   forceinline
00349   NaryMaxDom<View>::NaryMaxDom(Space& home, bool share, NaryMaxDom<View>& p)
00350     : NaryOnePropagator<View,PC_INT_DOM>(home,share,p) {}
00351 
00352   template<class View>
00353   Actor*
00354   NaryMaxDom<View>::copy(Space& home, bool share) {
00355     if (x.size() == 1)
00356       return new (home) Rel::EqDom<View,View>(home,share,*this,x[0],y);
00357     if (x.size() == 2)
00358       return new (home) MaxDom<View>(home,share,*this,x[0],x[1],y);
00359     return new (home) NaryMaxDom<View>(home,share,*this);
00360   }
00361 
00362   template<class View>
00363   PropCost
00364   NaryMaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
00365     if (View::me(med) == ME_INT_DOM)
00366       return PropCost::linear(PropCost::HI, y.size());
00367     else
00368       return PropCost::linear(PropCost::LO, x.size());
00369   }
00370 
00371   template<class View>
00372   ExecStatus
00373   NaryMaxDom<View>::propagate(Space& home, const ModEventDelta& med) {
00374     if (View::me(med) != ME_INT_DOM) {
00375       ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_DOM);
00376       GECODE_ES_CHECK(es);
00377       return (es == ES_FIX) ?
00378         home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)) :
00379         home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00380     }
00381     Region r(home);
00382     ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size());
00383     for (int i = x.size(); i--; ) {
00384       ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi;
00385     }
00386     Iter::Ranges::NaryUnion u(r, i_x, x.size());
00387     GECODE_ME_CHECK(y.inter_r(home,u,false));
00388     for (int i = x.size(); i--; )
00389       if (rtest_nq_dom(x[i],y) == RT_TRUE) {
00390         GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x[i],y)));
00391         x.move_lst(i,home,*this,PC_INT_DOM);
00392       }
00393     assert(x.size() > 0);
00394     if (x.size() == 1)
00395       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x[0],y)));
00396     return ES_FIX;
00397   }
00398 
00399 }}}
00400 
00401 // STATISTICS: int-prop
00402