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