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 * 00006 * Copyright: 00007 * Christian Schulte, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-04 09:40:05 +0200 (Fri, 04 Jun 2010) $ by $Author: tack $ 00011 * $Revision: 11024 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <algorithm> 00039 #include <cmath> 00040 00041 namespace Gecode { namespace Scheduling { namespace Cumulative { 00042 00043 /* 00044 * Omega tree 00045 */ 00046 00047 forceinline void 00048 OmegaNode::init(const OmegaNode&, const OmegaNode&) { 00049 e = 0.0; env = -Int::Limits::double_infinity; 00050 } 00051 00052 forceinline void 00053 OmegaNode::update(const OmegaNode& l, const OmegaNode& r) { 00054 e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env); 00055 } 00056 00057 template<class TaskView> 00058 OmegaTree<TaskView>::OmegaTree(Region& r, int c0, 00059 const TaskViewArray<TaskView>& t) 00060 : TaskTree<TaskView,OmegaNode>(r,t), c(c0) { 00061 for (int i=tasks.size(); i--; ) { 00062 leaf(i).e = 0.0; leaf(i).env = -Int::Limits::double_infinity; 00063 } 00064 init(); 00065 } 00066 00067 template<class TaskView> 00068 forceinline void 00069 OmegaTree<TaskView>::insert(int i) { 00070 leaf(i).e = tasks[i].e(); 00071 leaf(i).env = static_cast<double>(c)*tasks[i].est()+tasks[i].e(); 00072 update(i); 00073 } 00074 00075 template<class TaskView> 00076 forceinline void 00077 OmegaTree<TaskView>::remove(int i) { 00078 leaf(i).e = 0.0; leaf(i).env = -Int::Limits::double_infinity; 00079 update(i); 00080 } 00081 00082 template<class TaskView> 00083 forceinline double 00084 OmegaTree<TaskView>::env(void) const { 00085 return root().env; 00086 } 00087 00088 /* 00089 * Extended Omega tree 00090 */ 00091 00092 forceinline void 00093 ExtOmegaNode::init(const ExtOmegaNode& l, const ExtOmegaNode& r) { 00094 OmegaNode::init(l,r); 00095 cenv = -Int::Limits::double_infinity; 00096 } 00097 00098 forceinline void 00099 ExtOmegaNode::update(const ExtOmegaNode& l, const ExtOmegaNode& r) { 00100 OmegaNode::update(l,r); 00101 cenv = std::max(plus(l.cenv,r.e), r.cenv); 00102 } 00103 00104 template<class TaskView> void 00105 ExtOmegaTree<TaskView>::init(int ci0) { 00106 ci = ci0; 00107 for (int i=tasks.size(); i--; ) { 00108 leaf(i).e = 0.0; 00109 leaf(i).env = leaf(i).cenv = -Int::Limits::double_infinity; 00110 } 00111 init(); 00112 } 00113 00114 template<class TaskView> template<class Node> 00115 ExtOmegaTree<TaskView>::ExtOmegaTree(Region& r, int c0, 00116 const TaskTree<TaskView,Node>& t) 00117 : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {} 00118 00119 template<class TaskView> 00120 forceinline double 00121 ExtOmegaTree<TaskView>::env(int i) { 00122 // Enter task i 00123 leaf(i).e = tasks[i].e(); 00124 leaf(i).env = static_cast<double>(c)*tasks[i].est()+tasks[i].e(); 00125 leaf(i).cenv = static_cast<double>(c-ci)*tasks[i].est()+tasks[i].e(); 00126 TaskTree<TaskView,ExtOmegaNode>::update(i); 00127 00128 // Perform computation of node for task with minest 00129 int met = 0; 00130 { 00131 double e = 0.0; 00132 while (!n_leaf(met)) { 00133 if (plus(node[n_right(met)].cenv,e) > 00134 static_cast<double>(c-ci) * tasks[i].lct()) { 00135 met = n_right(met); 00136 } else { 00137 e += node[n_right(met)].e; met = n_left(met); 00138 } 00139 } 00140 } 00141 00142 /* 00143 * The following idea to compute the cut in one go is taken from: 00144 * Joseph Scott, Filtering Algorithms for Discrete Resources, 00145 * Master Thesis, Uppsala University, 2010 (in preparation). 00146 */ 00147 00148 // Now perform split from leaf met upwards 00149 double a_e = node[met].e; 00150 double a_env = node[met].env; 00151 double b_e = 0.0; 00152 00153 while (!n_root(met)) { 00154 if (left(met)) { 00155 b_e += node[n_right(n_parent(met))].e; 00156 } else { 00157 a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e)); 00158 a_e += node[n_left(n_parent(met))].e; 00159 } 00160 met = n_parent(met); 00161 } 00162 return b_e + a_env; 00163 } 00164 00165 00166 00167 /* 00168 * Omega lambda tree 00169 */ 00170 00171 forceinline void 00172 OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) { 00173 OmegaNode::init(l,r); 00174 le = 0.0; lenv = -Int::Limits::double_infinity; 00175 resLe = undef; resLenv = undef; 00176 } 00177 00178 forceinline void 00179 OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) { 00180 OmegaNode::update(l,r); 00181 if (l.le + r.e > l.e + r.le) { 00182 le = l.le + r.e; 00183 resLe = l.resLe; 00184 } else { 00185 le = l.e + r.le; 00186 resLe = r.resLe; 00187 } 00188 if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) { 00189 lenv = r.lenv; resLenv = r.resLenv; 00190 } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) { 00191 assert(plus(l.env,r.le) > r.lenv); 00192 lenv = plus(l.env,r.le); resLenv = r.resLe; 00193 } else { 00194 assert((plus(l.lenv,r.e) > r.lenv) && 00195 (plus(l.lenv,r.e) > plus(l.env,r.le))); 00196 lenv = plus(l.lenv,r.e); resLenv = l.resLenv; 00197 } 00198 } 00199 00200 00201 template<class TaskView> 00202 OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r, int c0, 00203 const TaskViewArray<TaskView>& t) 00204 : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) { 00205 // Enter all tasks into tree (omega = all tasks, lambda = empty) 00206 for (int i=tasks.size(); i--; ) { 00207 leaf(i).e = tasks[i].e(); 00208 leaf(i).le = 0.0; 00209 leaf(i).env = static_cast<double>(c)*tasks[i].est()+tasks[i].e(); 00210 leaf(i).lenv = -Int::Limits::double_infinity; 00211 leaf(i).resLe = OmegaLambdaNode::undef; 00212 leaf(i).resLenv = OmegaLambdaNode::undef; 00213 } 00214 init(); 00215 } 00216 00217 template<class TaskView> 00218 forceinline void 00219 OmegaLambdaTree<TaskView>::shift(int i) { 00220 // i is in omega 00221 assert(leaf(i).env > -Int::Limits::double_infinity); 00222 leaf(i).le = leaf(i).e; 00223 leaf(i).e = 0.0; 00224 leaf(i).lenv = leaf(i).env; 00225 leaf(i).env = -Int::Limits::double_infinity; 00226 leaf(i).resLe = i; 00227 leaf(i).resLenv = i; 00228 update(i); 00229 } 00230 00231 template<class TaskView> 00232 forceinline void 00233 OmegaLambdaTree<TaskView>::lremove(int i) { 00234 // i not in omega but in lambda 00235 assert(leaf(i).env == -Int::Limits::double_infinity); 00236 assert(leaf(i).lenv > -Int::Limits::double_infinity); 00237 leaf(i).le = 0.0; 00238 leaf(i).lenv = -Int::Limits::double_infinity; 00239 leaf(i).resLe = OmegaLambdaNode::undef; 00240 leaf(i).resLenv = OmegaLambdaNode::undef; 00241 update(i); 00242 } 00243 00244 template<class TaskView> 00245 forceinline bool 00246 OmegaLambdaTree<TaskView>::lempty(void) const { 00247 return root().resLenv < 0; 00248 } 00249 00250 template<class TaskView> 00251 forceinline int 00252 OmegaLambdaTree<TaskView>::responsible(void) const { 00253 return root().resLenv; 00254 } 00255 00256 template<class TaskView> 00257 forceinline double 00258 OmegaLambdaTree<TaskView>::env(void) const { 00259 return root().env; 00260 } 00261 00262 template<class TaskView> 00263 forceinline double 00264 OmegaLambdaTree<TaskView>::lenv(void) const { 00265 return root().lenv; 00266 } 00267 00268 }}} 00269 00270 // STATISTICS: scheduling-prop