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