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 #include <algorithm>
00041 #include <cmath>
00042
00043 namespace Gecode { namespace Int { namespace Cumulative {
00044
00045
00046
00047
00048
00049 forceinline void
00050 OmegaNode::init(const OmegaNode&, const OmegaNode&) {
00051 e = 0; env = -Limits::llinfinity;
00052 }
00053
00054 forceinline void
00055 OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
00056 e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
00057 }
00058
00059 template<class TaskView>
00060 OmegaTree<TaskView>::OmegaTree(Region& r, int c0,
00061 const TaskViewArray<TaskView>& t)
00062 : TaskTree<TaskView,OmegaNode>(r,t), c(c0) {
00063 for (int i=tasks.size(); i--; ) {
00064 leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
00065 }
00066 init();
00067 }
00068
00069 template<class TaskView>
00070 forceinline void
00071 OmegaTree<TaskView>::insert(int i) {
00072 leaf(i).e = tasks[i].e();
00073 leaf(i).env =
00074 static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
00075 update(i);
00076 }
00077
00078 template<class TaskView>
00079 forceinline void
00080 OmegaTree<TaskView>::remove(int i) {
00081 leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
00082 update(i);
00083 }
00084
00085 template<class TaskView>
00086 forceinline long long int
00087 OmegaTree<TaskView>::env(void) const {
00088 return root().env;
00089 }
00090
00091
00092
00093
00094
00095 forceinline void
00096 ExtOmegaNode::init(const ExtOmegaNode& l, const ExtOmegaNode& r) {
00097 OmegaNode::init(l,r);
00098 cenv = -Limits::llinfinity;
00099 }
00100
00101 forceinline void
00102 ExtOmegaNode::update(const ExtOmegaNode& l, const ExtOmegaNode& r) {
00103 OmegaNode::update(l,r);
00104 cenv = std::max(plus(l.cenv,r.e), r.cenv);
00105 }
00106
00107 template<class TaskView> void
00108 ExtOmegaTree<TaskView>::init(int ci0) {
00109 ci = ci0;
00110 for (int i=tasks.size(); i--; ) {
00111 leaf(i).e = 0;
00112 leaf(i).env = leaf(i).cenv = -Limits::llinfinity;
00113 }
00114 init();
00115 }
00116
00117 template<class TaskView> template<class Node>
00118 ExtOmegaTree<TaskView>::ExtOmegaTree(Region& r, int c0,
00119 const TaskTree<TaskView,Node>& t)
00120 : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
00121
00122 template<class TaskView>
00123 forceinline long long int
00124 ExtOmegaTree<TaskView>::env(int i) {
00125
00126 leaf(i).e = tasks[i].e();
00127 leaf(i).env =
00128 static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
00129 leaf(i).cenv =
00130 static_cast<long long int>(c-ci)*tasks[i].est()+tasks[i].e();
00131 TaskTree<TaskView,ExtOmegaNode>::update(i);
00132
00133
00134 int met = 0;
00135 {
00136 long long int e = 0;
00137 while (!n_leaf(met)) {
00138 if (plus(node[n_right(met)].cenv,e) >
00139 static_cast<long long int>(c-ci) * tasks[i].lct()) {
00140 met = n_right(met);
00141 } else {
00142 e += node[n_right(met)].e; met = n_left(met);
00143 }
00144 }
00145 }
00146
00147
00148
00149
00150
00151
00152
00153
00154 long long int a_e = node[met].e;
00155 long long int a_env = node[met].env;
00156 long long int b_e = 0;
00157
00158 while (!n_root(met)) {
00159 if (left(met)) {
00160 b_e += node[n_right(n_parent(met))].e;
00161 } else {
00162 a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e));
00163 a_e += node[n_left(n_parent(met))].e;
00164 }
00165 met = n_parent(met);
00166 }
00167
00168 return plus(a_env,b_e);
00169 }
00170
00171
00172
00173
00174
00175
00176
00177 forceinline void
00178 OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00179 OmegaNode::init(l,r);
00180 le = 0; lenv = -Limits::llinfinity;
00181 resLe = undef; resLenv = undef;
00182 }
00183
00184 forceinline void
00185 OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00186 OmegaNode::update(l,r);
00187 if (l.le + r.e > l.e + r.le) {
00188 le = l.le + r.e;
00189 resLe = l.resLe;
00190 } else {
00191 le = l.e + r.le;
00192 resLe = r.resLe;
00193 }
00194 if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) {
00195 lenv = r.lenv; resLenv = r.resLenv;
00196 } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) {
00197 assert(plus(l.env,r.le) > r.lenv);
00198 lenv = plus(l.env,r.le); resLenv = r.resLe;
00199 } else {
00200 assert((plus(l.lenv,r.e) > r.lenv) &&
00201 (plus(l.lenv,r.e) > plus(l.env,r.le)));
00202 lenv = plus(l.lenv,r.e); resLenv = l.resLenv;
00203 }
00204 }
00205
00206
00207 template<class TaskView>
00208 OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r, int c0,
00209 const TaskViewArray<TaskView>& t)
00210 : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) {
00211
00212 for (int i=tasks.size(); i--; ) {
00213 leaf(i).e = tasks[i].e();
00214 leaf(i).le = 0;
00215 leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
00216 leaf(i).lenv = -Limits::llinfinity;
00217 leaf(i).resLe = OmegaLambdaNode::undef;
00218 leaf(i).resLenv = OmegaLambdaNode::undef;
00219 }
00220 update();
00221 }
00222
00223 template<class TaskView>
00224 forceinline void
00225 OmegaLambdaTree<TaskView>::shift(int i) {
00226
00227 assert(leaf(i).env > -Limits::llinfinity);
00228 leaf(i).le = leaf(i).e;
00229 leaf(i).e = 0;
00230 leaf(i).lenv = leaf(i).env;
00231 leaf(i).env = -Limits::llinfinity;
00232 leaf(i).resLe = i;
00233 leaf(i).resLenv = i;
00234 update(i);
00235 }
00236
00237 template<class TaskView>
00238 forceinline void
00239 OmegaLambdaTree<TaskView>::lremove(int i) {
00240
00241 assert(leaf(i).env == -Limits::llinfinity);
00242 assert(leaf(i).lenv > -Limits::llinfinity);
00243 leaf(i).le = 0;
00244 leaf(i).lenv = -Limits::llinfinity;
00245 leaf(i).resLe = OmegaLambdaNode::undef;
00246 leaf(i).resLenv = OmegaLambdaNode::undef;
00247 update(i);
00248 }
00249
00250 template<class TaskView>
00251 forceinline bool
00252 OmegaLambdaTree<TaskView>::lempty(void) const {
00253 return root().resLenv < 0;
00254 }
00255
00256 template<class TaskView>
00257 forceinline int
00258 OmegaLambdaTree<TaskView>::responsible(void) const {
00259 return root().resLenv;
00260 }
00261
00262 template<class TaskView>
00263 forceinline long long int
00264 OmegaLambdaTree<TaskView>::env(void) const {
00265 return root().env;
00266 }
00267
00268 template<class TaskView>
00269 forceinline long long int
00270 OmegaLambdaTree<TaskView>::lenv(void) const {
00271 return root().lenv;
00272 }
00273
00274 }}}
00275
00276