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