basic.hpp
Go to the documentation of this file.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 namespace Gecode { namespace Int { namespace Cumulative {
00041
00043 class Event {
00044 public:
00046 enum Type {
00047 LRT = 0,
00048 LCT = 1,
00049 EST = 2,
00050 ZRO = 3,
00051 ERT = 4,
00052 END = 5
00053 };
00054 Type e;
00055 int t;
00056 int i;
00057
00058 void init(Type e, int t, int i);
00060 bool operator <(const Event& e) const;
00061 };
00062
00064 template<class Task>
00065 class TaskByDecCap {
00066 public:
00068 bool operator ()(const Task& t1, const Task& t2) const;
00069 };
00070
00071 forceinline void
00072 Event::init(Event::Type e0, int t0, int i0) {
00073 e=e0; t=t0; i=i0;
00074 }
00075
00076 forceinline bool
00077 Event::operator <(const Event& e) const {
00078 if (this->t == e.t)
00079 return this->e < e.e;
00080 return this->t < e.t;
00081 }
00082
00083 template<class Task>
00084 forceinline bool
00085 TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
00086 return t1.c() > t2.c();
00087 }
00088
00089
00090
00091 template<class Task, class Cap>
00092 ExecStatus
00093 basic(Space& home, bool& subsumed, Cap c, TaskArray<Task>& t) {
00094 subsumed = false;
00095 int ccur = c.max();
00096 int cmax = ccur;
00097 int cmin = ccur;
00098
00099 TaskByDecCap<Task> tbdc;
00100 Support::quicksort(&t[0], t.size(), tbdc);
00101
00102 Region r(home);
00103
00104 Event* e = r.alloc<Event>(4*t.size()+1);
00105
00106
00107 bool assigned=true;
00108 {
00109 bool required=false;
00110 int n=0;
00111 for (int i=t.size(); i--; )
00112 if (t[i].assigned()) {
00113
00114 if (t[i].pmin() > 0) {
00115 required = true;
00116 e[n++].init(Event::ERT,t[i].lst(),i);
00117 e[n++].init(Event::LRT,t[i].ect(),i);
00118 } else if (t[i].pmax() == 0) {
00119 required = true;
00120 e[n++].init(Event::ZRO,t[i].lst(),i);
00121 }
00122 } else {
00123 assigned = false;
00124 e[n++].init(Event::EST,t[i].est(),i);
00125 e[n++].init(Event::LCT,t[i].lct(),i);
00126
00127 if (t[i].lst() < t[i].ect()) {
00128 required = true;
00129 e[n++].init(Event::ERT,t[i].lst(),i);
00130 e[n++].init(Event::LRT,t[i].ect(),i);
00131 }
00132 }
00133
00134
00135 if (!required) {
00136 subsumed = assigned;
00137 return ES_FIX;
00138 }
00139
00140
00141 e[n++].init(Event::END,Int::Limits::infinity,-1);
00142
00143
00144 Support::quicksort(e, n);
00145 }
00146
00147
00148 Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
00149
00150
00151 while (e->e != Event::END) {
00152
00153 int time = e->t;
00154
00155
00156 for ( ; (e->t == time) && (e->e == Event::LRT); e++)
00157 if (t[e->i].mandatory()) {
00158 tasks.set(static_cast<unsigned int>(e->i)); ccur += t[e->i].c();
00159 }
00160
00161 for ( ; (e->t == time) && (e->e == Event::LCT); e++)
00162 tasks.clear(static_cast<unsigned int>(e->i));
00163
00164 for ( ; (e->t == time) && (e->e == Event::EST); e++)
00165 tasks.set(static_cast<unsigned int>(e->i));
00166
00167 for ( ; (e->t == time) && (e->e == Event::ZRO); e++) {
00168 ccur -= t[e->i].c();
00169 if (ccur < cmin) cmin=ccur;
00170 if (ccur < 0)
00171 return ES_FAILED;
00172 ccur += t[e->i].c();
00173 }
00174
00175
00176 int zltime = time;
00177
00178 for ( ; (e->t == time) && (e->e == Event::ERT); e++)
00179 if (t[e->i].mandatory()) {
00180 tasks.clear(static_cast<unsigned int>(e->i));
00181 ccur -= t[e->i].c();
00182 if (ccur < cmin) cmin=ccur;
00183 zltime = time+1;
00184 if (ccur < 0)
00185 return ES_FAILED;
00186 } else if (t[e->i].optional() && (t[e->i].c() > ccur)) {
00187 GECODE_ME_CHECK(t[e->i].excluded(home));
00188 }
00189
00190
00191 for (Iter::Values::BitSet<Support::BitSet<Region> > j(tasks);
00192 j() && (t[j.val()].c() > ccur); ++j)
00193
00194 if (t[j.val()].mandatory()) {
00195 if (t[j.val()].pmin() > 0) {
00196 GECODE_ME_CHECK(t[j.val()].norun(home, time, e->t - 1));
00197 } else {
00198 GECODE_ME_CHECK(t[j.val()].norun(home, zltime, e->t - 1));
00199 }
00200 }
00201 }
00202
00203 GECODE_ME_CHECK(c.gq(home,cmax-cmin));
00204
00205 subsumed = assigned;
00206 return ES_NOFIX;
00207 }
00208
00209 }}}
00210
00211