Generated on Mon May 10 06:46:43 2010 for Gecode by doxygen 1.6.3

task.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-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
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_TASK_HH__
00039 #define __GECODE_SCHEDULING_TASK_HH__
00040 
00041 #include <gecode/scheduling.hh>
00042 
00043 namespace Gecode { namespace Scheduling {
00044 
00046   template<class ManTask>
00047   class ManToOptTask : public ManTask {
00048   protected:
00050     Int::BoolView _m;
00051   public:
00053 
00054 
00055     ManToOptTask(void);
00057 
00059 
00060 
00061     bool mandatory(void) const;
00063     bool excluded(void) const;
00065     bool optional(void) const;
00067 
00069 
00070     bool assigned(void) const;
00072 
00074 
00075 
00076     ModEvent mandatory(Space& home);
00078     ModEvent excluded(Space& home);
00080 
00082 
00083 
00084     void update(Space& home, bool share, ManToOptTask& t);
00086 
00088 
00089 
00090     void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
00092     void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
00094   };
00095 
00096 }}
00097 
00098 #include <gecode/scheduling/task/man-to-opt.hpp>
00099 
00100 namespace Gecode { namespace Scheduling {
00101 
00103   template<class TaskView>
00104   class FwdToBwd : public TaskView {
00105   public:
00107 
00108 
00109     int est(void) const;
00111     int ect(void) const;
00113     int lst(void) const;
00115     int lct(void) const;
00117 
00119 
00120 
00121     ModEvent est(Space& home, int n);
00123     ModEvent ect(Space& home, int n);
00125     ModEvent lst(Space& home, int n);
00127     ModEvent lct(Space& home, int n);
00129     ModEvent norun(Space& home, int e, int l);
00131   };
00132 
00133 }}
00134 
00135 #include <gecode/scheduling/task/fwd-to-bwd.hpp>
00136 
00137 namespace Gecode { namespace Scheduling {
00138 
00145   template<class TaskView>
00146   class TaskViewTraits {};
00147 
00154   template<class Task>
00155   class TaskTraits {};
00156 
00157 }}
00158 
00159 namespace Gecode { namespace Scheduling {
00160 
00162   template<class Task>
00163   class TaskArray {
00164   private:
00166     int n;
00168     Task* t;
00169   public:
00171 
00172 
00173     TaskArray(void);
00175     TaskArray(Space& home, int n);
00177     TaskArray(const TaskArray<Task>& a);
00179     const TaskArray<Task>& operator =(const TaskArray<Task>& a);
00181 
00183 
00184 
00185     int size(void) const;
00187     void size(int n);
00189 
00191 
00192 
00193     Task& operator [](int i);
00195     const Task& operator [](int i) const;
00197 
00199 
00200 
00201     void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
00203     void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
00205 
00207 
00208 
00209     void update(Space&, bool share, TaskArray& a);
00211 
00212   private:
00213     static void* operator new(size_t);
00214     static void  operator delete(void*,size_t);
00215   };
00216 
00221   template<class Char, class Traits, class Task>
00222   std::basic_ostream<Char,Traits>&
00223   operator <<(std::basic_ostream<Char,Traits>& os, 
00224               const TaskArray<Task>& t);
00225 
00226 
00228   template<class TaskView>
00229   class TaskViewArray {
00230   protected:
00232     typedef typename TaskViewTraits<TaskView>::Task Task;
00234     TaskArray<Task>& t;
00235   public:
00237 
00238 
00239     TaskViewArray(TaskArray<Task>& t);
00241 
00243 
00244 
00245     int size(void) const;
00247     void size(int n);
00249 
00251 
00252 
00253     TaskView& operator [](int i);
00255     const TaskView& operator [](int i) const;
00257   private:
00258     static void* operator new(size_t);
00259     static void  operator delete(void*,size_t);
00260   };
00261 
00266   template<class Char, class Traits, class TaskView>
00267   std::basic_ostream<Char,Traits>&
00268   operator <<(std::basic_ostream<Char,Traits>& os, 
00269               const TaskViewArray<TaskView>& t);
00270 
00271 }}
00272 
00273 #include <gecode/scheduling/task/array.hpp>
00274 
00275 namespace Gecode { namespace Scheduling {
00276 
00278   enum SortTaskOrder {
00279     STO_EST, 
00280     STO_ECT, 
00281     STO_LST, 
00282     STO_LCT  
00283   };
00284 
00286   template<class TaskView, SortTaskOrder sto, bool inc>
00287   void sort(TaskViewArray<TaskView>& t);
00288 
00290   template<class TaskView, SortTaskOrder sto, bool inc>
00291   void sort(int* map, const TaskViewArray<TaskView>& t);
00292 
00294   template<class TaskView, SortTaskOrder sto, bool inc>
00295   void sort(int* map, int n, const TaskViewArray<TaskView>& t);
00296 
00297 }}
00298 
00299 #include <gecode/scheduling/task/sort.hpp>
00300 
00301 namespace Gecode { namespace Scheduling {
00302 
00304   template<class TaskView, SortTaskOrder sto, bool inc>
00305   class TaskViewIter {
00306   protected:
00308     int* map;
00310     int i;
00312     TaskViewIter(void);
00313   public:
00315     TaskViewIter(Region& r, const TaskViewArray<TaskView>& t);
00317 
00318 
00319     bool operator ()(void) const;
00321     int left(void) const;
00323     void operator ++(void);
00325 
00327 
00328 
00329     int task(void) const;
00331   };
00332 
00334   template<class OptTaskView, SortTaskOrder sto, bool inc>
00335   class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
00336   protected:
00337     using TaskViewIter<OptTaskView,sto,inc>::map;
00338     using TaskViewIter<OptTaskView,sto,inc>::i;
00339   public:
00341     ManTaskViewIter(Region& r, const TaskViewArray<OptTaskView>& t);
00342   };
00343 
00344 }}
00345 
00346 #include <gecode/scheduling/task/iter.hpp>
00347 
00348 namespace Gecode { namespace Scheduling {
00349 
00351   int plus(int x, int y);
00352 
00354   template<class TaskView, class Node>
00355   class TaskTree {
00356   protected:
00358     const TaskViewArray<TaskView>& tasks;
00360     Node* node;
00362     int* _leaf;
00363 
00365     int n_inner(void) const;
00367     int n_nodes(void) const;
00369     static bool n_root(int i);
00371     bool n_leaf(int i) const;
00373     static int n_left(int i);
00375     static bool left(int i);
00377     static int n_right(int i);
00379     static bool right(int i);
00381     static int n_parent(int i);
00382   protected:
00384     Node& leaf(int i);
00386     const Node& root(void) const;
00388     void update(int i, bool l=true);
00390     void init(void);
00392     TaskTree(Region& r, const TaskViewArray<TaskView>& t);
00393   };
00394 
00395 }}
00396 
00397 #include <gecode/scheduling/task/tree.hpp>
00398 
00399 namespace Gecode { namespace Scheduling {
00400 
00407   template<class Task>
00408   class TaskProp : public Propagator {
00409   protected:
00411     TaskArray<Task> t;
00413     TaskProp(Home home, TaskArray<Task>& t, PropCond pc=Int::PC_INT_BND);
00415     TaskProp(Space& home, bool shared, TaskProp<Task>& p);
00416   public:
00418     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00420     size_t dispose(Space& home, PropCond pc);
00422     virtual size_t dispose(Space& home);
00423   };
00424 
00426   template<class OptTask>
00427   ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t);
00428 
00429 }}
00430 
00431 #include <gecode/scheduling/task/prop.hpp>
00432 #include <gecode/scheduling/task/purge.hpp>
00433 
00434 #endif
00435 
00436 // STATISTICS: scheduling-prop