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 template<class VA, class VB, bool tiebreak>
00043 forceinline
00044 ArgMax<VA,VB,tiebreak>::ArgMax(Home home, IdxViewArray<VA>& x0, VB y0)
00045 : Propagator(home), x(x0), y(y0) {
00046 x.subscribe(home,*this,PC_INT_BND);
00047 y.subscribe(home,*this,PC_INT_DOM);
00048 }
00049
00050 template<class VA, class VB, bool tiebreak>
00051 ExecStatus
00052 ArgMax<VA,VB,tiebreak>::post(Home home, IdxViewArray<VA>& x, VB y) {
00053 assert(x.size() > 0);
00054 if (x.size() == 1) {
00055 GECODE_ME_CHECK(y.eq(home,x[0].idx));
00056 } else if (y.assigned()) {
00057 int max=0;
00058 while (x[max].idx < y.val())
00059 max++;
00060 assert(x[max].idx == y.val());
00061 if (tiebreak)
00062 for (int i=0; i<max; i++)
00063 GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home,
00064 x[i].view,x[max].view)));
00065 else
00066 for (int i=0; i<max; i++)
00067 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
00068 x[i].view,x[max].view)));
00069 for (int i=max+1; i<x.size(); i++)
00070 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
00071 x[i].view,x[max].view)));
00072 } else {
00073 (void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
00074 }
00075 return ES_OK;
00076 }
00077
00078 template<class VA, class VB, bool tiebreak>
00079 forceinline
00080 ArgMax<VA,VB,tiebreak>::ArgMax(Space& home, bool share,
00081 ArgMax<VA,VB,tiebreak>& p)
00082 : Propagator(home,share,p) {
00083 x.update(home,share,p.x);
00084 y.update(home,share,p.y);
00085 }
00086
00087 template<class VA, class VB, bool tiebreak>
00088 Actor*
00089 ArgMax<VA,VB,tiebreak>::copy(Space& home, bool share) {
00090 return new (home) ArgMax<VA,VB,tiebreak>(home,share,*this);
00091 }
00092
00093 template<class VA, class VB, bool tiebreak>
00094 PropCost
00095 ArgMax<VA,VB,tiebreak>::cost(const Space&,
00096 const ModEventDelta&) const {
00097 return PropCost::linear(PropCost::LO,x.size()+1);
00098 }
00099
00100 template<class VA, class VB, bool tiebreak>
00101 void
00102 ArgMax<VA,VB,tiebreak>::reschedule(Space& home) {
00103 x.reschedule(home,*this,PC_INT_BND);
00104 y.reschedule(home,*this,PC_INT_DOM);
00105 }
00106
00107 template<class VA, class VB, bool tiebreak>
00108 ExecStatus
00109 ArgMax<VA,VB,tiebreak>::propagate(Space& home, const ModEventDelta&) {
00110
00111
00112
00113
00114
00115
00116 int p = x[0].idx;
00117 int l = x[0].view.min();
00118 int u = x[0].view.max();
00119 for (int i=1; i<x.size(); i++) {
00120 if (l < x[i].view.min()) {
00121 p = x[i].idx; l = x[i].view.min();
00122 }
00123 if (u < x[i].view.max())
00124 u = x[i].view.max();
00125 }
00126
00127
00128 {
00129 Region r(home);
00130
00131
00132 int* d=r.alloc<int>(y.size());
00133
00134 int n = 0;
00135
00136 int i=0, j=0;
00137 ViewValues<VB> iy(y);
00138
00139 while ((i < x.size()) && iy()) {
00140 if (x[i].idx == iy.val()) {
00141 if (x[i].view.max() < l) {
00142 x[i].view.cancel(home,*this,PC_INT_BND);
00143 d[n++]=x[i].idx;
00144 } else {
00145 x[j++]=x[i];
00146 }
00147 ++iy;
00148 } else {
00149 assert(x[i].idx < iy.val());
00150 if (x[i].view.max() < l) {
00151 x[i].view.cancel(home,*this,PC_INT_BND);
00152 } else {
00153 x[j++]=x[i];
00154 }
00155 }
00156 i++;
00157 }
00158 while (i < x.size())
00159 if (x[i].view.max() < l) {
00160 x[i].view.cancel(home,*this,PC_INT_BND); i++;
00161 } else {
00162 x[j++]=x[i++];
00163 }
00164 x.size(j);
00165
00166 if (static_cast<unsigned int>(n) == y.size())
00167 return ES_FAILED;
00168 Iter::Values::Array id(d,n);
00169 GECODE_ME_CHECK(y.minus_v(home,id,false));
00170 }
00171
00172
00173
00174
00175
00176
00177
00178 if (tiebreak && (l == u))
00179 GECODE_ME_CHECK(y.lq(home,p));
00180
00181 if (y.assigned()) {
00182 int max=0;
00183 while (x[max].idx < y.val())
00184 max++;
00185 assert(x[max].idx == y.val());
00186 if (tiebreak)
00187 for (int i=0; i<max; i++)
00188 GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home(*this),
00189 x[i].view,x[max].view)));
00190 else
00191 for (int i=0; i<max; i++)
00192 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
00193 x[i].view,x[max].view)));
00194 for (int i=max+1; i<x.size(); i++)
00195 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
00196 x[i].view,x[max].view)));
00197 return home.ES_SUBSUMED(*this);
00198 }
00199
00200
00201 {
00202 ViewValues<VB> iy(y);
00203 int i=0;
00204
00205 while (x[i].idx < y.min())
00206 i++;
00207 u=x[i].view.max();
00208
00209 i++; ++iy;
00210 while (iy()) {
00211 if (x[i].idx == iy.val()) {
00212 u = std::max(u,x[i].view.max());
00213 ++iy;
00214 } else {
00215 assert(x[i].idx < iy.val());
00216 }
00217 i++;
00218 }
00219 }
00220
00221
00222 {
00223 int i = 0;
00224
00225 if (tiebreak)
00226 while ((i < x.size()) && (x[i].idx < y.min())) {
00227 GECODE_ME_CHECK(x[i].view.le(home,u));
00228 i++;
00229 }
00230 else
00231 while ((i < x.size()) && (x[i].idx < y.min())) {
00232 GECODE_ME_CHECK(x[i].view.lq(home,u));
00233 i++;
00234 }
00235 assert(x[i].idx == y.min());
00236
00237
00238 ViewValues<VB> iy(y);
00239
00240 i++; ++iy;
00241 while ((i < x.size()) && iy()) {
00242 if (x[i].idx == iy.val()) {
00243 ++iy;
00244 } else {
00245 assert(x[i].idx < iy.val());
00246 GECODE_ME_CHECK(x[i].view.lq(home,u));
00247 }
00248 i++;
00249 }
00250 while (i < x.size()) {
00251 assert(x[i].idx > y.max());
00252 GECODE_ME_CHECK(x[i].view.lq(home,u));
00253 i++;
00254 }
00255 }
00256 return tiebreak ? ES_NOFIX : ES_FIX;
00257 }
00258
00259 template<class VA, class VB, bool tiebreak>
00260 forceinline size_t
00261 ArgMax<VA,VB,tiebreak>::dispose(Space& home) {
00262 x.cancel(home,*this,PC_INT_BND);
00263 y.cancel(home,*this,PC_INT_DOM);
00264 (void) Propagator::dispose(home);
00265 return sizeof(*this);
00266 }
00267
00268 }}}
00269
00270
00271