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 * 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_UNARY_HH__ 00039 #define __GECODE_SCHEDULING_UNARY_HH__ 00040 00041 #include <gecode/scheduling/task.hh> 00042 00053 namespace Gecode { namespace Scheduling { namespace Unary { 00054 00056 class ManFixPTask { 00057 protected: 00059 Int::IntView _s; 00061 int _p; 00062 public: 00064 00065 00066 ManFixPTask(void); 00068 ManFixPTask(IntVar s, int p); 00070 void init(IntVar s, int p); 00072 void init(const ManFixPTask& t); 00074 00076 00077 00078 int est(void) const; 00080 int ect(void) const; 00082 int lst(void) const; 00084 int lct(void) const; 00086 int pmin(void) const; 00088 int pmax(void) const; 00090 IntVar st(void) const; 00092 bool mandatory(void) const; 00094 bool excluded(void) const; 00096 bool optional(void) const; 00098 00100 00101 00102 bool assigned(void) const; 00104 00106 00107 00108 ModEvent est(Space& home, int n); 00110 ModEvent ect(Space& home, int n); 00112 ModEvent lst(Space& home, int n); 00114 ModEvent lct(Space& home, int n); 00116 ModEvent norun(Space& home, int e, int l); 00118 ModEvent mandatory(Space& home); 00120 ModEvent excluded(Space& home); 00122 00124 00125 00126 void update(Space& home, bool share, ManFixPTask& t); 00128 00130 00131 00132 void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00134 void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00136 00137 }; 00138 00143 template<class Char, class Traits> 00144 std::basic_ostream<Char,Traits>& 00145 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t); 00146 00147 class ManFixPSETask : public ManFixPTask { 00148 protected: 00150 TaskType _t; 00151 public: 00153 00154 00155 ManFixPSETask(void); 00162 ManFixPSETask(TaskType t, IntVar s, int p); 00169 void init(TaskType t, IntVar s, int p); 00171 void init(const ManFixPSETask& t); 00173 00175 00176 00177 int est(void) const; 00179 int ect(void) const; 00181 int lst(void) const; 00183 int lct(void) const; 00185 int pmin(void) const; 00187 int pmax(void) const; 00189 00191 00192 00193 ModEvent est(Space& home, int n); 00195 ModEvent ect(Space& home, int n); 00197 ModEvent lst(Space& home, int n); 00199 ModEvent lct(Space& home, int n); 00201 ModEvent norun(Space& home, int e, int l); 00203 00205 00206 00207 void update(Space& home, bool share, ManFixPSETask& t); 00209 00210 }; 00211 00216 template<class Char, class Traits> 00217 std::basic_ostream<Char,Traits>& 00218 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t); 00219 00221 class OptFixPTask : public ManToOptTask<ManFixPTask> { 00222 protected: 00223 using ManToOptTask<ManFixPTask>::_m; 00224 public: 00226 00227 00228 OptFixPTask(void); 00230 OptFixPTask(IntVar s, int p, BoolVar m); 00232 void init(IntVar s, int p, BoolVar m); 00234 }; 00235 00240 template<class Char, class Traits> 00241 std::basic_ostream<Char,Traits>& 00242 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t); 00243 00245 class OptFixPSETask : public ManToOptTask<ManFixPSETask> { 00246 protected: 00247 using ManToOptTask<ManFixPSETask>::_m; 00248 public: 00250 00251 00252 OptFixPSETask(void); 00254 OptFixPSETask(TaskType t, IntVar s, int p, BoolVar m); 00256 void init(TaskType t, IntVar s, int p, BoolVar m); 00258 }; 00259 00264 template<class Char, class Traits> 00265 std::basic_ostream<Char,Traits>& 00266 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t); 00267 00269 class ManFlexTask { 00270 protected: 00272 Int::IntView _s; 00274 Int::IntView _p; 00276 Int::IntView _e; 00277 public: 00279 00280 00281 ManFlexTask(void); 00283 ManFlexTask(IntVar s, IntVar p, IntVar e); 00285 void init(IntVar s, IntVar p, IntVar e); 00287 void init(const ManFlexTask& t); 00289 00291 00292 00293 int est(void) const; 00295 int ect(void) const; 00297 int lst(void) const; 00299 int lct(void) const; 00301 int pmin(void) const; 00303 int pmax(void) const; 00305 IntVar st(void) const; 00307 IntVar p(void) const; 00309 IntVar e(void) const; 00311 bool mandatory(void) const; 00313 bool excluded(void) const; 00315 bool optional(void) const; 00317 00319 00320 00321 bool assigned(void) const; 00323 00325 00326 00327 ModEvent est(Space& home, int n); 00329 ModEvent ect(Space& home, int n); 00331 ModEvent lst(Space& home, int n); 00333 ModEvent lct(Space& home, int n); 00335 ModEvent norun(Space& home, int e, int l); 00337 ModEvent mandatory(Space& home); 00339 ModEvent excluded(Space& home); 00341 00343 00344 00345 void update(Space& home, bool share, ManFlexTask& t); 00347 00349 00350 00351 void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00353 void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND); 00355 00356 }; 00357 00362 template<class Char, class Traits> 00363 std::basic_ostream<Char,Traits>& 00364 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t); 00365 00367 class OptFlexTask : public ManToOptTask<ManFlexTask> { 00368 protected: 00369 using ManToOptTask<ManFlexTask>::_m; 00370 public: 00372 00373 00374 OptFlexTask(void); 00376 OptFlexTask(IntVar s, IntVar p, IntVar e, BoolVar m); 00378 void init(IntVar s, IntVar p, IntVar e, BoolVar m); 00380 }; 00381 00386 template<class Char, class Traits> 00387 std::basic_ostream<Char,Traits>& 00388 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t); 00389 00390 }}} 00391 00392 #include <gecode/scheduling/unary/task.hpp> 00393 00394 namespace Gecode { namespace Scheduling { namespace Unary { 00395 00397 typedef ManFixPTask ManFixPTaskFwd; 00398 00400 typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd; 00401 00403 typedef ManFixPSETask ManFixPSETaskFwd; 00404 00406 typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd; 00407 00409 typedef OptFixPTask OptFixPTaskFwd; 00410 00412 typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd; 00413 00415 typedef OptFixPSETask OptFixPSETaskFwd; 00416 00418 typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd; 00419 00421 typedef ManFlexTask ManFlexTaskFwd; 00422 00424 typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd; 00425 00427 typedef OptFlexTask OptFlexTaskFwd; 00428 00430 typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd; 00431 00432 00437 template<class Char, class Traits> 00438 std::basic_ostream<Char,Traits>& 00439 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t); 00440 00445 template<class Char, class Traits> 00446 std::basic_ostream<Char,Traits>& 00447 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t); 00448 00453 template<class Char, class Traits> 00454 std::basic_ostream<Char,Traits>& 00455 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t); 00456 00461 template<class Char, class Traits> 00462 std::basic_ostream<Char,Traits>& 00463 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t); 00464 00469 template<class Char, class Traits> 00470 std::basic_ostream<Char,Traits>& 00471 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTaskBwd& t); 00472 00479 template<class Char, class Traits> 00480 std::basic_ostream<Char,Traits>& 00481 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTaskBwd& t); 00482 00483 }}} 00484 00485 #include <gecode/scheduling/unary/task-view.hpp> 00486 00487 namespace Gecode { namespace Scheduling { 00488 00490 template<> 00491 class TaskViewTraits<Unary::ManFixPTaskFwd> { 00492 public: 00494 typedef Unary::ManFixPTask Task; 00495 }; 00496 00498 template<> 00499 class TaskViewTraits<Unary::ManFixPTaskBwd> { 00500 public: 00502 typedef Unary::ManFixPTask Task; 00503 }; 00504 00506 template<> 00507 class TaskViewTraits<Unary::ManFixPSETaskFwd> { 00508 public: 00510 typedef Unary::ManFixPSETask Task; 00511 }; 00512 00514 template<> 00515 class TaskViewTraits<Unary::ManFixPSETaskBwd> { 00516 public: 00518 typedef Unary::ManFixPSETask Task; 00519 }; 00520 00522 template<> 00523 class TaskViewTraits<Unary::OptFixPTaskFwd> { 00524 public: 00526 typedef Unary::OptFixPTask Task; 00527 }; 00528 00530 template<> 00531 class TaskViewTraits<Unary::OptFixPTaskBwd> { 00532 public: 00534 typedef Unary::OptFixPTask Task; 00535 }; 00536 00538 template<> 00539 class TaskViewTraits<Unary::OptFixPSETaskFwd> { 00540 public: 00542 typedef Unary::OptFixPSETask Task; 00543 }; 00544 00546 template<> 00547 class TaskViewTraits<Unary::OptFixPSETaskBwd> { 00548 public: 00550 typedef Unary::OptFixPSETask Task; 00551 }; 00552 00554 template<> 00555 class TaskViewTraits<Unary::ManFlexTaskFwd> { 00556 public: 00558 typedef Unary::ManFlexTask Task; 00559 }; 00560 00562 template<> 00563 class TaskViewTraits<Unary::ManFlexTaskBwd> { 00564 public: 00566 typedef Unary::ManFlexTask Task; 00567 }; 00568 00570 template<> 00571 class TaskViewTraits<Unary::OptFlexTaskFwd> { 00572 public: 00574 typedef Unary::OptFlexTask Task; 00575 }; 00576 00578 template<> 00579 class TaskViewTraits<Unary::OptFlexTaskBwd> { 00580 public: 00582 typedef Unary::OptFlexTask Task; 00583 }; 00584 00585 00587 template<> 00588 class TaskTraits<Unary::ManFixPTask> { 00589 public: 00591 typedef Unary::ManFixPTaskFwd TaskViewFwd; 00593 typedef Unary::ManFixPTaskBwd TaskViewBwd; 00594 }; 00595 00597 template<> 00598 class TaskTraits<Unary::ManFixPSETask> { 00599 public: 00601 typedef Unary::ManFixPSETaskFwd TaskViewFwd; 00603 typedef Unary::ManFixPSETaskBwd TaskViewBwd; 00604 }; 00605 00607 template<> 00608 class TaskTraits<Unary::OptFixPTask> { 00609 public: 00611 typedef Unary::OptFixPTaskFwd TaskViewFwd; 00613 typedef Unary::OptFixPTaskBwd TaskViewBwd; 00615 typedef Unary::ManFixPTask ManTask; 00616 }; 00617 00619 template<> 00620 class TaskTraits<Unary::OptFixPSETask> { 00621 public: 00623 typedef Unary::OptFixPSETaskFwd TaskViewFwd; 00625 typedef Unary::OptFixPSETaskBwd TaskViewBwd; 00627 typedef Unary::ManFixPTask ManTask; 00628 }; 00629 00631 template<> 00632 class TaskTraits<Unary::ManFlexTask> { 00633 public: 00635 typedef Unary::ManFlexTaskFwd TaskViewFwd; 00637 typedef Unary::ManFlexTaskBwd TaskViewBwd; 00638 }; 00639 00641 template<> 00642 class TaskTraits<Unary::OptFlexTask> { 00643 public: 00645 typedef Unary::OptFlexTaskFwd TaskViewFwd; 00647 typedef Unary::OptFlexTaskBwd TaskViewBwd; 00649 typedef Unary::ManFlexTask ManTask; 00650 }; 00651 00652 }} 00653 00654 namespace Gecode { namespace Scheduling { namespace Unary { 00655 00657 class OmegaNode { 00658 public: 00660 int p; 00662 int ect; 00664 void init(const OmegaNode& l, const OmegaNode& r); 00666 void update(const OmegaNode& l, const OmegaNode& r); 00667 }; 00668 00670 template<class TaskView> 00671 class OmegaTree : public TaskTree<TaskView,OmegaNode> { 00672 protected: 00673 using TaskTree<TaskView,OmegaNode>::tasks; 00674 using TaskTree<TaskView,OmegaNode>::leaf; 00675 using TaskTree<TaskView,OmegaNode>::root; 00676 using TaskTree<TaskView,OmegaNode>::init; 00677 using TaskTree<TaskView,OmegaNode>::update; 00678 public: 00680 OmegaTree(Region& r, const TaskViewArray<TaskView>& t); 00682 void insert(int i); 00684 void remove(int i); 00686 int ect(void) const; 00688 int ect(int i) const; 00689 }; 00690 00692 class OmegaLambdaNode : public OmegaNode { 00693 public: 00695 static const int undef = -1; 00697 int lp; 00699 int lect; 00701 int resEct; 00703 int resLp; 00705 void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r); 00707 void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r); 00708 }; 00709 00711 template<class TaskView> 00712 class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> { 00713 protected: 00714 using TaskTree<TaskView,OmegaLambdaNode>::tasks; 00715 using TaskTree<TaskView,OmegaLambdaNode>::leaf; 00716 using TaskTree<TaskView,OmegaLambdaNode>::root; 00717 using TaskTree<TaskView,OmegaLambdaNode>::init; 00718 using TaskTree<TaskView,OmegaLambdaNode>::update; 00719 public: 00721 OmegaLambdaTree(Region& r, const TaskViewArray<TaskView>& t, 00722 bool inc=true); 00724 void shift(int i); 00726 void oinsert(int i); 00728 void linsert(int i); 00730 void lremove(int i); 00732 bool lempty(void) const; 00734 int responsible(void) const; 00736 int ect(void) const; 00738 int lect(void) const; 00739 }; 00740 00741 }}} 00742 00743 #include <gecode/scheduling/unary/tree.hpp> 00744 00745 namespace Gecode { namespace Scheduling { namespace Unary { 00746 00748 template<class ManTask> 00749 ExecStatus overload(Space& home, TaskArray<ManTask>& t); 00751 template<class OptTask> 00752 ExecStatus overload(Space& home, Propagator& p, TaskArray<OptTask>& t); 00753 00755 template<class Task> 00756 ExecStatus subsumed(Space& home, Propagator& p, TaskArray<Task>& t); 00757 00759 template<class ManTask> 00760 ExecStatus detectable(Space& home, TaskArray<ManTask>& t); 00762 template<class OptTask> 00763 ExecStatus detectable(Space& home, Propagator& p, TaskArray<OptTask>& t); 00764 00766 template<class ManTask> 00767 ExecStatus notfirstnotlast(Space& home, TaskArray<ManTask>& t); 00769 template<class OptTask> 00770 ExecStatus notfirstnotlast(Space& home, Propagator& p, TaskArray<OptTask>& t); 00771 00773 template<class Task> 00774 ExecStatus edgefinding(Space& home, TaskArray<Task>& t); 00775 00776 00783 template<class ManTask> 00784 class ManProp : public TaskProp<ManTask,Int::PC_INT_BND> { 00785 protected: 00786 using TaskProp<ManTask,Int::PC_INT_BND>::t; 00788 ManProp(Home home, TaskArray<ManTask>& t); 00790 ManProp(Space& home, bool shared, ManProp& p); 00791 public: 00793 virtual Actor* copy(Space& home, bool share); 00795 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00797 static ExecStatus post(Home home, TaskArray<ManTask>& t); 00798 }; 00799 00806 template<class OptTask> 00807 class OptProp : public TaskProp<OptTask,Int::PC_INT_BND> { 00808 protected: 00809 using TaskProp<OptTask,Int::PC_INT_BND>::t; 00811 OptProp(Home home, TaskArray<OptTask>& t); 00813 OptProp(Space& home, bool shared, OptProp& p); 00814 public: 00816 virtual Actor* copy(Space& home, bool share); 00818 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00820 static ExecStatus post(Home home, TaskArray<OptTask>& t); 00821 }; 00822 00823 }}} 00824 00825 #include <gecode/scheduling/unary/overload.hpp> 00826 #include <gecode/scheduling/unary/subsumption.hpp> 00827 #include <gecode/scheduling/unary/detectable.hpp> 00828 #include <gecode/scheduling/unary/not-first-not-last.hpp> 00829 #include <gecode/scheduling/unary/edge-finding.hpp> 00830 00831 #include <gecode/scheduling/unary/man-prop.hpp> 00832 #include <gecode/scheduling/unary/opt-prop.hpp> 00833 00834 #endif 00835 00836 // STATISTICS: scheduling-prop