Generated on Mon Nov 30 23:53:34 2009 for Gecode by doxygen 1.6.1

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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9878 $
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);
00092     void cancel(Space& home, Propagator& p);
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   };
00130 
00131 }}
00132 
00133 #include <gecode/scheduling/task/fwd-to-bwd.hpp>
00134 
00135 namespace Gecode { namespace Scheduling {
00136 
00143   template<class TaskView>
00144   class TaskViewTraits {};
00145 
00152   template<class Task>
00153   class TaskTraits {};
00154 
00155 }}
00156 
00157 namespace Gecode { namespace Scheduling {
00158 
00160   template<class Task>
00161   class TaskArray {
00162   private:
00164     int n;
00166     Task* t;
00167   public:
00169 
00170 
00171     TaskArray(void);
00173     TaskArray(Space& home, int n);
00175     TaskArray(const TaskArray<Task>& a);
00177     const TaskArray<Task>& operator =(const TaskArray<Task>& a);
00179 
00181 
00182 
00183     int size(void) const;
00185     void size(int n);
00187 
00189 
00190 
00191     Task& operator [](int i);
00193     const Task& operator [](int i) const;
00195 
00197 
00198 
00199     void subscribe(Space& home, Propagator& p);
00201     void cancel(Space& home, Propagator& p);
00203 
00205 
00206 
00207     void update(Space&, bool share, TaskArray& a);
00209 
00210   private:
00211     static void* operator new(size_t);
00212     static void  operator delete(void*,size_t);
00213   };
00214 
00219   template<class Char, class Traits, class Task>
00220   std::basic_ostream<Char,Traits>&
00221   operator <<(std::basic_ostream<Char,Traits>& os, 
00222               const TaskArray<Task>& t);
00223 
00224 
00226   template<class TaskView>
00227   class TaskViewArray {
00228   protected:
00230     typedef typename TaskViewTraits<TaskView>::Task Task;
00232     TaskArray<Task>& t;
00233   public:
00235 
00236 
00237     TaskViewArray(TaskArray<Task>& t);
00239 
00241 
00242 
00243     int size(void) const;
00245     void size(int n);
00247 
00249 
00250 
00251     TaskView& operator [](int i);
00253     const TaskView& operator [](int i) const;
00255   private:
00256     static void* operator new(size_t);
00257     static void  operator delete(void*,size_t);
00258   };
00259 
00264   template<class Char, class Traits, class TaskView>
00265   std::basic_ostream<Char,Traits>&
00266   operator <<(std::basic_ostream<Char,Traits>& os, 
00267               const TaskViewArray<TaskView>& t);
00268 
00269 }}
00270 
00271 #include <gecode/scheduling/task/array.hpp>
00272 
00273 namespace Gecode { namespace Scheduling {
00274 
00276   enum SortTaskOrder {
00277     STO_EST, 
00278     STO_ECT, 
00279     STO_LST, 
00280     STO_LCT  
00281   };
00282 
00284   template<class TaskView, SortTaskOrder sto, bool inc>
00285   void sort(TaskViewArray<TaskView>& t);
00286 
00288   template<class TaskView, SortTaskOrder sto, bool inc>
00289   void sort(int* map, const TaskViewArray<TaskView>& t);
00290 
00292   template<class TaskView, SortTaskOrder sto, bool inc>
00293   void sort(int* map, int n, const TaskViewArray<TaskView>& t);
00294 
00295 }}
00296 
00297 #include <gecode/scheduling/task/sort.hpp>
00298 
00299 namespace Gecode { namespace Scheduling {
00300 
00302   template<class TaskView, SortTaskOrder sto, bool inc>
00303   class TaskViewIter {
00304   protected:
00306     int* map;
00308     int i;
00310     TaskViewIter(void);
00311   public:
00313     TaskViewIter(Region& r, const TaskViewArray<TaskView>& t);
00315 
00316 
00317     bool operator ()(void) const;
00319     int left(void) const;
00321     void operator ++(void);
00323 
00325 
00326 
00327     int task(void) const;
00329   };
00330 
00332   template<class OptTaskView, SortTaskOrder sto, bool inc>
00333   class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
00334   protected:
00335     using TaskViewIter<OptTaskView,sto,inc>::map;
00336     using TaskViewIter<OptTaskView,sto,inc>::i;
00337   public:
00339     ManTaskViewIter(Region& r, const TaskViewArray<OptTaskView>& t);
00340   };
00341 
00342 }}
00343 
00344 #include <gecode/scheduling/task/iter.hpp>
00345 
00346 namespace Gecode { namespace Scheduling {
00347 
00349   int plus(int x, int y);
00350 
00352   template<class TaskView, class Node>
00353   class TaskTree {
00354   protected:
00356     const TaskViewArray<TaskView>& tasks;
00358     Node* node;
00360     int* _leaf;
00361 
00363     int n_inner(void) const;
00365     int n_nodes(void) const;
00367     static bool n_root(int i);
00369     bool n_leaf(int i) const;
00371     static int n_left(int i);
00373     static int n_right(int i);
00375     static int n_parent(int i);
00376   protected:
00378     Node& leaf(int i);
00380     const Node& root(void) const;
00382     void update(int i, bool l=true);
00384     void init(void);
00386     TaskTree(Region& r, const TaskViewArray<TaskView>& t);
00387   };
00388 
00389 }}
00390 
00391 #include <gecode/scheduling/task/tree.hpp>
00392 
00393 namespace Gecode { namespace Scheduling {
00394 
00401   template<class Task>
00402   class TaskProp : public Propagator {
00403   protected:
00405     TaskArray<Task> t;
00407     TaskProp(Home home, TaskArray<Task>& t);
00409     TaskProp(Space& home, bool shared, TaskProp<Task>& p);
00410   public:
00412     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00414     virtual size_t dispose(Space& home);
00415   };
00416 
00418   template<class OptTask>
00419   ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t);
00420 
00421 }}
00422 
00423 #include <gecode/scheduling/task/prop.hpp>
00424 #include <gecode/scheduling/task/purge.hpp>
00425 
00426 #endif
00427 
00428 // STATISTICS: scheduling-prop