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 #include <algorithm>
00035
00036
00037
00038
00039
00040
00041
00042
00043 namespace Gecode { namespace Int { namespace Cumulatives {
00044
00045 template<class ViewM, class ViewP, class ViewU, class View>
00046 forceinline
00047 Val<ViewM,ViewP,ViewU,View>::Val(Home home,
00048 const ViewArray<ViewM>& _m,
00049 const ViewArray<View>& _s,
00050 const ViewArray<ViewP>& _p,
00051 const ViewArray<View>& _e,
00052 const ViewArray<ViewU>& _u,
00053 const SharedArray<int>& _c,
00054 bool _at_most) :
00055 Propagator(home),
00056 m(_m), s(_s), p(_p), e(_e), u(_u), c(_c), at_most(_at_most) {
00057 home.notice(*this,AP_DISPOSE);
00058
00059 m.subscribe(home,*this,Int::PC_INT_DOM);
00060 s.subscribe(home,*this,Int::PC_INT_BND);
00061 p.subscribe(home,*this,Int::PC_INT_BND);
00062 e.subscribe(home,*this,Int::PC_INT_BND);
00063 u.subscribe(home,*this,Int::PC_INT_BND);
00064 }
00065
00066 template<class ViewM, class ViewP, class ViewU, class View>
00067 ExecStatus
00068 Val<ViewM,ViewP,ViewU,View>
00069 ::post(Home home, const ViewArray<ViewM>& m,
00070 const ViewArray<View>& s, const ViewArray<ViewP>& p,
00071 const ViewArray<View>& e, const ViewArray<ViewU>& u,
00072 const SharedArray<int>& c, bool at_most) {
00073 (void) new (home) Val(home, m,s,p,e,u,c,at_most);
00074 return ES_OK;
00075 }
00076
00077 template<class ViewM, class ViewP, class ViewU, class View>
00078 forceinline
00079 Val<ViewM,ViewP,ViewU,View>::Val(Space& home,
00080 Val<ViewM,ViewP,ViewU,View>& vp)
00081 : Propagator(home,vp), c(vp.c), at_most(vp.at_most) {
00082 m.update(home,vp.m);
00083 s.update(home, vp.s);
00084 p.update(home, vp.p);
00085 e.update(home, vp.e);
00086 u.update(home, vp.u);
00087 }
00088
00089 template<class ViewM, class ViewP, class ViewU, class View>
00090 size_t
00091 Val<ViewM,ViewP,ViewU,View>::dispose(Space& home) {
00092 home.ignore(*this,AP_DISPOSE);
00093 if (!home.failed()) {
00094 m.cancel(home,*this,Int::PC_INT_DOM);
00095 s.cancel(home,*this,Int::PC_INT_BND);
00096 p.cancel(home,*this,Int::PC_INT_BND);
00097 e.cancel(home,*this,Int::PC_INT_BND);
00098 u.cancel(home,*this,Int::PC_INT_BND);
00099 }
00100 c.~SharedArray();
00101 (void) Propagator::dispose(home);
00102 return sizeof(*this);
00103 }
00104
00105 template<class ViewM, class ViewP, class ViewU, class View>
00106 PropCost
00107 Val<ViewM,ViewP,ViewU,View>::cost(const Space&, const ModEventDelta&) const {
00108 return PropCost::quadratic(PropCost::LO, s.size());
00109 }
00110
00111 template<class ViewM, class ViewP, class ViewU, class View>
00112 void
00113 Val<ViewM,ViewP,ViewU,View>::reschedule(Space& home) {
00114 m.reschedule(home,*this,Int::PC_INT_DOM);
00115 s.reschedule(home,*this,Int::PC_INT_BND);
00116 p.reschedule(home,*this,Int::PC_INT_BND);
00117 e.reschedule(home,*this,Int::PC_INT_BND);
00118 u.reschedule(home,*this,Int::PC_INT_BND);
00119 }
00120
00121 template<class ViewM, class ViewP, class ViewU, class View>
00122 Actor*
00123 Val<ViewM,ViewP,ViewU,View>::copy(Space& home) {
00124 return new (home) Val<ViewM,ViewP,ViewU,View>(home,*this);
00125 }
00126
00128 typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
00130 class Event
00131 {
00132 public:
00134 ev_t e;
00136 int task;
00138 int date;
00140 int inc;
00145 bool first_prof;
00146
00148 Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
00149 : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
00150 {}
00151
00152
00153 Event(void) {}
00154
00156 bool operator <(const Event& ev) const {
00157 if (date == ev.date) {
00158 if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
00159 if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
00160 return false;
00161 }
00162 return date < ev.date;
00163 }
00164 };
00165
00166 template<class ViewM, class ViewP, class ViewU, class View>
00167 ExecStatus
00168 Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
00169 int ntask, int su,
00170 int* contribution,
00171 int* prune_tasks, int& prune_tasks_size) {
00172
00173 if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
00174 return ES_FAILED;
00175 }
00176
00177 int pti = 0;
00178 while (pti != prune_tasks_size) {
00179 int t = prune_tasks[pti];
00180
00181
00182
00183
00184 if (ntask != 0 &&
00185 (at_most ? u[t].min() < 0
00186 : u[t].max() > 0) &&
00187 (at_most ? su-contribution[t] > c[r]
00188 : su-contribution[t] < c[r])) {
00189 if (me_failed(m[t].eq(home, r))||
00190 me_failed(s[t].gq(home, up-p[t].max()+1))||
00191 me_failed(s[t].lq(home, low))||
00192 me_failed(e[t].lq(home,low+p[t].max()))||
00193 me_failed(e[t].gq(home, up+1))||
00194 me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
00195 ) {
00196 return ES_FAILED;
00197 }
00198 }
00199
00200
00201
00202 if (at_most ? u[t].min() > std::min(0, c[r])
00203 : u[t].max() < std::max(0, c[r])) {
00204 if (at_most ? su-contribution[t]+u[t].min() > c[r]
00205 : su-contribution[t]+u[t].max() < c[r]) {
00206 if (e[t].min() > low &&
00207 s[t].max() <= up &&
00208 p[t].min() > 0) {
00209 if (me_failed(m[t].nq(home, r))) {
00210 return ES_FAILED;
00211 }
00212 } else if (m[t].assigned()) {
00213 int ptmin = p[t].min();
00214 if (ptmin > 0) {
00215 Iter::Ranges::Singleton
00216 a(low-ptmin+1, up), b(low+1, up+ptmin);
00217 if (me_failed(s[t].minus_r(home,a,false)) ||
00218 me_failed(e[t].minus_r(home, b,false)))
00219 return ES_FAILED;
00220 }
00221 if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
00222 e[t].max()-up-1),
00223 0)))) {
00224 return ES_FAILED;
00225 }
00226 }
00227 }
00228 }
00229
00230
00231
00232
00233
00234
00235
00236 if (m[t].assigned() &&
00237 m[t].val() == r &&
00238 e[t].min() > low &&
00239 s[t].max() <= up &&
00240 p[t].min() > 0 ) {
00241 if (me_failed(at_most
00242 ? u[t].lq(home, c[r]-su+contribution[t])
00243 : u[t].gq(home, c[r]-su+contribution[t]))) {
00244 return ES_FAILED;
00245 }
00246 }
00247
00248
00249 if (!m[t].in(r) || (e[t].max() <= up+1)) {
00250 prune_tasks[pti] = prune_tasks[--prune_tasks_size];
00251 } else {
00252 ++pti;
00253 }
00254 }
00255
00256 return ES_OK;
00257 }
00258
00259 namespace {
00260 template<class C>
00261 class Less {
00262 public:
00263 bool operator ()(const C& lhs, const C& rhs) {
00264 return lhs < rhs;
00265 }
00266 };
00267 }
00268
00269 template<class ViewM, class ViewP, class ViewU, class View>
00270 ExecStatus
00271 Val<ViewM,ViewP,ViewU,View>::propagate(Space& home, const ModEventDelta&) {
00272
00273 bool subsumed = true;
00274 for (int t = s.size(); t--; )
00275 if (!(p[t].assigned() && e[t].assigned() &&
00276 m[t].assigned() && s[t].assigned() &&
00277 u[t].assigned())) {
00278 subsumed = false;
00279 break;
00280 }
00281
00282 Region region;
00283 Event *events = region.alloc<Event>(s.size()*8);
00284 int events_size;
00285 int *prune_tasks = region.alloc<int>(s.size());
00286 int prune_tasks_size;
00287 int *contribution = region.alloc<int>(s.size());
00288 for (int r = c.size(); r--; ) {
00289 events_size = 0;
00290 #define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
00291 events[events_size++] = E
00292
00293
00294 for (int t = s.size(); t--; ) {
00295 if (m[t].assigned() &&
00296 m[t].val() == r &&
00297 s[t].max() < e[t].min()) {
00298 if (at_most
00299 ? u[t].min() > std::min(0, c[r])
00300 : u[t].max() < std::max(0, c[r])) {
00301 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, s[t].max(), 1));
00302 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, e[t].min(), -1));
00303 }
00304 if (at_most
00305 ? u[t].min() > 0
00306 : u[t].max() < 0) {
00307 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].max(),
00308 at_most ? u[t].min() : u[t].max(), true));
00309 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].min(),
00310 at_most ? -u[t].min() : -u[t].max()));
00311 }
00312 }
00313
00314 if (m[t].in(r)) {
00315 if (at_most
00316 ? u[t].min() < 0
00317 : u[t].max() > 0) {
00318 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].min(),
00319 at_most ? u[t].min() : u[t].max(), true));
00320 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].max(),
00321 at_most ? -u[t].min() : -u[t].max()));
00322 }
00323 if (!(m[t].assigned() &&
00324 u[t].assigned() &&
00325 s[t].assigned() &&
00326 e[t].assigned())) {
00327 GECODE_PUSH_EVENTS(Event(EVENT_PRUN, t, s[t].min()));
00328 }
00329 }
00330 }
00331 #undef GECODE_PUSH_EVENTS
00332
00333
00334 if (events_size == 0) {
00335 continue;
00336 }
00337
00338
00339 Less<Event> less;
00340 Support::insertion(&events[0], events_size, less);
00341
00342
00343 int d = 0;
00344 int ntask = 0;
00345 int su = 0;
00346 int ei = 0;
00347
00348 prune_tasks_size = 0;
00349 for (int i = s.size(); i--; ) contribution[i] = 0;
00350
00351 d = events[ei].date;
00352 while (ei < events_size) {
00353 if (events[ei].e != EVENT_PRUN) {
00354 if (d != events[ei].date) {
00355 GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
00356 ntask, su,
00357 contribution, prune_tasks, prune_tasks_size));
00358 d = events[ei].date;
00359 }
00360 if (events[ei].e == EVENT_CHCK) {
00361 ntask += events[ei].inc;
00362 } else {
00363 su += events[ei].inc;
00364 if(events[ei].first_prof)
00365 contribution[events[ei].task] = at_most
00366 ? std::max(contribution[events[ei].task], events[ei].inc)
00367 : std::min(contribution[events[ei].task], events[ei].inc);
00368 }
00369 } else {
00370 assert(prune_tasks_size<s.size());
00371 prune_tasks[prune_tasks_size++] = events[ei].task;
00372 }
00373 ei++;
00374 }
00375
00376 GECODE_ES_CHECK(prune(home, d, d, r,
00377 ntask, su,
00378 contribution, prune_tasks, prune_tasks_size));
00379 }
00380 return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
00381 }
00382
00383 }}}
00384
00385