00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include "gecode/int/rel.hh"
00039
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041
00042
00043
00044
00045
00046
00047 template <class View>
00048 forceinline
00049 Max<View>::Max(Space* home, View x0, View x1, View x2)
00050 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00051
00052 template <class View>
00053 ExecStatus
00054 Max<View>::post(Space* home, View x0, View x1, View x2) {
00055 if (same(x0,x1))
00056 return Rel::EqBnd<View,View>::post(home,x0,x2);
00057 if (same(x0,x2))
00058 return Rel::Lq<View>::post(home,x1,x2);
00059 if (same(x1,x2))
00060 return Rel::Lq<View>::post(home,x0,x2);
00061 (void) new (home) Max<View>(home,x0,x1,x2);
00062 return ES_OK;
00063 }
00064
00065 template <class View>
00066 forceinline void
00067 Max<View>::post(Space* home, Reflection::VarMap& vars,
00068 const Reflection::ActorSpec& spec) {
00069 spec.checkArity(3);
00070 View x0(home, vars, spec[0]);
00071 View x1(home, vars, spec[1]);
00072 View x2(home, vars, spec[2]);
00073 (void) new (home) Max<View>(home,x0,x1,x2);
00074 }
00075
00076 template <class View>
00077 forceinline
00078 Max<View>::Max(Space* home, bool share, Max<View>& p)
00079 : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00080
00081 template <class View>
00082 forceinline
00083 Max<View>::Max(Space* home, bool share, Propagator& p,
00084 View x0, View x1, View x2)
00085 : TernaryPropagator<View,PC_INT_BND>(home,share,p,x0,x1,x2) {}
00086
00087 template <class View>
00088 Actor*
00089 Max<View>::copy(Space* home, bool share) {
00090 return new (home) Max<View>(home,share,*this);
00091 }
00092
00093 template <class View>
00094 ExecStatus
00095 Max<View>::propagate(Space* home, ModEventDelta) {
00096 bool mod = false;
00097 do {
00098 mod = false;
00099 {
00100 ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
00101 if (me_failed(me)) return ES_FAILED;
00102 mod |= me_modified(me);
00103 }
00104 {
00105 ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
00106 if (me_failed(me)) return ES_FAILED;
00107 mod |= me_modified(me);
00108 }
00109 {
00110 ModEvent me = x0.lq(home,x2.max());
00111 if (me_failed(me)) return ES_FAILED;
00112 mod |= me_modified(me);
00113 }
00114 {
00115 ModEvent me = x1.lq(home,x2.max());
00116 if (me_failed(me)) return ES_FAILED;
00117 mod |= me_modified(me);
00118 }
00119 } while (mod);
00120 if (x0.max() <= x1.min())
00121 GECODE_REWRITE(this,(Rel::EqBnd<View,View>::post(home,x1,x2)));
00122 if (x1.max() <= x0.min())
00123 GECODE_REWRITE(this,(Rel::EqBnd<View,View>::post(home,x0,x2)));
00124 return x0.assigned() && x1.assigned() && x2.assigned() ?
00125 ES_SUBSUMED(this,sizeof(*this)) : ES_FIX;
00126 }
00127
00128 template <class View>
00129 Support::Symbol
00130 Max<View>::ati(void) {
00131 return Reflection::mangle<View>("Gecode::Int::Arithmetic::Max");
00132 }
00133
00134 template <class View>
00135 Reflection::ActorSpec
00136 Max<View>::spec(const Space* home, Reflection::VarMap& m) const {
00137 return TernaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00138 }
00139
00140
00141
00142
00143
00144
00145 template <class View>
00146 forceinline
00147 NaryMax<View>::NaryMax(Space* home, ViewArray<View>& x, View y)
00148 : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
00149
00150 template <class View>
00151 ExecStatus
00152 NaryMax<View>::post(Space* home, ViewArray<View>& x, View y) {
00153 assert(x.size() > 0);
00154 x.unique();
00155 if (x.size() == 1)
00156 return Rel::EqBnd<View,View>::post(home,x[0],y);
00157 if (x.size() == 2)
00158 return Max<View>::post(home,x[0],x[1],y);
00159 if (x.same(y)) {
00160
00161 for (int i=x.size(); i--; )
00162 GECODE_ES_CHECK(Rel::Lq<View>::post(home,x[i],y));
00163 } else {
00164 (void) new (home) NaryMax<View>(home,x,y);
00165 }
00166 return ES_OK;
00167 }
00168
00169 template <class View>
00170 forceinline void
00171 NaryMax<View>::post(Space* home, Reflection::VarMap& vars,
00172 const Reflection::ActorSpec& spec) {
00173 spec.checkArity(2);
00174 ViewArray<View> x(home, vars, spec[0]);
00175 View y(home, vars, spec[1]);
00176 (void) new (home) NaryMax<View>(home,x,y);
00177 }
00178
00179 template <class View>
00180 forceinline
00181 NaryMax<View>::NaryMax(Space* home, bool share, NaryMax<View>& p)
00182 : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
00183
00184 template <class View>
00185 Actor*
00186 NaryMax<View>::copy(Space* home, bool share) {
00187 if (x.size() == 1)
00188 return new (home) Rel::EqBnd<View,View>(home,share,*this,x[0],y);
00189 if (x.size() == 2)
00190 return new (home) Max<View>(home,share,*this,x[0],x[1],y);
00191 return new (home) NaryMax<View>(home,share,*this);
00192 }
00193
00195 enum MaxPropStatus {
00196 MPS_ASSIGNED = 1<<0,
00197 MPS_REMOVED = 1<<1,
00198 MPS_NEW_BOUND = 1<<2
00199 };
00200
00201 template <class View>
00202 ExecStatus
00203 NaryMax<View>::propagate(Space* home, ModEventDelta) {
00204 rerun:
00205 assert(x.size() > 0);
00206 int maxmax = x[x.size()-1].max();
00207 int maxmin = x[x.size()-1].min();
00208 for (int i = x.size()-1; i--; ) {
00209 maxmax = std::max(x[i].max(),maxmax);
00210 maxmin = std::max(x[i].min(),maxmin);
00211 }
00212 GECODE_ME_CHECK(y.lq(home,maxmax));
00213 GECODE_ME_CHECK(y.gq(home,maxmin));
00214 maxmin = y.min();
00215 maxmax = y.max();
00216 int status = MPS_ASSIGNED;
00217 for (int i = x.size(); i--; ) {
00218 ModEvent me = x[i].lq(home,maxmax);
00219 if (me == ME_INT_FAILED)
00220 return ES_FAILED;
00221 if (me_modified(me) && (x[i].max() != maxmax))
00222 status |= MPS_NEW_BOUND;
00223 if (x[i].max() < maxmin) {
00224 x.move_lst(i,home,this,PC_INT_BND);
00225 status |= MPS_REMOVED;
00226 } else if (!x[i].assigned())
00227 status &= ~MPS_ASSIGNED;
00228 }
00229 if (x.size() == 0)
00230 return ES_FAILED;
00231 if ((status & MPS_REMOVED) != 0)
00232 goto rerun;
00233 if (((status & MPS_ASSIGNED) != 0) && y.assigned())
00234 return ES_SUBSUMED(this,sizeof(*this));
00235 return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
00236 }
00237
00238 template <class View>
00239 Support::Symbol
00240 NaryMax<View>::ati(void) {
00241 return Reflection::mangle<View>("Gecode::Int::Arithmetic::NaryMax");
00242 }
00243
00244 template <class View>
00245 Reflection::ActorSpec
00246 NaryMax<View>::spec(const Space* home, Reflection::VarMap& m) const {
00247 return NaryOnePropagator<View,PC_INT_BND>::spec(home, m, ati());
00248 }
00249
00250 }}}
00251
00252
00253