task.hh
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-09-27 15:45:13 +0200 (Mon, 27 Sep 2010) $ by $Author: schulte $ 00011 * $Revision: 11420 $ 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 #ifndef __GECODE_SCHEDULING_TASK_HH__ 00039 #define __GECODE_SCHEDULING_TASK_HH__ 00040 00041 #include <gecode/scheduling.hh> 00042 00043 namespace Gecode { namespace Scheduling { 00044 00046 template<class ManTask> 00047 class ManToOptTask : public ManTask { 00048 protected: 00050 Int::BoolView _m; 00051 public: 00053 00054 00055 ManToOptTask(void); 00057 00059 00060 00061 bool mandatory(void) const; 00063 bool excluded(void) const; 00065 bool optional(void) const; 00067 00069 00070 bool assigned(void) const; 00072 00074 00075 00076 ModEvent mandatory(Space& home); 00078 ModEvent excluded(Space& home); 00080 00082 00083 00084 void update(Space& home, bool share, ManToOptTask& t); 00086 00088 00089 00090 void subscribe(Space& home, Propagator& p, PropCond pc); 00092 void cancel(Space& home, Propagator& p, PropCond pc); 00094 }; 00095 00096 }} 00097 00098 #include <gecode/scheduling/task/man-to-opt.hpp> 00099 00100 namespace Gecode { namespace Scheduling { 00101 00103 template<class TaskView> 00104 class FwdToBwd : public TaskView { 00105 public: 00107 00108 00109 int est(void) const; 00111 int ect(void) const; 00113 int lst(void) const; 00115 int lct(void) const; 00117 int pmin(void) const; 00119 int pmax(void) const; 00121 00123 00124 00125 ModEvent est(Space& home, int n); 00127 ModEvent ect(Space& home, int n); 00129 ModEvent lst(Space& home, int n); 00131 ModEvent lct(Space& home, int n); 00133 ModEvent norun(Space& home, int e, int l); 00135 }; 00136 00137 }} 00138 00139 #include <gecode/scheduling/task/fwd-to-bwd.hpp> 00140 00141 namespace Gecode { namespace Scheduling { 00142 00149 template<class TaskView> 00150 class TaskViewTraits {}; 00151 00158 template<class Task> 00159 class TaskTraits {}; 00160 00161 }} 00162 00163 namespace Gecode { namespace Scheduling { 00164 00166 template<class Task> 00167 class TaskArray { 00168 private: 00170 int n; 00172 Task* t; 00173 public: 00175 00176 00177 TaskArray(void); 00179 TaskArray(Space& home, int n); 00181 TaskArray(const TaskArray<Task>& a); 00183 const TaskArray<Task>& operator =(const TaskArray<Task>& a); 00185 00187 00188 00189 int size(void) const; 00191 void size(int n); 00193 00195 00196 00197 Task& operator [](int i); 00199 const Task& operator [](int i) const; 00201 00203 00204 00205 void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00207 void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00209 00211 00212 00213 void update(Space&, bool share, TaskArray& a); 00215 00216 private: 00217 static void* operator new(size_t); 00218 static void operator delete(void*,size_t); 00219 }; 00220 00225 template<class Char, class Traits, class Task> 00226 std::basic_ostream<Char,Traits>& 00227 operator <<(std::basic_ostream<Char,Traits>& os, 00228 const TaskArray<Task>& t); 00229 00230 00232 template<class TaskView> 00233 class TaskViewArray { 00234 protected: 00236 typedef typename TaskViewTraits<TaskView>::Task Task; 00238 TaskArray<Task>& t; 00239 public: 00241 00242 00243 TaskViewArray(TaskArray<Task>& t); 00245 00247 00248 00249 int size(void) const; 00251 void size(int n); 00253 00255 00256 00257 TaskView& operator [](int i); 00259 const TaskView& operator [](int i) const; 00261 private: 00262 static void* operator new(size_t); 00263 static void operator delete(void*,size_t); 00264 }; 00265 00270 template<class Char, class Traits, class TaskView> 00271 std::basic_ostream<Char,Traits>& 00272 operator <<(std::basic_ostream<Char,Traits>& os, 00273 const TaskViewArray<TaskView>& t); 00274 00275 }} 00276 00277 #include <gecode/scheduling/task/array.hpp> 00278 00279 namespace Gecode { namespace Scheduling { 00280 00282 enum SortTaskOrder { 00283 STO_EST, 00284 STO_ECT, 00285 STO_LST, 00286 STO_LCT 00287 }; 00288 00290 template<class TaskView, SortTaskOrder sto, bool inc> 00291 void sort(TaskViewArray<TaskView>& t); 00292 00294 template<class TaskView, SortTaskOrder sto, bool inc> 00295 void sort(int* map, const TaskViewArray<TaskView>& t); 00296 00298 template<class TaskView, SortTaskOrder sto, bool inc> 00299 void sort(int* map, int n, const TaskViewArray<TaskView>& t); 00300 00301 }} 00302 00303 #include <gecode/scheduling/task/sort.hpp> 00304 00305 namespace Gecode { namespace Scheduling { 00306 00308 template<class TaskView, SortTaskOrder sto, bool inc> 00309 class TaskViewIter { 00310 protected: 00312 int* map; 00314 int i; 00316 TaskViewIter(void); 00317 public: 00319 TaskViewIter(Region& r, const TaskViewArray<TaskView>& t); 00321 00322 00323 bool operator ()(void) const; 00325 int left(void) const; 00327 void operator ++(void); 00329 00331 00332 00333 int task(void) const; 00335 }; 00336 00338 template<class OptTaskView, SortTaskOrder sto, bool inc> 00339 class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> { 00340 protected: 00341 using TaskViewIter<OptTaskView,sto,inc>::map; 00342 using TaskViewIter<OptTaskView,sto,inc>::i; 00343 public: 00345 ManTaskViewIter(Region& r, const TaskViewArray<OptTaskView>& t); 00346 }; 00347 00348 }} 00349 00350 #include <gecode/scheduling/task/iter.hpp> 00351 00352 namespace Gecode { namespace Scheduling { 00353 00355 int plus(int x, int y); 00356 00358 double plus(double x, double y); 00359 00361 double div(double x, double y); 00362 00364 template<class TaskView, class Node> 00365 class TaskTree { 00366 template<class,class> friend class TaskTree; 00367 protected: 00369 const TaskViewArray<TaskView>& tasks; 00371 Node* node; 00373 int* _leaf; 00374 00376 int n_inner(void) const; 00378 int n_nodes(void) const; 00380 static bool n_root(int i); 00382 bool n_leaf(int i) const; 00384 static int n_left(int i); 00386 static bool left(int i); 00388 static int n_right(int i); 00390 static bool right(int i); 00392 static int n_parent(int i); 00393 protected: 00395 Node& leaf(int i); 00397 const Node& root(void) const; 00399 void update(int i, bool l=true); 00401 void init(void); 00403 void update(void); 00405 TaskTree(Region& r, const TaskViewArray<TaskView>& t); 00407 template<class Node2> TaskTree(Region& r, 00408 const TaskTree<TaskView,Node2>& t); 00409 }; 00410 00411 }} 00412 00413 #include <gecode/scheduling/task/tree.hpp> 00414 00415 namespace Gecode { namespace Scheduling { 00416 00423 template<class Task, PropCond pc> 00424 class TaskProp : public Propagator { 00425 protected: 00427 TaskArray<Task> t; 00429 TaskProp(Home home, TaskArray<Task>& t); 00431 TaskProp(Space& home, bool shared, TaskProp<Task,pc>& p); 00432 public: 00434 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00436 virtual size_t dispose(Space& home); 00437 }; 00438 00440 template<class OptTask,PropCond pc> 00441 ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t); 00442 00443 }} 00444 00445 #include <gecode/scheduling/task/prop.hpp> 00446 #include <gecode/scheduling/task/purge.hpp> 00447 00448 #endif 00449 00450 // STATISTICS: scheduling-prop