edge-finding.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
00041
00042
00043
00044 #include <algorithm>
00045
00046 namespace Gecode { namespace Int { namespace Cumulative {
00047
00049 template<class TaskView, bool inc>
00050 class StoCap {
00051 public:
00053 bool operator ()(const TaskView& t1, const TaskView& t2) const {
00054 return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
00055 }
00056 };
00057
00059 class PrecOrder {
00060 public:
00061 int* prec;
00063 PrecOrder(int* prec0) : prec(prec0) {}
00065 bool operator ()(int i, int j) const {
00066 return prec[i] > prec[j];
00067 }
00068 };
00069
00070 template<class TaskView>
00071 forceinline ExecStatus
00072 edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
00073 sort<TaskView,STO_LCT,false>(t);
00074
00075 Region r(home);
00076
00078
00079
00080 int* prec = r.alloc<int>(t.size());
00081 for (int i=t.size(); i--; )
00082 prec[i] = t[i].ect();
00083
00084 OmegaLambdaTree<TaskView> ol(r,c,t);
00085
00086 for (int j=0; j<t.size(); j++) {
00087 while (!ol.lempty() &&
00088 (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
00089 int i = ol.responsible();
00090 prec[i] = std::max(prec[i], t[j].lct());
00091 ol.lremove(i);
00092 }
00093 ol.shift(j);
00094 }
00095
00097
00098
00099
00100
00101
00102
00103 int* cap = r.alloc<int>(t.size());
00104 for (int i=t.size(); i--;)
00105 cap[i] = i;
00106 SortMap<TaskView,StoCap,true> o(t);
00107 Support::quicksort(cap, t.size(), o);
00108
00109 int* capacities = r.alloc<int>(t.size());
00110 int* capInv = r.alloc<int>(t.size());
00111 for (int i=t.size(); i--;) {
00112 capacities[cap[i]] = t[i].c();
00113 capInv[cap[i]] = i;
00114 }
00115
00116 int n_c = 0;
00117 for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
00118 if (capacities[i] != cur_c)
00119 capacities[n_c++] = cur_c = capacities[i];
00120 cap[capInv[i]] = n_c-1;
00121 }
00122 r.free<int>(capInv, t.size());
00123
00124
00125
00126 int* update = r.alloc<int>(t.size()*n_c);
00127 for (int i=t.size()*n_c; i--;)
00128 update[i] = -Limits::infinity;
00129
00130 ExtOmegaTree<TaskView> eo(r,c,ol);
00131 for (int i=0; i<n_c; i++) {
00132 eo.init(capacities[i]);
00133 int u = -Limits::infinity;
00134 for (int j=t.size(); j--;) {
00135 long long int lctj =
00136 static_cast<long long int>(c-capacities[i])*t[j].lct();
00137 long long int eml = plus(eo.env(j), -lctj);
00138 long long int diff_l;
00139 if (eml == -Limits::llinfinity)
00140 diff_l = -Limits::llinfinity;
00141 else
00142 diff_l = ceil_div_xx(eml,
00143 static_cast<long long int>(capacities[i]));
00144 int diff = (diff_l <= -Limits::infinity) ?
00145 -Limits::infinity : static_cast<int>(diff_l);
00146 u = std::max(u,diff);
00147 update[i*t.size()+j] = u;
00148 }
00149 }
00150
00151
00152
00153
00154 int* precMap = r.alloc<int>(t.size());
00155 for (int i=t.size(); i--;)
00156 precMap[i] = i;
00157 PrecOrder po(prec);
00158 Support::quicksort(precMap, t.size(), po);
00159
00160 int curJ = 0;
00161 for (int i=0; i<t.size(); i++) {
00162
00163 while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
00164 curJ++;
00165 if (curJ >= t.size())
00166 break;
00167
00168 int locJ = curJ;
00169 do {
00170 if (t[locJ].lct() != t[precMap[i]].lct()) {
00171 GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
00172 break;
00173 }
00174 } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
00175 }
00176
00177 return ES_OK;
00178 }
00179
00180 template<class Task>
00181 ExecStatus
00182 edgefinding(Space& home, int c, TaskArray<Task>& t) {
00183 TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
00184 GECODE_ES_CHECK(edgefinding(home,c,f));
00185 TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
00186 GECODE_ES_CHECK(edgefinding(home,c,b));
00187 return ES_OK;
00188 }
00189
00190 }}}
00191
00192