Generated on Sat Feb 12 2011 17:41:01 for Gecode by doxygen 1.7.3

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  *     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_CUMULATIVE_HH__
00041 #define __GECODE_SCHEDULING_CUMULATIVE_HH__
00042 
00043 #include <gecode/scheduling/task.hh>
00044 #include <gecode/scheduling/unary.hh>
00045 
00059 namespace Gecode { namespace Scheduling { namespace Cumulative {
00060 
00062   class ManFixPTask : public Unary::ManFixPTask {
00063   protected:
00065     int _c;
00066   public:
00068 
00069 
00070     ManFixPTask(void);
00072     ManFixPTask(IntVar s, int p, int c);
00074     void init(IntVar s, int p, int c);
00076     void init(const ManFixPTask& t);
00078 
00080 
00081 
00082     int c(void) const;
00084     double e(void) const;
00086 
00088 
00089 
00090     void update(Space& home, bool share, ManFixPTask& t);
00092 
00093   };
00094 
00099   template<class Char, class Traits>
00100   std::basic_ostream<Char,Traits>&
00101   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);
00102 
00104   class ManFixPSETask : public Unary::ManFixPSETask {
00105   protected:
00107     int _c;
00108   public:
00110 
00111 
00112     ManFixPSETask(void);
00120     ManFixPSETask(TaskType t, IntVar s, int p, int c);
00128     void init(TaskType t, IntVar s, int p, int c);
00130     void init(const ManFixPSETask& t);
00132 
00134 
00135 
00136     int c(void) const;
00138     double e(void) const;
00140 
00142 
00143 
00144     void update(Space& home, bool share, ManFixPSETask& t);
00146 
00147   };
00148 
00153   template<class Char, class Traits>
00154   std::basic_ostream<Char,Traits>&
00155   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);
00156 
00158   class ManFlexTask : public Unary::ManFlexTask {
00159   protected:
00161     int _c;
00162   public:
00164 
00165 
00166     ManFlexTask(void);
00168     ManFlexTask(IntVar s, IntVar p, IntVar e, int c);
00170     void init(IntVar s, IntVar p, IntVar e, int c);
00172     void init(const ManFlexTask& t);
00174 
00176 
00177 
00178     int c(void) const;
00180     double e(void) const;
00182 
00184 
00185 
00186     void update(Space& home, bool share, ManFlexTask& t);
00188 
00189   };
00190 
00195   template<class Char, class Traits>
00196   std::basic_ostream<Char,Traits>&
00197   operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);
00198 
00199 
00201   class OptFixPTask : public ManToOptTask<ManFixPTask> {
00202   protected:
00203     using ManToOptTask<ManFixPTask>::_m;
00204   public:
00206 
00207 
00208     OptFixPTask(void);
00210     OptFixPTask(IntVar s, int p, int c, BoolVar m);
00212     void init(IntVar s, int p, int c, BoolVar m);
00214   };
00215 
00220   template<class Char, class Traits>
00221   std::basic_ostream<Char,Traits>&
00222   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);
00223 
00225   class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
00226   protected:
00227     using ManToOptTask<ManFixPSETask>::_m;
00228   public:
00230 
00231 
00232     OptFixPSETask(void);
00234     OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m);
00236     void init(TaskType t, IntVar s, int p, int c, BoolVar m);
00238   };
00239 
00244   template<class Char, class Traits>
00245   std::basic_ostream<Char,Traits>&
00246   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);
00247 
00249   class OptFlexTask : public ManToOptTask<ManFlexTask> {
00250   protected:
00251     using ManToOptTask<ManFlexTask>::_m;
00252   public:
00254 
00255 
00256     OptFlexTask(void);
00258     OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
00260     void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
00262   };
00263 
00268   template<class Char, class Traits>
00269   std::basic_ostream<Char,Traits>&
00270   operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);
00271 
00272 }}}
00273 
00274 #include <gecode/scheduling/cumulative/task.hpp>
00275 
00276 namespace Gecode { namespace Scheduling { namespace Cumulative {
00277 
00279   typedef ManFixPTask ManFixPTaskFwd;
00280 
00282   typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd;
00283 
00285   typedef ManFixPSETask ManFixPSETaskFwd;
00286 
00288   typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd;
00289 
00291   typedef OptFixPTask OptFixPTaskFwd;
00292 
00294   typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd;
00295 
00297   typedef OptFixPSETask OptFixPSETaskFwd;
00298 
00300   typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd;
00301 
00303   typedef ManFlexTask ManFlexTaskFwd;
00304 
00306   typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd;
00307 
00309   typedef OptFlexTask OptFlexTaskFwd;
00310 
00312   typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd;
00313 
00314 
00319   template<class Char, class Traits>
00320   std::basic_ostream<Char,Traits>&
00321   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);
00322 
00327   template<class Char, class Traits>
00328   std::basic_ostream<Char,Traits>&
00329   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);
00330 
00335   template<class Char, class Traits>
00336   std::basic_ostream<Char,Traits>&
00337   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);
00338 
00343   template<class Char, class Traits>
00344   std::basic_ostream<Char,Traits>&
00345   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);
00346 
00347 }}}
00348 
00349 #include <gecode/scheduling/cumulative/task-view.hpp>
00350 
00351 namespace Gecode { namespace Scheduling {
00352 
00354   template<>
00355   class TaskViewTraits<Cumulative::ManFixPTaskFwd> {
00356   public:
00358     typedef Cumulative::ManFixPTask Task;
00359   };
00360 
00362   template<>
00363   class TaskViewTraits<Cumulative::ManFixPTaskBwd> {
00364   public:
00366     typedef Cumulative::ManFixPTask Task;
00367   };
00368 
00370   template<>
00371   class TaskViewTraits<Cumulative::ManFixPSETaskFwd> {
00372   public:
00374     typedef Cumulative::ManFixPSETask Task;
00375   };
00376 
00378   template<>
00379   class TaskViewTraits<Cumulative::ManFixPSETaskBwd> {
00380   public:
00382     typedef Cumulative::ManFixPSETask Task;
00383   };
00384 
00386   template<>
00387   class TaskViewTraits<Cumulative::OptFixPTaskFwd> {
00388   public:
00390     typedef Cumulative::OptFixPTask Task;
00391   };
00392 
00394   template<>
00395   class TaskViewTraits<Cumulative::OptFixPTaskBwd> {
00396   public:
00398     typedef Cumulative::OptFixPTask Task;
00399   };
00400 
00402   template<>
00403   class TaskViewTraits<Cumulative::OptFixPSETaskFwd> {
00404   public:
00406     typedef Cumulative::OptFixPSETask Task;
00407   };
00408 
00410   template<>
00411   class TaskViewTraits<Cumulative::OptFixPSETaskBwd> {
00412   public:
00414     typedef Cumulative::OptFixPSETask Task;
00415   };
00416 
00418   template<>
00419   class TaskViewTraits<Cumulative::ManFlexTaskFwd> {
00420   public:
00422     typedef Cumulative::ManFlexTask Task;
00423   };
00424 
00426   template<>
00427   class TaskViewTraits<Cumulative::ManFlexTaskBwd> {
00428   public:
00430     typedef Cumulative::ManFlexTask Task;
00431   };
00432 
00434   template<>
00435   class TaskViewTraits<Cumulative::OptFlexTaskFwd> {
00436   public:
00438     typedef Cumulative::OptFlexTask Task;
00439   };
00440 
00442   template<>
00443   class TaskViewTraits<Cumulative::OptFlexTaskBwd> {
00444   public:
00446     typedef Cumulative::OptFlexTask Task;
00447   };
00448 
00449 
00451   template<>
00452   class TaskTraits<Cumulative::ManFixPTask> {
00453   public:
00455     typedef Cumulative::ManFixPTaskFwd TaskViewFwd;
00457     typedef Cumulative::ManFixPTaskBwd TaskViewBwd;
00458   };
00459 
00461   template<>
00462   class TaskTraits<Cumulative::ManFixPSETask> {
00463   public:
00465     typedef Cumulative::ManFixPSETaskFwd TaskViewFwd;
00467     typedef Cumulative::ManFixPSETaskBwd TaskViewBwd;
00468   };
00469 
00471   template<>
00472   class TaskTraits<Cumulative::OptFixPTask> {
00473   public:
00475     typedef Cumulative::OptFixPTaskFwd TaskViewFwd;
00477     typedef Cumulative::OptFixPTaskBwd TaskViewBwd;
00479     typedef Cumulative::ManFixPTask ManTask;
00480   };
00481 
00483   template<>
00484   class TaskTraits<Cumulative::OptFixPSETask> {
00485   public:
00487     typedef Cumulative::OptFixPSETaskFwd TaskViewFwd;
00489     typedef Cumulative::OptFixPSETaskBwd TaskViewBwd;
00491     typedef Cumulative::ManFixPSETask ManTask;
00492   };
00493 
00495   template<>
00496   class TaskTraits<Cumulative::ManFlexTask> {
00497   public:
00499     typedef Cumulative::ManFlexTaskFwd TaskViewFwd;
00501     typedef Cumulative::ManFlexTaskBwd TaskViewBwd;
00502   };
00503 
00505   template<>
00506   class TaskTraits<Cumulative::OptFlexTask> {
00507   public:
00509     typedef Cumulative::OptFlexTaskFwd TaskViewFwd;
00511     typedef Cumulative::OptFlexTaskBwd TaskViewBwd;
00513     typedef Cumulative::ManFlexTask ManTask;
00514   };
00515 
00516 }}
00517 
00518 namespace Gecode { namespace Scheduling { namespace Cumulative {
00519 
00521   class OmegaNode {
00522   public:
00524     double e;
00526     double env;
00528     void init(const OmegaNode& l, const OmegaNode& r);
00530     void update(const OmegaNode& l, const OmegaNode& r);
00531   };
00532 
00534   template<class TaskView>
00535   class OmegaTree : public TaskTree<TaskView,OmegaNode> {
00536   protected:
00537     using TaskTree<TaskView,OmegaNode>::tasks;
00538     using TaskTree<TaskView,OmegaNode>::leaf;
00539     using TaskTree<TaskView,OmegaNode>::root;
00540     using TaskTree<TaskView,OmegaNode>::init;
00541     using TaskTree<TaskView,OmegaNode>::update;
00543     int c;
00544   public:
00546     OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
00548     void insert(int i);
00550     void remove(int i);
00552     double env(void) const;
00553   };
00554 
00556   class ExtOmegaNode : public OmegaNode {
00557   public:
00559     double cenv;
00561     void init(const ExtOmegaNode& l, const ExtOmegaNode& r);
00563     void update(const ExtOmegaNode& l, const ExtOmegaNode& r);
00564   };
00565 
00567   template<class TaskView>
00568   class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> {
00569   protected:
00570     using TaskTree<TaskView,ExtOmegaNode>::tasks;
00571     using TaskTree<TaskView,ExtOmegaNode>::leaf;
00572     using TaskTree<TaskView,ExtOmegaNode>::root;
00573     using TaskTree<TaskView,ExtOmegaNode>::init;
00574     using TaskTree<TaskView,ExtOmegaNode>::update;
00575     using TaskTree<TaskView,ExtOmegaNode>::node;
00576     using TaskTree<TaskView,ExtOmegaNode>::n_leaf;
00577     using TaskTree<TaskView,ExtOmegaNode>::n_left;
00578     using TaskTree<TaskView,ExtOmegaNode>::left;
00579     using TaskTree<TaskView,ExtOmegaNode>::n_right;
00580     using TaskTree<TaskView,ExtOmegaNode>::right;
00581     using TaskTree<TaskView,ExtOmegaNode>::n_root;
00582     using TaskTree<TaskView,ExtOmegaNode>::n_parent;
00583     using TaskTree<TaskView,ExtOmegaNode>::n_nodes;
00584     using TaskTree<TaskView,ExtOmegaNode>::_leaf;
00586     int c, ci;
00587   public:
00589     template<class Node>
00590     ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t);
00592     void init(int ci);
00594     double env(int i);
00595   };
00596 
00597 
00599   class OmegaLambdaNode : public OmegaNode {
00600   public:
00602     static const int undef = -1;
00604     double le;
00606     double lenv;
00608     int resLe;
00610     int resLenv;
00612     void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
00614     void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
00615   };
00616 
00618   template<class TaskView>
00619   class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
00620   protected:
00621     using TaskTree<TaskView,OmegaLambdaNode>::tasks;
00622     using TaskTree<TaskView,OmegaLambdaNode>::leaf;
00623     using TaskTree<TaskView,OmegaLambdaNode>::root;
00624     using TaskTree<TaskView,OmegaLambdaNode>::init;
00625     using TaskTree<TaskView,OmegaLambdaNode>::update;
00627     int c;
00628   public:
00630     OmegaLambdaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
00632     void shift(int i);
00634     void lremove(int i);
00636     bool lempty(void) const;
00638     int responsible(void) const;
00640     double env(void) const;
00642     double lenv(void) const;
00643   };
00644 
00645 }}}
00646 
00647 #include <gecode/scheduling/cumulative/tree.hpp>
00648 
00649 namespace Gecode { namespace Scheduling { namespace Cumulative {
00650 
00652   template<class Task>
00653   ExecStatus basic(Space& home, Propagator& p, int c, TaskArray<Task>& t);
00654 
00656   template<class ManTask>
00657   ExecStatus overload(Space& home, int c, TaskArray<ManTask>& t);
00658 
00660   template<class Task>
00661   ExecStatus edgefinding(Space& home, int c, TaskArray<Task>& t);
00662 
00669   template<class ManTask>
00670   class ManProp : public TaskProp<ManTask,Int::PC_INT_DOM> {
00671   protected:
00672     using TaskProp<ManTask,Int::PC_INT_DOM>::t;
00674     int c;
00676     ManProp(Home home, int c, TaskArray<ManTask>& t);
00678     ManProp(Space& home, bool shared, ManProp& p);
00679   public:
00681     virtual Actor* copy(Space& home, bool share);
00683     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00685     static ExecStatus post(Home home, int c, TaskArray<ManTask>& t);
00687     virtual size_t dispose(Space& home);
00688   };
00689 
00696   template<class OptTask>
00697   class OptProp : public TaskProp<OptTask,Int::PC_INT_DOM> {
00698   protected:
00699     using TaskProp<OptTask,Int::PC_INT_DOM>::t;
00701     int c;
00703     OptProp(Home home, int c, TaskArray<OptTask>& t);
00705     OptProp(Space& home, bool shared, OptProp& p);
00706   public:
00708     virtual Actor* copy(Space& home, bool share);
00710     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00712     static ExecStatus post(Home home, int c, TaskArray<OptTask>& t);
00714     virtual size_t dispose(Space& home);
00715   };
00716 
00717 }}}
00718 
00719 #include <gecode/scheduling/cumulative/basic.hpp>
00720 #include <gecode/scheduling/cumulative/overload.hpp>
00721 #include <gecode/scheduling/cumulative/edge-finding.hpp>
00722 #include <gecode/scheduling/cumulative/man-prop.hpp>
00723 #include <gecode/scheduling/cumulative/opt-prop.hpp>
00724 
00725 #endif
00726 
00727 // STATISTICS: scheduling-prop