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-05-27 13:09:22 +0200 (Thu, 27 May 2010) $ by $Author: tack $ 00011 * $Revision: 10977 $ 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 00040 namespace Gecode { namespace Scheduling { namespace Unary { 00041 00042 /* 00043 * Omega tree 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 // Check whether task i is in? 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 * Ome lambda tree 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 // Enter all tasks into tree (omega = all tasks, lambda = empty) 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 } else { 00151 // Enter no tasks into tree (omega = empty, lambda = empty) 00152 for (int i=tasks.size(); i--; ) { 00153 leaf(i).p = leaf(i).lp = 0; 00154 leaf(i).ect = leaf(i).lect = -Int::Limits::infinity; 00155 leaf(i).resEct = OmegaLambdaNode::undef; 00156 leaf(i).resLp = OmegaLambdaNode::undef; 00157 } 00158 } 00159 init(); 00160 } 00161 00162 template<class TaskView> 00163 forceinline void 00164 OmegaLambdaTree<TaskView>::shift(int i) { 00165 // That means that i is in omega 00166 assert(leaf(i).ect > -Int::Limits::infinity); 00167 leaf(i).p = 0; 00168 leaf(i).ect = -Int::Limits::infinity; 00169 leaf(i).resEct = i; 00170 leaf(i).resLp = i; 00171 update(i); 00172 } 00173 00174 template<class TaskView> 00175 forceinline void 00176 OmegaLambdaTree<TaskView>::oinsert(int i) { 00177 leaf(i).p = tasks[i].pmin(); 00178 leaf(i).ect = tasks[i].est()+tasks[i].pmin(); 00179 update(i); 00180 } 00181 00182 template<class TaskView> 00183 forceinline void 00184 OmegaLambdaTree<TaskView>::linsert(int i) { 00185 leaf(i).lp = tasks[i].pmin(); 00186 leaf(i).lect = tasks[i].est()+tasks[i].pmin(); 00187 leaf(i).resEct = i; 00188 leaf(i).resLp = i; 00189 update(i); 00190 } 00191 00192 template<class TaskView> 00193 forceinline void 00194 OmegaLambdaTree<TaskView>::lremove(int i) { 00195 leaf(i).lp = 0; 00196 leaf(i).lect = -Int::Limits::infinity; 00197 leaf(i).resEct = OmegaLambdaNode::undef; 00198 leaf(i).resLp = OmegaLambdaNode::undef; 00199 update(i); 00200 } 00201 00202 template<class TaskView> 00203 forceinline bool 00204 OmegaLambdaTree<TaskView>::lempty(void) const { 00205 return root().resEct < 0; 00206 } 00207 00208 template<class TaskView> 00209 forceinline int 00210 OmegaLambdaTree<TaskView>::responsible(void) const { 00211 return root().resEct; 00212 } 00213 00214 template<class TaskView> 00215 forceinline int 00216 OmegaLambdaTree<TaskView>::ect(void) const { 00217 return root().ect; 00218 } 00219 00220 template<class TaskView> 00221 forceinline int 00222 OmegaLambdaTree<TaskView>::lect(void) const { 00223 return root().lect; 00224 } 00225 00226 }}} 00227 00228 // STATISTICS: scheduling-prop