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 #include <algorithm>
00039
00040 namespace Gecode { namespace Scheduling { namespace Unary {
00041
00042
00043
00044
00045
00046 forceinline void
00047 OmegaNode::init(const OmegaNode&, const OmegaNode&) {
00048 p = 0; ect = -Int::Limits::infinity;
00049 }
00050
00051 forceinline void
00052 OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
00053 p = l.p + r.p;
00054 ect = std::max(plus(l.ect,r.p), r.ect);
00055 }
00056
00057 template<class TaskView>
00058 OmegaTree<TaskView>::OmegaTree(Region& r, const TaskViewArray<TaskView>& t)
00059 : TaskTree<TaskView,OmegaNode>(r,t) {
00060 for (int i=tasks.size(); i--; ) {
00061 leaf(i).p = 0; leaf(i).ect = -Int::Limits::infinity;
00062 }
00063 init();
00064 }
00065
00066 template<class TaskView>
00067 forceinline void
00068 OmegaTree<TaskView>::insert(int i) {
00069 leaf(i).p = tasks[i].p(); leaf(i).ect = tasks[i].ect();
00070 update(i);
00071 }
00072
00073 template<class TaskView>
00074 forceinline void
00075 OmegaTree<TaskView>::remove(int i) {
00076 leaf(i).p = 0; leaf(i).ect = -Int::Limits::infinity;
00077 update(i);
00078 }
00079
00080 template<class TaskView>
00081 forceinline int
00082 OmegaTree<TaskView>::ect(void) const {
00083 return root().ect;
00084 }
00085
00086 template<class TaskView>
00087 forceinline int
00088 OmegaTree<TaskView>::ect(int i) const {
00089
00090 OmegaTree<TaskView>& o = const_cast<OmegaTree<TaskView>&>(*this);
00091 if (o.leaf(i).ect != -Int::Limits::infinity) {
00092 o.remove(i);
00093 int ect = o.root().ect;
00094 o.insert(i);
00095 return ect;
00096 } else {
00097 return root().ect;
00098 }
00099 }
00100
00101
00102
00103
00104
00105
00106
00107 forceinline void
00108 OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00109 OmegaNode::init(l,r);
00110 lp = p; lect = ect; res = undef;
00111 }
00112
00113 forceinline void
00114 OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00115 OmegaNode::update(l,r);
00116 lp = std::max(l.lp + r.p, l.p + r.lp);
00117 if ((r.lect >= plus(l.ect,r.lp)) && (r.lect >= plus(l.lect,r.p))) {
00118 lect = r.lect; res = r.res;
00119 } else if (plus(l.ect,r.lp) >= plus(l.lect,r.p)) {
00120 assert(plus(l.ect,r.lp) > r.lect);
00121 lect = plus(l.ect,r.lp); res = r.res;
00122 } else {
00123 assert((plus(l.lect,r.p) > r.lect) &&
00124 (plus(l.lect,r.p) > plus(l.ect,r.lp)));
00125 lect = plus(l.lect,r.p); res = l.res;
00126 }
00127 }
00128
00129
00130 template<class TaskView>
00131 OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r,
00132 const TaskViewArray<TaskView>& t,
00133 bool inc)
00134 : TaskTree<TaskView,OmegaLambdaNode>(r,t) {
00135 if (inc) {
00136
00137 for (int i=tasks.size(); i--; ) {
00138 leaf(i).p = leaf(i).lp = tasks[i].p();
00139 leaf(i).ect = leaf(i).lect = tasks[i].ect();
00140 leaf(i).res = OmegaLambdaNode::undef;
00141 }
00142 } else {
00143
00144 for (int i=tasks.size(); i--; ) {
00145 leaf(i).p = leaf(i).lp = 0;
00146 leaf(i).ect = leaf(i).lect = -Int::Limits::infinity;
00147 leaf(i).res = OmegaLambdaNode::undef;
00148 }
00149 }
00150 init();
00151 }
00152
00153 template<class TaskView>
00154 forceinline void
00155 OmegaLambdaTree<TaskView>::shift(int i) {
00156
00157 assert(leaf(i).ect > -Int::Limits::infinity);
00158 leaf(i).p = 0;
00159 leaf(i).ect = -Int::Limits::infinity;
00160 leaf(i).res = i;
00161 update(i);
00162 }
00163
00164 template<class TaskView>
00165 forceinline void
00166 OmegaLambdaTree<TaskView>::oinsert(int i) {
00167 leaf(i).p = tasks[i].p();
00168 leaf(i).ect = tasks[i].ect();
00169 update(i);
00170 }
00171
00172 template<class TaskView>
00173 forceinline void
00174 OmegaLambdaTree<TaskView>::linsert(int i) {
00175 leaf(i).lp = tasks[i].p();
00176 leaf(i).lect = tasks[i].ect();
00177 leaf(i).res = i;
00178 update(i);
00179 }
00180
00181 template<class TaskView>
00182 forceinline void
00183 OmegaLambdaTree<TaskView>::lremove(int i) {
00184 leaf(i).lp = 0;
00185 leaf(i).lect = -Int::Limits::infinity;
00186 leaf(i).res = OmegaLambdaNode::undef;
00187 update(i);
00188 }
00189
00190 template<class TaskView>
00191 forceinline bool
00192 OmegaLambdaTree<TaskView>::lempty(void) const {
00193 return root().res < 0;
00194 }
00195
00196 template<class TaskView>
00197 forceinline int
00198 OmegaLambdaTree<TaskView>::responsible(void) const {
00199 return root().res;
00200 }
00201
00202 template<class TaskView>
00203 forceinline int
00204 OmegaLambdaTree<TaskView>::ect(void) const {
00205 return root().ect;
00206 }
00207
00208 template<class TaskView>
00209 forceinline int
00210 OmegaLambdaTree<TaskView>::lect(void) const {
00211 return root().lect;
00212 }
00213
00214 }}}
00215
00216