unary.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 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2009 00009 * Guido Tack, 2010 00010 * 00011 * Last modified: 00012 * $Date: 2011-01-18 23:37:08 +0100 (Tue, 18 Jan 2011) $ by $Author: tack $ 00013 * $Revision: 11551 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #ifndef __GECODE_SCHEDULING_UNARY_HH__ 00041 #define __GECODE_SCHEDULING_UNARY_HH__ 00042 00043 #include <gecode/scheduling/task.hh> 00044 00055 namespace Gecode { namespace Scheduling { namespace Unary { 00056 00058 class ManFixPTask { 00059 protected: 00061 Int::IntView _s; 00063 int _p; 00064 public: 00066 00067 00068 ManFixPTask(void); 00070 ManFixPTask(IntVar s, int p); 00072 void init(IntVar s, int p); 00074 void init(const ManFixPTask& t); 00076 00078 00079 00080 int est(void) const; 00082 int ect(void) const; 00084 int lst(void) const; 00086 int lct(void) const; 00088 int pmin(void) const; 00090 int pmax(void) const; 00092 IntVar st(void) const; 00094 bool mandatory(void) const; 00096 bool excluded(void) const; 00098 bool optional(void) const; 00100 00102 00103 00104 bool assigned(void) const; 00106 00108 00109 00110 ModEvent est(Space& home, int n); 00112 ModEvent ect(Space& home, int n); 00114 ModEvent lst(Space& home, int n); 00116 ModEvent lct(Space& home, int n); 00118 ModEvent norun(Space& home, int e, int l); 00120 ModEvent mandatory(Space& home); 00122 ModEvent excluded(Space& home); 00124 00126 00127 00128 void update(Space& home, bool share, ManFixPTask& t); 00130 00132 00133 00134 void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00136 void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00138 00139 }; 00140 00145 template<class Char, class Traits> 00146 std::basic_ostream<Char,Traits>& 00147 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t); 00148 00149 class ManFixPSETask : public ManFixPTask { 00150 protected: 00152 TaskType _t; 00153 public: 00155 00156 00157 ManFixPSETask(void); 00164 ManFixPSETask(TaskType t, IntVar s, int p); 00171 void init(TaskType t, IntVar s, int p); 00173 void init(const ManFixPSETask& t); 00175 00177 00178 00179 int est(void) const; 00181 int ect(void) const; 00183 int lst(void) const; 00185 int lct(void) const; 00187 int pmin(void) const; 00189 int pmax(void) const; 00191 00193 00194 00195 ModEvent est(Space& home, int n); 00197 ModEvent ect(Space& home, int n); 00199 ModEvent lst(Space& home, int n); 00201 ModEvent lct(Space& home, int n); 00203 ModEvent norun(Space& home, int e, int l); 00205 00207 00208 00209 void update(Space& home, bool share, ManFixPSETask& t); 00211 00212 }; 00213 00218 template<class Char, class Traits> 00219 std::basic_ostream<Char,Traits>& 00220 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t); 00221 00223 class OptFixPTask : public ManToOptTask<ManFixPTask> { 00224 protected: 00225 using ManToOptTask<ManFixPTask>::_m; 00226 public: 00228 00229 00230 OptFixPTask(void); 00232 OptFixPTask(IntVar s, int p, BoolVar m); 00234 void init(IntVar s, int p, 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 OptFixPTask& t); 00245 00247 class OptFixPSETask : public ManToOptTask<ManFixPSETask> { 00248 protected: 00249 using ManToOptTask<ManFixPSETask>::_m; 00250 public: 00252 00253 00254 OptFixPSETask(void); 00256 OptFixPSETask(TaskType t, IntVar s, int p, BoolVar m); 00258 void init(TaskType t, IntVar s, int p, 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 OptFixPSETask& t); 00269 00271 class ManFlexTask { 00272 protected: 00274 Int::IntView _s; 00276 Int::IntView _p; 00278 Int::IntView _e; 00279 public: 00281 00282 00283 ManFlexTask(void); 00285 ManFlexTask(IntVar s, IntVar p, IntVar e); 00287 void init(IntVar s, IntVar p, IntVar e); 00289 void init(const ManFlexTask& t); 00291 00293 00294 00295 int est(void) const; 00297 int ect(void) const; 00299 int lst(void) const; 00301 int lct(void) const; 00303 int pmin(void) const; 00305 int pmax(void) const; 00307 IntVar st(void) const; 00309 IntVar p(void) const; 00311 IntVar e(void) const; 00313 bool mandatory(void) const; 00315 bool excluded(void) const; 00317 bool optional(void) const; 00319 00321 00322 00323 bool assigned(void) const; 00325 00327 00328 00329 ModEvent est(Space& home, int n); 00331 ModEvent ect(Space& home, int n); 00333 ModEvent lst(Space& home, int n); 00335 ModEvent lct(Space& home, int n); 00337 ModEvent norun(Space& home, int e, int l); 00339 ModEvent mandatory(Space& home); 00341 ModEvent excluded(Space& home); 00343 00345 00346 00347 void update(Space& home, bool share, ManFlexTask& t); 00349 00351 00352 00353 void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00355 void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00357 00358 }; 00359 00364 template<class Char, class Traits> 00365 std::basic_ostream<Char,Traits>& 00366 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t); 00367 00369 class OptFlexTask : public ManToOptTask<ManFlexTask> { 00370 protected: 00371 using ManToOptTask<ManFlexTask>::_m; 00372 public: 00374 00375 00376 OptFlexTask(void); 00378 OptFlexTask(IntVar s, IntVar p, IntVar e, BoolVar m); 00380 void init(IntVar s, IntVar p, IntVar e, BoolVar m); 00382 }; 00383 00388 template<class Char, class Traits> 00389 std::basic_ostream<Char,Traits>& 00390 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t); 00391 00392 }}} 00393 00394 #include <gecode/scheduling/unary/task.hpp> 00395 00396 namespace Gecode { namespace Scheduling { namespace Unary { 00397 00399 typedef ManFixPTask ManFixPTaskFwd; 00400 00402 typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd; 00403 00405 typedef ManFixPSETask ManFixPSETaskFwd; 00406 00408 typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd; 00409 00411 typedef OptFixPTask OptFixPTaskFwd; 00412 00414 typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd; 00415 00417 typedef OptFixPSETask OptFixPSETaskFwd; 00418 00420 typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd; 00421 00423 typedef ManFlexTask ManFlexTaskFwd; 00424 00426 typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd; 00427 00429 typedef OptFlexTask OptFlexTaskFwd; 00430 00432 typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd; 00433 00434 00439 template<class Char, class Traits> 00440 std::basic_ostream<Char,Traits>& 00441 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t); 00442 00447 template<class Char, class Traits> 00448 std::basic_ostream<Char,Traits>& 00449 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t); 00450 00455 template<class Char, class Traits> 00456 std::basic_ostream<Char,Traits>& 00457 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t); 00458 00463 template<class Char, class Traits> 00464 std::basic_ostream<Char,Traits>& 00465 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t); 00466 00471 template<class Char, class Traits> 00472 std::basic_ostream<Char,Traits>& 00473 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTaskBwd& t); 00474 00481 template<class Char, class Traits> 00482 std::basic_ostream<Char,Traits>& 00483 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTaskBwd& t); 00484 00485 }}} 00486 00487 #include <gecode/scheduling/unary/task-view.hpp> 00488 00489 namespace Gecode { namespace Scheduling { 00490 00492 template<> 00493 class TaskViewTraits<Unary::ManFixPTaskFwd> { 00494 public: 00496 typedef Unary::ManFixPTask Task; 00497 }; 00498 00500 template<> 00501 class TaskViewTraits<Unary::ManFixPTaskBwd> { 00502 public: 00504 typedef Unary::ManFixPTask Task; 00505 }; 00506 00508 template<> 00509 class TaskViewTraits<Unary::ManFixPSETaskFwd> { 00510 public: 00512 typedef Unary::ManFixPSETask Task; 00513 }; 00514 00516 template<> 00517 class TaskViewTraits<Unary::ManFixPSETaskBwd> { 00518 public: 00520 typedef Unary::ManFixPSETask Task; 00521 }; 00522 00524 template<> 00525 class TaskViewTraits<Unary::OptFixPTaskFwd> { 00526 public: 00528 typedef Unary::OptFixPTask Task; 00529 }; 00530 00532 template<> 00533 class TaskViewTraits<Unary::OptFixPTaskBwd> { 00534 public: 00536 typedef Unary::OptFixPTask Task; 00537 }; 00538 00540 template<> 00541 class TaskViewTraits<Unary::OptFixPSETaskFwd> { 00542 public: 00544 typedef Unary::OptFixPSETask Task; 00545 }; 00546 00548 template<> 00549 class TaskViewTraits<Unary::OptFixPSETaskBwd> { 00550 public: 00552 typedef Unary::OptFixPSETask Task; 00553 }; 00554 00556 template<> 00557 class TaskViewTraits<Unary::ManFlexTaskFwd> { 00558 public: 00560 typedef Unary::ManFlexTask Task; 00561 }; 00562 00564 template<> 00565 class TaskViewTraits<Unary::ManFlexTaskBwd> { 00566 public: 00568 typedef Unary::ManFlexTask Task; 00569 }; 00570 00572 template<> 00573 class TaskViewTraits<Unary::OptFlexTaskFwd> { 00574 public: 00576 typedef Unary::OptFlexTask Task; 00577 }; 00578 00580 template<> 00581 class TaskViewTraits<Unary::OptFlexTaskBwd> { 00582 public: 00584 typedef Unary::OptFlexTask Task; 00585 }; 00586 00587 00589 template<> 00590 class TaskTraits<Unary::ManFixPTask> { 00591 public: 00593 typedef Unary::ManFixPTaskFwd TaskViewFwd; 00595 typedef Unary::ManFixPTaskBwd TaskViewBwd; 00596 }; 00597 00599 template<> 00600 class TaskTraits<Unary::ManFixPSETask> { 00601 public: 00603 typedef Unary::ManFixPSETaskFwd TaskViewFwd; 00605 typedef Unary::ManFixPSETaskBwd TaskViewBwd; 00606 }; 00607 00609 template<> 00610 class TaskTraits<Unary::OptFixPTask> { 00611 public: 00613 typedef Unary::OptFixPTaskFwd TaskViewFwd; 00615 typedef Unary::OptFixPTaskBwd TaskViewBwd; 00617 typedef Unary::ManFixPTask ManTask; 00618 }; 00619 00621 template<> 00622 class TaskTraits<Unary::OptFixPSETask> { 00623 public: 00625 typedef Unary::OptFixPSETaskFwd TaskViewFwd; 00627 typedef Unary::OptFixPSETaskBwd TaskViewBwd; 00629 typedef Unary::ManFixPTask ManTask; 00630 }; 00631 00633 template<> 00634 class TaskTraits<Unary::ManFlexTask> { 00635 public: 00637 typedef Unary::ManFlexTaskFwd TaskViewFwd; 00639 typedef Unary::ManFlexTaskBwd TaskViewBwd; 00640 }; 00641 00643 template<> 00644 class TaskTraits<Unary::OptFlexTask> { 00645 public: 00647 typedef Unary::OptFlexTaskFwd TaskViewFwd; 00649 typedef Unary::OptFlexTaskBwd TaskViewBwd; 00651 typedef Unary::ManFlexTask ManTask; 00652 }; 00653 00654 }} 00655 00656 namespace Gecode { namespace Scheduling { namespace Unary { 00657 00659 class OmegaNode { 00660 public: 00662 int p; 00664 int ect; 00666 void init(const OmegaNode& l, const OmegaNode& r); 00668 void update(const OmegaNode& l, const OmegaNode& r); 00669 }; 00670 00672 template<class TaskView> 00673 class OmegaTree : public TaskTree<TaskView,OmegaNode> { 00674 protected: 00675 using TaskTree<TaskView,OmegaNode>::tasks; 00676 using TaskTree<TaskView,OmegaNode>::leaf; 00677 using TaskTree<TaskView,OmegaNode>::root; 00678 using TaskTree<TaskView,OmegaNode>::init; 00679 using TaskTree<TaskView,OmegaNode>::update; 00680 public: 00682 OmegaTree(Region& r, const TaskViewArray<TaskView>& t); 00684 void insert(int i); 00686 void remove(int i); 00688 int ect(void) const; 00690 int ect(int i) const; 00691 }; 00692 00694 class OmegaLambdaNode : public OmegaNode { 00695 public: 00697 static const int undef = -1; 00699 int lp; 00701 int lect; 00703 int resEct; 00705 int resLp; 00707 void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r); 00709 void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r); 00710 }; 00711 00713 template<class TaskView> 00714 class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> { 00715 protected: 00716 using TaskTree<TaskView,OmegaLambdaNode>::tasks; 00717 using TaskTree<TaskView,OmegaLambdaNode>::leaf; 00718 using TaskTree<TaskView,OmegaLambdaNode>::root; 00719 using TaskTree<TaskView,OmegaLambdaNode>::init; 00720 using TaskTree<TaskView,OmegaLambdaNode>::update; 00721 public: 00723 OmegaLambdaTree(Region& r, const TaskViewArray<TaskView>& t, 00724 bool inc=true); 00726 void shift(int i); 00728 void oinsert(int i); 00730 void linsert(int i); 00732 void lremove(int i); 00734 bool lempty(void) const; 00736 int responsible(void) const; 00738 int ect(void) const; 00740 int lect(void) const; 00741 }; 00742 00743 }}} 00744 00745 #include <gecode/scheduling/unary/tree.hpp> 00746 00747 namespace Gecode { namespace Scheduling { namespace Unary { 00748 00750 template<class ManTask> 00751 ExecStatus overload(Space& home, TaskArray<ManTask>& t); 00753 template<class OptTask> 00754 ExecStatus overload(Space& home, Propagator& p, TaskArray<OptTask>& t); 00755 00757 template<class Task> 00758 ExecStatus subsumed(Space& home, Propagator& p, TaskArray<Task>& t); 00759 00761 template<class ManTask> 00762 ExecStatus detectable(Space& home, TaskArray<ManTask>& t); 00764 template<class OptTask> 00765 ExecStatus detectable(Space& home, Propagator& p, TaskArray<OptTask>& t); 00766 00768 template<class ManTask> 00769 ExecStatus notfirstnotlast(Space& home, TaskArray<ManTask>& t); 00771 template<class OptTask> 00772 ExecStatus notfirstnotlast(Space& home, Propagator& p, TaskArray<OptTask>& t); 00773 00775 template<class Task> 00776 ExecStatus edgefinding(Space& home, TaskArray<Task>& t); 00777 00778 00785 template<class ManTask> 00786 class ManProp : public TaskProp<ManTask,Int::PC_INT_BND> { 00787 protected: 00788 using TaskProp<ManTask,Int::PC_INT_BND>::t; 00790 ManProp(Home home, TaskArray<ManTask>& t); 00792 ManProp(Space& home, bool shared, ManProp& p); 00793 public: 00795 virtual Actor* copy(Space& home, bool share); 00797 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00799 static ExecStatus post(Home home, TaskArray<ManTask>& t); 00800 }; 00801 00808 template<class OptTask> 00809 class OptProp : public TaskProp<OptTask,Int::PC_INT_BND> { 00810 protected: 00811 using TaskProp<OptTask,Int::PC_INT_BND>::t; 00813 OptProp(Home home, TaskArray<OptTask>& t); 00815 OptProp(Space& home, bool shared, OptProp& p); 00816 public: 00818 virtual Actor* copy(Space& home, bool share); 00820 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00822 static ExecStatus post(Home home, TaskArray<OptTask>& t); 00823 }; 00824 00825 }}} 00826 00827 #include <gecode/scheduling/unary/overload.hpp> 00828 #include <gecode/scheduling/unary/subsumption.hpp> 00829 #include <gecode/scheduling/unary/detectable.hpp> 00830 #include <gecode/scheduling/unary/not-first-not-last.hpp> 00831 #include <gecode/scheduling/unary/edge-finding.hpp> 00832 00833 #include <gecode/scheduling/unary/man-prop.hpp> 00834 #include <gecode/scheduling/unary/opt-prop.hpp> 00835 00836 #endif 00837 00838 // STATISTICS: scheduling-prop