Generated on Fri May 13 2011 22:41:21 for Gecode by doxygen 1.7.1

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