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