Generated on Thu Apr 11 13:59:06 2019 for Gecode by doxygen 1.6.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  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #ifndef __GECODE_INT_CUMULATIVE_HH__
00037 #define __GECODE_INT_CUMULATIVE_HH__
00038 
00039 #include <gecode/int/task.hh>
00040 #include <gecode/int/unary.hh>
00041 
00055 namespace Gecode { namespace Int { namespace Cumulative {
00056 
00058   void mul_check(long long int x, long long int y);
00059 
00061   void mul_check(long long int x, long long int y, long long int z);
00062 
00063 }}}
00064 
00065 #include <gecode/int/cumulative/limits.hpp>
00066 
00067 namespace Gecode { namespace Int { namespace Cumulative {
00068 
00070   class ManFixPTask : public Unary::ManFixPTask {
00071   protected:
00073     int _c;
00074   public:
00076 
00077 
00078     ManFixPTask(void);
00080     ManFixPTask(IntVar s, int p, int c);
00082     void init(IntVar s, int p, int c);
00084     void init(const ManFixPTask& t);
00086 
00088 
00089 
00090     int c(void) const;
00092     long long int e(void) const;
00094 
00096 
00097 
00098     void update(Space& home, ManFixPTask& t);
00100 
00101   };
00102 
00107   template<class Char, class Traits>
00108   std::basic_ostream<Char,Traits>&
00109   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);
00110 
00112   class ManFixPSETask : public Unary::ManFixPSETask {
00113   protected:
00115     int _c;
00116   public:
00118 
00119 
00120     ManFixPSETask(void);
00128     ManFixPSETask(TaskType t, IntVar s, int p, int c);
00136     void init(TaskType t, IntVar s, int p, int c);
00138     void init(const ManFixPSETask& t);
00140 
00142 
00143 
00144     int c(void) const;
00146     long long int e(void) const;
00148 
00150 
00151 
00152     void update(Space& home, ManFixPSETask& t);
00154 
00155   };
00156 
00161   template<class Char, class Traits>
00162   std::basic_ostream<Char,Traits>&
00163   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);
00164 
00166   class ManFlexTask : public Unary::ManFlexTask {
00167   protected:
00169     int _c;
00170   public:
00172 
00173 
00174     ManFlexTask(void);
00176     ManFlexTask(IntVar s, IntVar p, IntVar e, int c);
00178     void init(IntVar s, IntVar p, IntVar e, int c);
00180     void init(const ManFlexTask& t);
00182 
00184 
00185 
00186     int c(void) const;
00188     long long int e(void) const;
00190 
00192 
00193 
00194     void update(Space& home, ManFlexTask& t);
00196 
00197   };
00198 
00203   template<class Char, class Traits>
00204   std::basic_ostream<Char,Traits>&
00205   operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);
00206 
00207 
00209   class OptFixPTask : public ManToOptTask<ManFixPTask> {
00210   protected:
00211     using ManToOptTask<ManFixPTask>::_m;
00212   public:
00214 
00215 
00216     OptFixPTask(void);
00218     OptFixPTask(IntVar s, int p, int c, BoolVar m);
00220     void init(IntVar s, int p, int c, BoolVar m);
00222 
00223     operator Unary::OptFixPTask (void);
00224   };
00225 
00230   template<class Char, class Traits>
00231   std::basic_ostream<Char,Traits>&
00232   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);
00233 
00235   class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
00236   protected:
00237     using ManToOptTask<ManFixPSETask>::_m;
00238   public:
00240 
00241 
00242     OptFixPSETask(void);
00244     OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m);
00246     void init(TaskType t, IntVar s, int p, int c, BoolVar m);
00248 
00249     operator Unary::OptFixPSETask (void);
00250   };
00251 
00256   template<class Char, class Traits>
00257   std::basic_ostream<Char,Traits>&
00258   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);
00259 
00261   class OptFlexTask : public ManToOptTask<ManFlexTask> {
00262   protected:
00263     using ManToOptTask<ManFlexTask>::_m;
00264   public:
00266 
00267 
00268     OptFlexTask(void);
00270     OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
00272     void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
00274 
00275     operator Unary::OptFlexTask (void);
00276   };
00277 
00282   template<class Char, class Traits>
00283   std::basic_ostream<Char,Traits>&
00284   operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);
00285 
00286 }}}
00287 
00288 #include <gecode/int/cumulative/task.hpp>
00289 
00290 namespace Gecode { namespace Int { namespace Cumulative {
00291 
00293   typedef ManFixPTask ManFixPTaskFwd;
00294 
00296   typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd;
00297 
00299   typedef ManFixPSETask ManFixPSETaskFwd;
00300 
00302   typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd;
00303 
00305   typedef OptFixPTask OptFixPTaskFwd;
00306 
00308   typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd;
00309 
00311   typedef OptFixPSETask OptFixPSETaskFwd;
00312 
00314   typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd;
00315 
00317   typedef ManFlexTask ManFlexTaskFwd;
00318 
00320   typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd;
00321 
00323   typedef OptFlexTask OptFlexTaskFwd;
00324 
00326   typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd;
00327 
00328 
00333   template<class Char, class Traits>
00334   std::basic_ostream<Char,Traits>&
00335   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);
00336 
00341   template<class Char, class Traits>
00342   std::basic_ostream<Char,Traits>&
00343   operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);
00344 
00349   template<class Char, class Traits>
00350   std::basic_ostream<Char,Traits>&
00351   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);
00352 
00357   template<class Char, class Traits>
00358   std::basic_ostream<Char,Traits>&
00359   operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);
00360 
00361 }}}
00362 
00363 #include <gecode/int/cumulative/task-view.hpp>
00364 
00365 namespace Gecode { namespace Int {
00366 
00368   template<>
00369   class TaskViewTraits<Cumulative::ManFixPTaskFwd> {
00370   public:
00372     typedef Cumulative::ManFixPTask Task;
00373   };
00374 
00376   template<>
00377   class TaskViewTraits<Cumulative::ManFixPTaskBwd> {
00378   public:
00380     typedef Cumulative::ManFixPTask Task;
00381   };
00382 
00384   template<>
00385   class TaskViewTraits<Cumulative::ManFixPSETaskFwd> {
00386   public:
00388     typedef Cumulative::ManFixPSETask Task;
00389   };
00390 
00392   template<>
00393   class TaskViewTraits<Cumulative::ManFixPSETaskBwd> {
00394   public:
00396     typedef Cumulative::ManFixPSETask Task;
00397   };
00398 
00400   template<>
00401   class TaskViewTraits<Cumulative::OptFixPTaskFwd> {
00402   public:
00404     typedef Cumulative::OptFixPTask Task;
00405   };
00406 
00408   template<>
00409   class TaskViewTraits<Cumulative::OptFixPTaskBwd> {
00410   public:
00412     typedef Cumulative::OptFixPTask Task;
00413   };
00414 
00416   template<>
00417   class TaskViewTraits<Cumulative::OptFixPSETaskFwd> {
00418   public:
00420     typedef Cumulative::OptFixPSETask Task;
00421   };
00422 
00424   template<>
00425   class TaskViewTraits<Cumulative::OptFixPSETaskBwd> {
00426   public:
00428     typedef Cumulative::OptFixPSETask Task;
00429   };
00430 
00432   template<>
00433   class TaskViewTraits<Cumulative::ManFlexTaskFwd> {
00434   public:
00436     typedef Cumulative::ManFlexTask Task;
00437   };
00438 
00440   template<>
00441   class TaskViewTraits<Cumulative::ManFlexTaskBwd> {
00442   public:
00444     typedef Cumulative::ManFlexTask Task;
00445   };
00446 
00448   template<>
00449   class TaskViewTraits<Cumulative::OptFlexTaskFwd> {
00450   public:
00452     typedef Cumulative::OptFlexTask Task;
00453   };
00454 
00456   template<>
00457   class TaskViewTraits<Cumulative::OptFlexTaskBwd> {
00458   public:
00460     typedef Cumulative::OptFlexTask Task;
00461   };
00462 
00463 
00465   template<>
00466   class TaskTraits<Cumulative::ManFixPTask> {
00467   public:
00469     typedef Cumulative::ManFixPTaskFwd TaskViewFwd;
00471     typedef Cumulative::ManFixPTaskBwd TaskViewBwd;
00473     typedef Unary::ManFixPTask UnaryTask;
00474   };
00475 
00477   template<>
00478   class TaskTraits<Cumulative::ManFixPSETask> {
00479   public:
00481     typedef Cumulative::ManFixPSETaskFwd TaskViewFwd;
00483     typedef Cumulative::ManFixPSETaskBwd TaskViewBwd;
00485     typedef Unary::ManFixPSETask UnaryTask;
00486   };
00487 
00489   template<>
00490   class TaskTraits<Cumulative::OptFixPTask> {
00491   public:
00493     typedef Cumulative::OptFixPTaskFwd TaskViewFwd;
00495     typedef Cumulative::OptFixPTaskBwd TaskViewBwd;
00497     typedef Cumulative::ManFixPTask ManTask;
00499     typedef Unary::OptFixPTask UnaryTask;
00500   };
00501 
00503   template<>
00504   class TaskTraits<Cumulative::OptFixPSETask> {
00505   public:
00507     typedef Cumulative::OptFixPSETaskFwd TaskViewFwd;
00509     typedef Cumulative::OptFixPSETaskBwd TaskViewBwd;
00511     typedef Cumulative::ManFixPSETask ManTask;
00513     typedef Unary::OptFixPSETask UnaryTask;
00514   };
00515 
00517   template<>
00518   class TaskTraits<Cumulative::ManFlexTask> {
00519   public:
00521     typedef Cumulative::ManFlexTaskFwd TaskViewFwd;
00523     typedef Cumulative::ManFlexTaskBwd TaskViewBwd;
00525     typedef Unary::ManFlexTask UnaryTask;
00526   };
00527 
00529   template<>
00530   class TaskTraits<Cumulative::OptFlexTask> {
00531   public:
00533     typedef Cumulative::OptFlexTaskFwd TaskViewFwd;
00535     typedef Cumulative::OptFlexTaskBwd TaskViewBwd;
00537     typedef Cumulative::ManFlexTask ManTask;
00539     typedef Unary::OptFlexTask UnaryTask;
00540   };
00541 
00542 }}
00543 
00544 namespace Gecode { namespace Int { namespace Cumulative {
00545 
00547   class OmegaNode {
00548   public:
00550     long long int e;
00552     long long int env;
00554     void init(const OmegaNode& l, const OmegaNode& r);
00556     void update(const OmegaNode& l, const OmegaNode& r);
00557   };
00558 
00560   template<class TaskView>
00561   class OmegaTree : public TaskTree<TaskView,OmegaNode> {
00562   protected:
00563     using TaskTree<TaskView,OmegaNode>::tasks;
00564     using TaskTree<TaskView,OmegaNode>::leaf;
00565     using TaskTree<TaskView,OmegaNode>::root;
00566     using TaskTree<TaskView,OmegaNode>::init;
00567     using TaskTree<TaskView,OmegaNode>::update;
00569     int c;
00570   public:
00572     OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
00574     void insert(int i);
00576     void remove(int i);
00578     long long int env(void) const;
00579   };
00580 
00582   class ExtOmegaNode : public OmegaNode {
00583   public:
00585     long long int cenv;
00587     void init(const ExtOmegaNode& l, const ExtOmegaNode& r);
00589     void update(const ExtOmegaNode& l, const ExtOmegaNode& r);
00590   };
00591 
00593   template<class TaskView>
00594   class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> {
00595   protected:
00596     using TaskTree<TaskView,ExtOmegaNode>::tasks;
00597     using TaskTree<TaskView,ExtOmegaNode>::leaf;
00598     using TaskTree<TaskView,ExtOmegaNode>::root;
00599     using TaskTree<TaskView,ExtOmegaNode>::init;
00600     using TaskTree<TaskView,ExtOmegaNode>::update;
00601     using TaskTree<TaskView,ExtOmegaNode>::node;
00602     using TaskTree<TaskView,ExtOmegaNode>::n_leaf;
00603     using TaskTree<TaskView,ExtOmegaNode>::n_left;
00604     using TaskTree<TaskView,ExtOmegaNode>::left;
00605     using TaskTree<TaskView,ExtOmegaNode>::n_right;
00606     using TaskTree<TaskView,ExtOmegaNode>::right;
00607     using TaskTree<TaskView,ExtOmegaNode>::n_root;
00608     using TaskTree<TaskView,ExtOmegaNode>::n_parent;
00609     using TaskTree<TaskView,ExtOmegaNode>::n_nodes;
00610     using TaskTree<TaskView,ExtOmegaNode>::_leaf;
00612     int c, ci;
00613   public:
00615     template<class Node>
00616     ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t);
00618     void init(int ci);
00620     long long int env(int i);
00621   };
00622 
00623 
00625   class OmegaLambdaNode : public OmegaNode {
00626   public:
00628     static const int undef = -1;
00630     long long int le;
00632     long long int lenv;
00634     int resLe;
00636     int resLenv;
00638     void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
00640     void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
00641   };
00642 
00644   template<class TaskView>
00645   class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
00646   protected:
00647     using TaskTree<TaskView,OmegaLambdaNode>::tasks;
00648     using TaskTree<TaskView,OmegaLambdaNode>::leaf;
00649     using TaskTree<TaskView,OmegaLambdaNode>::root;
00650     using TaskTree<TaskView,OmegaLambdaNode>::init;
00651     using TaskTree<TaskView,OmegaLambdaNode>::update;
00653     int c;
00654   public:
00656     OmegaLambdaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
00658     void shift(int i);
00660     void lremove(int i);
00662     bool lempty(void) const;
00664     int responsible(void) const;
00666     long long int env(void) const;
00668     long long int lenv(void) const;
00669   };
00670 
00671 }}}
00672 
00673 #include <gecode/int/cumulative/tree.hpp>
00674 
00675 namespace Gecode { namespace Int { namespace Cumulative {
00676 
00678   template<class Task>
00679   ExecStatus
00680   subsumed(Space& home, Propagator& p, int c, TaskArray<Task>& t);
00681 
00683   template<class ManTask>
00684   ExecStatus overload(Space& home, int c, TaskArray<ManTask>& t);
00685 
00687   template<class Task, class Cap>
00688   ExecStatus timetabling(Space& home, Propagator& p, Cap c,
00689                          TaskArray<Task>& t);
00690 
00692   template<class Task>
00693   ExecStatus edgefinding(Space& home, int c, TaskArray<Task>& t);
00694 
00701   template<class ManTask, class Cap, class PL>
00702   class ManProp : public TaskProp<ManTask,PL> {
00703   protected:
00704     using TaskProp<ManTask,PL>::t;
00706     Cap c;
00708     ManProp(Home home, Cap c, TaskArray<ManTask>& t);
00710     ManProp(Space& home, ManProp& p);
00711   public:
00713     virtual Actor* copy(Space& home);
00715     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00717     static ExecStatus post(Home home, Cap c, TaskArray<ManTask>& t);
00719     virtual size_t dispose(Space& home);
00720   };
00721 
00728   template<class OptTask, class Cap, class PL>
00729   class OptProp : public TaskProp<OptTask,PL> {
00730   protected:
00731     using TaskProp<OptTask,PL>::t;
00733     Cap c;
00735     OptProp(Home home, Cap c, TaskArray<OptTask>& t);
00737     OptProp(Space& home, OptProp& p);
00738   public:
00740     virtual Actor* copy(Space& home);
00742     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00744     static ExecStatus post(Home home, Cap c, TaskArray<OptTask>& t);
00746     virtual size_t dispose(Space& home);
00747   };
00748 
00750   template<class ManTask, class Cap>
00751   ExecStatus
00752   cmanpost(Home home, Cap c, TaskArray<ManTask>& t, IntPropLevel ipl);
00753 
00755   template<class OptTask, class Cap>
00756   ExecStatus
00757   coptpost(Home home, Cap c, TaskArray<OptTask>& t, IntPropLevel ipl);
00758 
00759 }}}
00760 
00761 #include <gecode/int/cumulative/time-tabling.hpp>
00762 #include <gecode/int/cumulative/subsumption.hpp>
00763 #include <gecode/int/cumulative/overload.hpp>
00764 #include <gecode/int/cumulative/edge-finding.hpp>
00765 #include <gecode/int/cumulative/man-prop.hpp>
00766 #include <gecode/int/cumulative/opt-prop.hpp>
00767 #include <gecode/int/cumulative/post.hpp>
00768 
00769 #endif
00770 
00771 // STATISTICS: int-prop