tree.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2009 00009 * Guido Tack, 2010 00010 * 00011 * Last modified: 00012 * $Date: 2011-01-18 23:37:08 +0100 (Tue, 18 Jan 2011) $ by $Author: tack $ 00013 * $Revision: 11551 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #include <algorithm> 00041 #include <cmath> 00042 00043 namespace Gecode { namespace Scheduling { namespace Cumulative { 00044 00045 /* 00046 * Omega tree 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 * Extended Omega tree 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 // Enter task i 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 // Perform computation of node for task with minest 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 * The following idea to compute the cut in one go is taken from: 00146 * Joseph Scott, Filtering Algorithms for Discrete Resources, 00147 * Master Thesis, Uppsala University, 2010 (in preparation). 00148 */ 00149 00150 // Now perform split from leaf met upwards 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 * Omega lambda tree 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 // Enter all tasks into tree (omega = all tasks, lambda = empty) 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 // i is in omega 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 // i not in omega but in lambda 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 // STATISTICS: scheduling-prop