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