Generated on Thu Jul 6 07:06:41 2006 for Gecode by doxygen 1.4.7

minmax.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: 2006-05-23 17:20:37 +0200 (Tue, 23 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3236 $
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 Arithmetic {
00023 
00024   /*
00025    * Ternary bounds-consistent maximum
00026    *
00027    */
00028 
00029   template <class View>
00030   forceinline
00031   Max<View>::Max(Space* home, View x0, View x1, View x2)
00032     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00033 
00034   template <class View>
00035   ExecStatus
00036   Max<View>::post(Space* home, View x0, View x1, View x2) {
00037     if (same(x0,x1))
00038       return Rel::EqBnd<View,View>::post(home,x0,x2);
00039     (void) new (home) Max<View>(home,x0,x1,x2);
00040     return ES_OK;
00041   }
00042 
00043   template <class View>
00044   forceinline
00045   Max<View>::Max(Space* home, bool share, Max<View>& p)
00046     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00047 
00048   template <class View>
00049   forceinline
00050   Max<View>::Max(Space* home, bool share, Propagator& p,
00051                  View x0, View x1, View x2)
00052     : TernaryPropagator<View,PC_INT_BND>(home,share,p,x0,x1,x2) {}
00053 
00054   template <class View>
00055   Actor*
00056   Max<View>::copy(Space* home, bool share) {
00057     return new (home) Max<View>(home,share,*this);
00058   }
00059 
00061 #define GECODE_CM(TELL)                         \
00062 {                                               \
00063   ModEvent me = (TELL);                         \
00064   if (me_failed(me))   return ES_FAILED;        \
00065   if (me_modified(me)) mod = true;              \
00066 }
00067 
00068   template <class View>
00069   ExecStatus
00070   Max<View>::propagate(Space* home) {
00071     bool mod = false;
00072     do {
00073       mod = false;
00074       GECODE_CM(x2.lq(home,std::max(x0.max(),x1.max())));
00075       GECODE_CM(x2.gq(home,std::max(x0.min(),x1.min())));
00076       GECODE_CM(x0.lq(home,x2.max()));
00077       GECODE_CM(x1.lq(home,x2.max()));
00078     } while (mod);
00079     if (x0.max() <= x1.min()) {
00080       GECODE_ES_CHECK((Rel::EqBnd<View,View>::post(home,x1,x2)));
00081       return ES_SUBSUMED;
00082     }
00083     if (x1.max() <= x0.min()) {
00084       GECODE_ES_CHECK((Rel::EqBnd<View,View>::post(home,x0,x2)));
00085       return ES_SUBSUMED;
00086     }
00087     return x0.assigned() && x1.assigned() && x2.assigned() ? ES_SUBSUMED : ES_FIX;
00088   }
00089 
00090 #undef GECODE_CM
00091 
00092 
00093 
00094   /*
00095    * Nary bounds-consistent maximum
00096    *
00097    */
00098 
00099   template <class View>
00100   forceinline
00101   NaryMax<View>::NaryMax(Space* home, ViewArray<View>& x, View y)
00102     : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
00103 
00104   template <class View>
00105   ExecStatus
00106   NaryMax<View>::post(Space* home, ViewArray<View>& x, View y) {
00107     assert(x.size() > 0);
00108     x.unique();
00109     if (x.size() == 1)
00110       return Rel::EqBnd<View,View>::post(home,x[0],y);
00111     if (x.size() == 2)
00112       return Max<View>::post(home,x[0],x[1],y);
00113     (void) new (home) NaryMax<View>(home,x,y);
00114     return ES_OK;
00115   }
00116 
00117   template <class View>
00118   forceinline
00119   NaryMax<View>::NaryMax(Space* home, bool share, NaryMax<View>& p)
00120     : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
00121 
00122   template <class View>
00123   Actor*
00124   NaryMax<View>::copy(Space* home, bool share) {
00125     if (x.size() == 1)
00126       return new (home) Rel::EqBnd<View,View>(home,share,*this,x[0],y);
00127     if (x.size() == 2)
00128       return new (home) Max<View>(home,share,*this,x[0],x[1],y);
00129     return new (home) NaryMax<View>(home,share,*this);
00130   }
00131 
00132   template <class View>
00133   ExecStatus
00134   NaryMax<View>::propagate(Space* home) {
00135     int maxmax = Limits::Int::int_min-1;
00136     int maxmin = Limits::Int::int_min-1;
00137     for (int i = x.size(); i--; ) {
00138       maxmax = std::max(x[i].max(),maxmax);
00139       maxmin = std::max(x[i].min(),maxmin);
00140     }
00141     GECODE_ME_CHECK(y.lq(home,maxmax)); 
00142     GECODE_ME_CHECK(y.gq(home,maxmin));
00143     ExecStatus es = ES_FIX;
00144     maxmin = y.min();
00145     maxmax = y.max();
00146     bool assigned = true;
00147     for (int i = x.size(); i--; ) {
00148       if (x[i].modified())
00149         es = ES_NOFIX;
00150       ModEvent me = x[i].lq(home,maxmax);
00151       if (me == ME_INT_FAILED)
00152         return ES_FAILED;
00153       if (me_modified(me) && (x[i].max() != maxmax))
00154         es = ES_NOFIX;
00155       if (x[i].max() < maxmin) {
00156         x.move_lst(i,home,this,PC_INT_BND);
00157       } else if (!x[i].assigned())
00158         assigned = false;
00159     }
00160     if (x.size() == 0)
00161       return ES_FAILED;
00162     return (assigned && y.assigned()) ? ES_SUBSUMED : es;
00163   }
00164 
00165 }}}
00166 
00167 // STATISTICS: int-prop
00168