cumulative.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-07-15 12:39:29 +0200 (Thu, 15 Jul 2010) $ by $Author: tack $ 00011 * $Revision: 11199 $ 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_CUMULATIVE_HH__ 00039 #define __GECODE_SCHEDULING_CUMULATIVE_HH__ 00040 00041 #include <gecode/scheduling/task.hh> 00042 #include <gecode/scheduling/unary.hh> 00043 00057 namespace Gecode { namespace Scheduling { namespace Cumulative { 00058 00060 class ManFixPTask : public Unary::ManFixPTask { 00061 protected: 00063 int _c; 00064 public: 00066 00067 00068 ManFixPTask(void); 00070 ManFixPTask(IntVar s, int p, int c); 00072 void init(IntVar s, int p, int c); 00074 void init(const ManFixPTask& t); 00076 00078 00079 00080 int c(void) const; 00082 double e(void) const; 00084 00086 00087 00088 void update(Space& home, bool share, ManFixPTask& t); 00090 00091 }; 00092 00097 template<class Char, class Traits> 00098 std::basic_ostream<Char,Traits>& 00099 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t); 00100 00102 class ManFixPSETask : public Unary::ManFixPSETask { 00103 protected: 00105 int _c; 00106 public: 00108 00109 00110 ManFixPSETask(void); 00118 ManFixPSETask(TaskType t, IntVar s, int p, int c); 00126 void init(TaskType t, IntVar s, int p, int c); 00128 void init(const ManFixPSETask& t); 00130 00132 00133 00134 int c(void) const; 00136 double e(void) const; 00138 00140 00141 00142 void update(Space& home, bool share, ManFixPSETask& t); 00144 00145 }; 00146 00151 template<class Char, class Traits> 00152 std::basic_ostream<Char,Traits>& 00153 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t); 00154 00156 class ManFlexTask : public Unary::ManFlexTask { 00157 protected: 00159 int _c; 00160 public: 00162 00163 00164 ManFlexTask(void); 00166 ManFlexTask(IntVar s, IntVar p, IntVar e, int c); 00168 void init(IntVar s, IntVar p, IntVar e, int c); 00170 void init(const ManFlexTask& t); 00172 00174 00175 00176 int c(void) const; 00178 double e(void) const; 00180 00182 00183 00184 void update(Space& home, bool share, ManFlexTask& t); 00186 00187 }; 00188 00193 template<class Char, class Traits> 00194 std::basic_ostream<Char,Traits>& 00195 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t); 00196 00197 00199 class OptFixPTask : public ManToOptTask<ManFixPTask> { 00200 protected: 00201 using ManToOptTask<ManFixPTask>::_m; 00202 public: 00204 00205 00206 OptFixPTask(void); 00208 OptFixPTask(IntVar s, int p, int c, BoolVar m); 00210 void init(IntVar s, int p, int c, BoolVar m); 00212 }; 00213 00218 template<class Char, class Traits> 00219 std::basic_ostream<Char,Traits>& 00220 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t); 00221 00223 class OptFixPSETask : public ManToOptTask<ManFixPSETask> { 00224 protected: 00225 using ManToOptTask<ManFixPSETask>::_m; 00226 public: 00228 00229 00230 OptFixPSETask(void); 00232 OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m); 00234 void init(TaskType t, IntVar s, int p, int c, BoolVar m); 00236 }; 00237 00242 template<class Char, class Traits> 00243 std::basic_ostream<Char,Traits>& 00244 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t); 00245 00247 class OptFlexTask : public ManToOptTask<ManFlexTask> { 00248 protected: 00249 using ManToOptTask<ManFlexTask>::_m; 00250 public: 00252 00253 00254 OptFlexTask(void); 00256 OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m); 00258 void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m); 00260 }; 00261 00266 template<class Char, class Traits> 00267 std::basic_ostream<Char,Traits>& 00268 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t); 00269 00270 }}} 00271 00272 #include <gecode/scheduling/cumulative/task.hpp> 00273 00274 namespace Gecode { namespace Scheduling { namespace Cumulative { 00275 00277 typedef ManFixPTask ManFixPTaskFwd; 00278 00280 typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd; 00281 00283 typedef ManFixPSETask ManFixPSETaskFwd; 00284 00286 typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd; 00287 00289 typedef OptFixPTask OptFixPTaskFwd; 00290 00292 typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd; 00293 00295 typedef OptFixPSETask OptFixPSETaskFwd; 00296 00298 typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd; 00299 00301 typedef ManFlexTask ManFlexTaskFwd; 00302 00304 typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd; 00305 00307 typedef OptFlexTask OptFlexTaskFwd; 00308 00310 typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd; 00311 00312 00317 template<class Char, class Traits> 00318 std::basic_ostream<Char,Traits>& 00319 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t); 00320 00325 template<class Char, class Traits> 00326 std::basic_ostream<Char,Traits>& 00327 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t); 00328 00333 template<class Char, class Traits> 00334 std::basic_ostream<Char,Traits>& 00335 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t); 00336 00341 template<class Char, class Traits> 00342 std::basic_ostream<Char,Traits>& 00343 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t); 00344 00345 }}} 00346 00347 #include <gecode/scheduling/cumulative/task-view.hpp> 00348 00349 namespace Gecode { namespace Scheduling { 00350 00352 template<> 00353 class TaskViewTraits<Cumulative::ManFixPTaskFwd> { 00354 public: 00356 typedef Cumulative::ManFixPTask Task; 00357 }; 00358 00360 template<> 00361 class TaskViewTraits<Cumulative::ManFixPTaskBwd> { 00362 public: 00364 typedef Cumulative::ManFixPTask Task; 00365 }; 00366 00368 template<> 00369 class TaskViewTraits<Cumulative::ManFixPSETaskFwd> { 00370 public: 00372 typedef Cumulative::ManFixPSETask Task; 00373 }; 00374 00376 template<> 00377 class TaskViewTraits<Cumulative::ManFixPSETaskBwd> { 00378 public: 00380 typedef Cumulative::ManFixPSETask Task; 00381 }; 00382 00384 template<> 00385 class TaskViewTraits<Cumulative::OptFixPTaskFwd> { 00386 public: 00388 typedef Cumulative::OptFixPTask Task; 00389 }; 00390 00392 template<> 00393 class TaskViewTraits<Cumulative::OptFixPTaskBwd> { 00394 public: 00396 typedef Cumulative::OptFixPTask Task; 00397 }; 00398 00400 template<> 00401 class TaskViewTraits<Cumulative::OptFixPSETaskFwd> { 00402 public: 00404 typedef Cumulative::OptFixPSETask Task; 00405 }; 00406 00408 template<> 00409 class TaskViewTraits<Cumulative::OptFixPSETaskBwd> { 00410 public: 00412 typedef Cumulative::OptFixPSETask Task; 00413 }; 00414 00416 template<> 00417 class TaskViewTraits<Cumulative::ManFlexTaskFwd> { 00418 public: 00420 typedef Cumulative::ManFlexTask Task; 00421 }; 00422 00424 template<> 00425 class TaskViewTraits<Cumulative::ManFlexTaskBwd> { 00426 public: 00428 typedef Cumulative::ManFlexTask Task; 00429 }; 00430 00432 template<> 00433 class TaskViewTraits<Cumulative::OptFlexTaskFwd> { 00434 public: 00436 typedef Cumulative::OptFlexTask Task; 00437 }; 00438 00440 template<> 00441 class TaskViewTraits<Cumulative::OptFlexTaskBwd> { 00442 public: 00444 typedef Cumulative::OptFlexTask Task; 00445 }; 00446 00447 00449 template<> 00450 class TaskTraits<Cumulative::ManFixPTask> { 00451 public: 00453 typedef Cumulative::ManFixPTaskFwd TaskViewFwd; 00455 typedef Cumulative::ManFixPTaskBwd TaskViewBwd; 00456 }; 00457 00459 template<> 00460 class TaskTraits<Cumulative::ManFixPSETask> { 00461 public: 00463 typedef Cumulative::ManFixPSETaskFwd TaskViewFwd; 00465 typedef Cumulative::ManFixPSETaskBwd TaskViewBwd; 00466 }; 00467 00469 template<> 00470 class TaskTraits<Cumulative::OptFixPTask> { 00471 public: 00473 typedef Cumulative::OptFixPTaskFwd TaskViewFwd; 00475 typedef Cumulative::OptFixPTaskBwd TaskViewBwd; 00477 typedef Cumulative::ManFixPTask ManTask; 00478 }; 00479 00481 template<> 00482 class TaskTraits<Cumulative::OptFixPSETask> { 00483 public: 00485 typedef Cumulative::OptFixPSETaskFwd TaskViewFwd; 00487 typedef Cumulative::OptFixPSETaskBwd TaskViewBwd; 00489 typedef Cumulative::ManFixPSETask ManTask; 00490 }; 00491 00493 template<> 00494 class TaskTraits<Cumulative::ManFlexTask> { 00495 public: 00497 typedef Cumulative::ManFlexTaskFwd TaskViewFwd; 00499 typedef Cumulative::ManFlexTaskBwd TaskViewBwd; 00500 }; 00501 00503 template<> 00504 class TaskTraits<Cumulative::OptFlexTask> { 00505 public: 00507 typedef Cumulative::OptFlexTaskFwd TaskViewFwd; 00509 typedef Cumulative::OptFlexTaskBwd TaskViewBwd; 00511 typedef Cumulative::ManFlexTask ManTask; 00512 }; 00513 00514 }} 00515 00516 namespace Gecode { namespace Scheduling { namespace Cumulative { 00517 00519 class OmegaNode { 00520 public: 00522 double e; 00524 double env; 00526 void init(const OmegaNode& l, const OmegaNode& r); 00528 void update(const OmegaNode& l, const OmegaNode& r); 00529 }; 00530 00532 template<class TaskView> 00533 class OmegaTree : public TaskTree<TaskView,OmegaNode> { 00534 protected: 00535 using TaskTree<TaskView,OmegaNode>::tasks; 00536 using TaskTree<TaskView,OmegaNode>::leaf; 00537 using TaskTree<TaskView,OmegaNode>::root; 00538 using TaskTree<TaskView,OmegaNode>::init; 00539 using TaskTree<TaskView,OmegaNode>::update; 00541 int c; 00542 public: 00544 OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t); 00546 void insert(int i); 00548 void remove(int i); 00550 double env(void) const; 00551 }; 00552 00554 class ExtOmegaNode : public OmegaNode { 00555 public: 00557 double cenv; 00559 void init(const ExtOmegaNode& l, const ExtOmegaNode& r); 00561 void update(const ExtOmegaNode& l, const ExtOmegaNode& r); 00562 }; 00563 00565 template<class TaskView> 00566 class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> { 00567 protected: 00568 using TaskTree<TaskView,ExtOmegaNode>::tasks; 00569 using TaskTree<TaskView,ExtOmegaNode>::leaf; 00570 using TaskTree<TaskView,ExtOmegaNode>::root; 00571 using TaskTree<TaskView,ExtOmegaNode>::init; 00572 using TaskTree<TaskView,ExtOmegaNode>::update; 00573 using TaskTree<TaskView,ExtOmegaNode>::node; 00574 using TaskTree<TaskView,ExtOmegaNode>::n_leaf; 00575 using TaskTree<TaskView,ExtOmegaNode>::n_left; 00576 using TaskTree<TaskView,ExtOmegaNode>::left; 00577 using TaskTree<TaskView,ExtOmegaNode>::n_right; 00578 using TaskTree<TaskView,ExtOmegaNode>::right; 00579 using TaskTree<TaskView,ExtOmegaNode>::n_root; 00580 using TaskTree<TaskView,ExtOmegaNode>::n_parent; 00581 using TaskTree<TaskView,ExtOmegaNode>::n_nodes; 00582 using TaskTree<TaskView,ExtOmegaNode>::_leaf; 00584 int c, ci; 00585 public: 00587 template<class Node> 00588 ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t); 00590 void init(int ci); 00592 double env(int i); 00593 }; 00594 00595 00597 class OmegaLambdaNode : public OmegaNode { 00598 public: 00600 static const int undef = -1; 00602 double le; 00604 double lenv; 00606 int resLe; 00608 int resLenv; 00610 void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r); 00612 void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r); 00613 }; 00614 00616 template<class TaskView> 00617 class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> { 00618 protected: 00619 using TaskTree<TaskView,OmegaLambdaNode>::tasks; 00620 using TaskTree<TaskView,OmegaLambdaNode>::leaf; 00621 using TaskTree<TaskView,OmegaLambdaNode>::root; 00622 using TaskTree<TaskView,OmegaLambdaNode>::init; 00623 using TaskTree<TaskView,OmegaLambdaNode>::update; 00625 int c; 00626 public: 00628 OmegaLambdaTree(Region& r, int c, const TaskViewArray<TaskView>& t); 00630 void shift(int i); 00632 void lremove(int i); 00634 bool lempty(void) const; 00636 int responsible(void) const; 00638 double env(void) const; 00640 double lenv(void) const; 00641 }; 00642 00643 }}} 00644 00645 #include <gecode/scheduling/cumulative/tree.hpp> 00646 00647 namespace Gecode { namespace Scheduling { namespace Cumulative { 00648 00650 template<class Task> 00651 ExecStatus basic(Space& home, Propagator& p, int c, TaskArray<Task>& t); 00652 00654 template<class ManTask> 00655 ExecStatus overload(Space& home, int c, TaskArray<ManTask>& t); 00656 00658 template<class Task> 00659 ExecStatus edgefinding(Space& home, int c, TaskArray<Task>& t); 00660 00667 template<class ManTask> 00668 class ManProp : public TaskProp<ManTask,Int::PC_INT_DOM> { 00669 protected: 00670 using TaskProp<ManTask,Int::PC_INT_DOM>::t; 00672 int c; 00674 ManProp(Home home, int c, TaskArray<ManTask>& t); 00676 ManProp(Space& home, bool shared, ManProp& p); 00677 public: 00679 virtual Actor* copy(Space& home, bool share); 00681 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00683 static ExecStatus post(Home home, int c, TaskArray<ManTask>& t); 00685 virtual size_t dispose(Space& home); 00686 }; 00687 00694 template<class OptTask> 00695 class OptProp : public TaskProp<OptTask,Int::PC_INT_DOM> { 00696 protected: 00697 using TaskProp<OptTask,Int::PC_INT_DOM>::t; 00699 int c; 00701 OptProp(Home home, int c, TaskArray<OptTask>& t); 00703 OptProp(Space& home, bool shared, OptProp& p); 00704 public: 00706 virtual Actor* copy(Space& home, bool share); 00708 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00710 static ExecStatus post(Home home, int c, TaskArray<OptTask>& t); 00712 virtual size_t dispose(Space& home); 00713 }; 00714 00715 }}} 00716 00717 #include <gecode/scheduling/cumulative/basic.hpp> 00718 #include <gecode/scheduling/cumulative/overload.hpp> 00719 #include <gecode/scheduling/cumulative/edge-finding.hpp> 00720 #include <gecode/scheduling/cumulative/man-prop.hpp> 00721 #include <gecode/scheduling/cumulative/opt-prop.hpp> 00722 00723 #endif 00724 00725 // STATISTICS: scheduling-prop