Generated on Tue Jul 27 2010 21:59:17 for Gecode by doxygen 1.7.1

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