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 #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);
00092 void cancel(Space& home, Propagator& p);
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
00119
00120
00121 ModEvent est(Space& home, int n);
00123 ModEvent ect(Space& home, int n);
00125 ModEvent lst(Space& home, int n);
00127 ModEvent lct(Space& home, int n);
00129 };
00130
00131 }}
00132
00133 #include <gecode/scheduling/task/fwd-to-bwd.hpp>
00134
00135 namespace Gecode { namespace Scheduling {
00136
00143 template<class TaskView>
00144 class TaskViewTraits {};
00145
00152 template<class Task>
00153 class TaskTraits {};
00154
00155 }}
00156
00157 namespace Gecode { namespace Scheduling {
00158
00160 template<class Task>
00161 class TaskArray {
00162 private:
00164 int n;
00166 Task* t;
00167 public:
00169
00170
00171 TaskArray(void);
00173 TaskArray(Space& home, int n);
00175 TaskArray(const TaskArray<Task>& a);
00177 const TaskArray<Task>& operator =(const TaskArray<Task>& a);
00179
00181
00182
00183 int size(void) const;
00185 void size(int n);
00187
00189
00190
00191 Task& operator [](int i);
00193 const Task& operator [](int i) const;
00195
00197
00198
00199 void subscribe(Space& home, Propagator& p);
00201 void cancel(Space& home, Propagator& p);
00203
00205
00206
00207 void update(Space&, bool share, TaskArray& a);
00209
00210 private:
00211 static void* operator new(size_t);
00212 static void operator delete(void*,size_t);
00213 };
00214
00219 template<class Char, class Traits, class Task>
00220 std::basic_ostream<Char,Traits>&
00221 operator <<(std::basic_ostream<Char,Traits>& os,
00222 const TaskArray<Task>& t);
00223
00224
00226 template<class TaskView>
00227 class TaskViewArray {
00228 protected:
00230 typedef typename TaskViewTraits<TaskView>::Task Task;
00232 TaskArray<Task>& t;
00233 public:
00235
00236
00237 TaskViewArray(TaskArray<Task>& t);
00239
00241
00242
00243 int size(void) const;
00245 void size(int n);
00247
00249
00250
00251 TaskView& operator [](int i);
00253 const TaskView& operator [](int i) const;
00255 private:
00256 static void* operator new(size_t);
00257 static void operator delete(void*,size_t);
00258 };
00259
00264 template<class Char, class Traits, class TaskView>
00265 std::basic_ostream<Char,Traits>&
00266 operator <<(std::basic_ostream<Char,Traits>& os,
00267 const TaskViewArray<TaskView>& t);
00268
00269 }}
00270
00271 #include <gecode/scheduling/task/array.hpp>
00272
00273 namespace Gecode { namespace Scheduling {
00274
00276 enum SortTaskOrder {
00277 STO_EST,
00278 STO_ECT,
00279 STO_LST,
00280 STO_LCT
00281 };
00282
00284 template<class TaskView, SortTaskOrder sto, bool inc>
00285 void sort(TaskViewArray<TaskView>& t);
00286
00288 template<class TaskView, SortTaskOrder sto, bool inc>
00289 void sort(int* map, const TaskViewArray<TaskView>& t);
00290
00292 template<class TaskView, SortTaskOrder sto, bool inc>
00293 void sort(int* map, int n, const TaskViewArray<TaskView>& t);
00294
00295 }}
00296
00297 #include <gecode/scheduling/task/sort.hpp>
00298
00299 namespace Gecode { namespace Scheduling {
00300
00302 template<class TaskView, SortTaskOrder sto, bool inc>
00303 class TaskViewIter {
00304 protected:
00306 int* map;
00308 int i;
00310 TaskViewIter(void);
00311 public:
00313 TaskViewIter(Region& r, const TaskViewArray<TaskView>& t);
00315
00316
00317 bool operator ()(void) const;
00319 int left(void) const;
00321 void operator ++(void);
00323
00325
00326
00327 int task(void) const;
00329 };
00330
00332 template<class OptTaskView, SortTaskOrder sto, bool inc>
00333 class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
00334 protected:
00335 using TaskViewIter<OptTaskView,sto,inc>::map;
00336 using TaskViewIter<OptTaskView,sto,inc>::i;
00337 public:
00339 ManTaskViewIter(Region& r, const TaskViewArray<OptTaskView>& t);
00340 };
00341
00342 }}
00343
00344 #include <gecode/scheduling/task/iter.hpp>
00345
00346 namespace Gecode { namespace Scheduling {
00347
00349 int plus(int x, int y);
00350
00352 template<class TaskView, class Node>
00353 class TaskTree {
00354 protected:
00356 const TaskViewArray<TaskView>& tasks;
00358 Node* node;
00360 int* _leaf;
00361
00363 int n_inner(void) const;
00365 int n_nodes(void) const;
00367 static bool n_root(int i);
00369 bool n_leaf(int i) const;
00371 static int n_left(int i);
00373 static int n_right(int i);
00375 static int n_parent(int i);
00376 protected:
00378 Node& leaf(int i);
00380 const Node& root(void) const;
00382 void update(int i, bool l=true);
00384 void init(void);
00386 TaskTree(Region& r, const TaskViewArray<TaskView>& t);
00387 };
00388
00389 }}
00390
00391 #include <gecode/scheduling/task/tree.hpp>
00392
00393 namespace Gecode { namespace Scheduling {
00394
00401 template<class Task>
00402 class TaskProp : public Propagator {
00403 protected:
00405 TaskArray<Task> t;
00407 TaskProp(Home home, TaskArray<Task>& t);
00409 TaskProp(Space& home, bool shared, TaskProp<Task>& p);
00410 public:
00412 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00414 virtual size_t dispose(Space& home);
00415 };
00416
00418 template<class OptTask>
00419 ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t);
00420
00421 }}
00422
00423 #include <gecode/scheduling/task/prop.hpp>
00424 #include <gecode/scheduling/task/purge.hpp>
00425
00426 #endif
00427
00428