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