Generated on Wed Jan 4 17:49:08 2006 for Gecode by doxygen 1.4.6

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: 2005-11-04 21:34:08 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2503 $
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>::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   Actor*
00050   Max<View>::copy(Space* home, bool share) {
00051     return new (home) Max<View>(home,share,*this);
00052   }
00053 
00054   template <class View>
00055   ExecStatus
00056   Max<View>::propagate(Space* home) {
00057     GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
00058     GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
00059     ExecStatus es = (x0.modified() || x1.modified()) ? ES_NOFIX : ES_FIX;
00060     GECODE_ME_CHECK(x0.lq(home,x2.max()));
00061     GECODE_ME_CHECK(x1.lq(home,x2.max()));
00062     if (x0.max() <= x1.min()) {
00063       GECODE_ES_CHECK(Rel::EqBnd<View>::post(home,x1,x2)); 
00064       return ES_SUBSUMED;
00065     }
00066     if (x1.max() <= x0.min()) {
00067       GECODE_ES_CHECK(Rel::EqBnd<View>::post(home,x0,x2)); 
00068       return ES_SUBSUMED;
00069     }
00070     return x0.assigned() && x1.assigned() && x2.assigned() ? ES_SUBSUMED : es;
00071   }
00072 
00073 
00074 
00075 
00076   /*
00077    * Nary bounds-consistent maximum
00078    *
00079    */
00080 
00081   template <class View>
00082   forceinline
00083   NaryMax<View>::NaryMax(Space* home, ViewArray<View>& x, View y)
00084     : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
00085 
00086   template <class View>
00087   ExecStatus
00088   NaryMax<View>::post(Space* home, ViewArray<View>& x, View y) {
00089     assert(x.size() > 0);
00090     x.unique();
00091     if (x.size() == 1)
00092       return Rel::EqBnd<View>::post(home,x[0],y);
00093     if (x.size() == 2)
00094       return Max<View>::post(home,x[0],x[1],y);
00095     (void) new (home) NaryMax<View>(home,x,y);
00096     return ES_OK;
00097   }
00098 
00099   template <class View>
00100   forceinline
00101   NaryMax<View>::NaryMax(Space* home, bool share, NaryMax<View>& p)
00102     : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
00103 
00104   template <class View>
00105   Actor*
00106   NaryMax<View>::copy(Space* home, bool share) {
00107     return new (home) NaryMax<View>(home,share,*this);
00108   }
00109 
00110   template <class View>
00111   ExecStatus
00112   NaryMax<View>::propagate(Space* home) {
00113     int maxmax = Limits::Int::int_min-1;
00114     int maxmin = Limits::Int::int_min-1;
00115     for (int i = x.size(); i--; ) {
00116       maxmax = std::max(x[i].max(),maxmax);
00117       maxmin = std::max(x[i].min(),maxmin);
00118     }
00119     GECODE_ME_CHECK(y.lq(home,maxmax)); 
00120     GECODE_ME_CHECK(y.gq(home,maxmin));
00121     ExecStatus es = ES_FIX;
00122     maxmin = y.min();
00123     maxmax = y.max();
00124     bool assigned = true;
00125     for (int i = x.size(); i--; ) {
00126       if (x[i].modified())
00127         es = ES_NOFIX;
00128       ModEvent me = x[i].lq(home,maxmax);
00129       if (me == ME_INT_FAILED)
00130         return ES_FAILED;
00131       if (x[i].max() < maxmin) {
00132         x.move_lst(i,this,PC_INT_BND);
00133       } else {
00134         if (me_modified(me) && (x[i].max() != maxmax))
00135           es = ES_NOFIX;
00136         if (!x[i].assigned())
00137           assigned = false;
00138       }
00139     }
00140     if (x.size() == 0)
00141       return ES_FAILED;
00142     if (x.size() == 1) {
00143       GECODE_ES_CHECK(Rel::EqBnd<View>::post(home,x[0],y));
00144       return ES_SUBSUMED;
00145     }
00146     return (assigned && y.assigned()) ? ES_SUBSUMED : es;
00147   }
00148 
00149 }}}
00150 
00151 // STATISTICS: int-prop
00152