Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
unary.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_INT_UNARY_HH__
41 #define __GECODE_INT_UNARY_HH__
42 
43 #include <gecode/int/task.hh>
44 
55 namespace Gecode { namespace Int { namespace Unary {
56 
58  class ManFixPTask {
59  protected:
63  int _p;
64  public:
66 
67  ManFixPTask(void);
70  ManFixPTask(IntVar s, int p);
72  void init(IntVar s, int p);
74  void init(const ManFixPTask& t);
76 
78 
79  int est(void) const;
82  int ect(void) const;
84  int lst(void) const;
86  int lct(void) const;
88  int pmin(void) const;
90  int pmax(void) const;
92  IntVar st(void) const;
94  bool mandatory(void) const;
96  bool excluded(void) const;
98  bool optional(void) const;
100 
102 
103  bool assigned(void) const;
106 
108 
109  ModEvent est(Space& home, int n);
112  ModEvent ect(Space& home, int n);
114  ModEvent lst(Space& home, int n);
116  ModEvent lct(Space& home, int n);
118  ModEvent norun(Space& home, int e, int l);
120  ModEvent mandatory(Space& home);
122  ModEvent excluded(Space& home);
124 
126 
127  void update(Space& home, bool share, ManFixPTask& t);
130 
132 
133  void subscribe(Space& home, Propagator& p, PropCond pc);
136  void cancel(Space& home, Propagator& p, PropCond pc);
138  void reschedule(Space& home, Propagator& p, PropCond pc);
140 
141  };
142 
147  template<class Char, class Traits>
148  std::basic_ostream<Char,Traits>&
149  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);
150 
152  class ManFixPSETask : public ManFixPTask {
153  protected:
156  public:
158 
159  ManFixPSETask(void);
167  ManFixPSETask(TaskType t, IntVar s, int p);
174  void init(TaskType t, IntVar s, int p);
176  void init(const ManFixPSETask& t);
178 
180 
181  int est(void) const;
184  int ect(void) const;
186  int lst(void) const;
188  int lct(void) const;
190  int pmin(void) const;
192  int pmax(void) const;
194 
196 
197  ModEvent est(Space& home, int n);
200  ModEvent ect(Space& home, int n);
202  ModEvent lst(Space& home, int n);
204  ModEvent lct(Space& home, int n);
206  ModEvent norun(Space& home, int e, int l);
208 
210 
211  void update(Space& home, bool share, ManFixPSETask& t);
214 
215  };
216 
221  template<class Char, class Traits>
222  std::basic_ostream<Char,Traits>&
223  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);
224 
226  class OptFixPTask : public ManToOptTask<ManFixPTask> {
227  protected:
229  public:
231 
232  OptFixPTask(void);
235  OptFixPTask(IntVar s, int p, BoolVar m);
237  void init(IntVar s, int p, BoolVar m);
239  };
240 
245  template<class Char, class Traits>
246  std::basic_ostream<Char,Traits>&
247  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);
248 
250  class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
251  protected:
253  public:
255 
256  OptFixPSETask(void);
259  OptFixPSETask(TaskType t, IntVar s, int p, BoolVar m);
261  void init(TaskType t, IntVar s, int p, BoolVar m);
263  };
264 
269  template<class Char, class Traits>
270  std::basic_ostream<Char,Traits>&
271  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);
272 
274  class ManFlexTask {
275  protected:
282  public:
284 
285  ManFlexTask(void);
290  void init(IntVar s, IntVar p, IntVar e);
292  void init(const ManFlexTask& t);
294 
296 
297  int est(void) const;
300  int ect(void) const;
302  int lst(void) const;
304  int lct(void) const;
306  int pmin(void) const;
308  int pmax(void) const;
310  IntVar st(void) const;
312  IntVar p(void) const;
314  IntVar e(void) const;
316  bool mandatory(void) const;
318  bool excluded(void) const;
320  bool optional(void) const;
322 
324 
325  bool assigned(void) const;
328 
330 
331  ModEvent est(Space& home, int n);
334  ModEvent ect(Space& home, int n);
336  ModEvent lst(Space& home, int n);
338  ModEvent lct(Space& home, int n);
340  ModEvent norun(Space& home, int e, int l);
342  ModEvent mandatory(Space& home);
344  ModEvent excluded(Space& home);
346 
348 
349  void update(Space& home, bool share, ManFlexTask& t);
352 
354 
355  void subscribe(Space& home, Propagator& p, PropCond pc);
358  void cancel(Space& home, Propagator& p, PropCond pc);
360  void reschedule(Space& home, Propagator& p, PropCond pc);
362 
363  };
364 
369  template<class Char, class Traits>
370  std::basic_ostream<Char,Traits>&
371  operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);
372 
374  class OptFlexTask : public ManToOptTask<ManFlexTask> {
375  protected:
377  public:
379 
380  OptFlexTask(void);
385  void init(IntVar s, IntVar p, IntVar e, BoolVar m);
387  };
388 
393  template<class Char, class Traits>
394  std::basic_ostream<Char,Traits>&
395  operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);
396 
397 }}}
398 
399 #include <gecode/int/unary/task.hpp>
400 
401 namespace Gecode { namespace Int { namespace Unary {
402 
405 
408 
411 
414 
417 
420 
423 
426 
429 
432 
435 
438 
439 
444  template<class Char, class Traits>
445  std::basic_ostream<Char,Traits>&
446  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);
447 
452  template<class Char, class Traits>
453  std::basic_ostream<Char,Traits>&
454  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);
455 
460  template<class Char, class Traits>
461  std::basic_ostream<Char,Traits>&
462  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);
463 
468  template<class Char, class Traits>
469  std::basic_ostream<Char,Traits>&
470  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);
471 
476  template<class Char, class Traits>
477  std::basic_ostream<Char,Traits>&
478  operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTaskBwd& t);
479 
486  template<class Char, class Traits>
487  std::basic_ostream<Char,Traits>&
488  operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTaskBwd& t);
489 
490 }}}
491 
493 
494 namespace Gecode { namespace Int {
495 
497  template<>
499  public:
502  };
503 
505  template<>
507  public:
510  };
511 
513  template<>
515  public:
518  };
519 
521  template<>
523  public:
526  };
527 
529  template<>
531  public:
534  };
535 
537  template<>
539  public:
542  };
543 
545  template<>
547  public:
550  };
551 
553  template<>
555  public:
558  };
559 
561  template<>
563  public:
566  };
567 
569  template<>
571  public:
574  };
575 
577  template<>
579  public:
582  };
583 
585  template<>
587  public:
590  };
591 
592 
594  template<>
595  class TaskTraits<Unary::ManFixPTask> {
596  public:
601  };
602 
604  template<>
605  class TaskTraits<Unary::ManFixPSETask> {
606  public:
611  };
612 
614  template<>
615  class TaskTraits<Unary::OptFixPTask> {
616  public:
623  };
624 
626  template<>
627  class TaskTraits<Unary::OptFixPSETask> {
628  public:
635  };
636 
638  template<>
639  class TaskTraits<Unary::ManFlexTask> {
640  public:
645  };
646 
648  template<>
649  class TaskTraits<Unary::OptFlexTask> {
650  public:
657  };
658 
659 }}
660 
661 namespace Gecode { namespace Int { namespace Unary {
662 
664  class OmegaNode {
665  public:
667  int p;
669  int ect;
671  void init(const OmegaNode& l, const OmegaNode& r);
673  void update(const OmegaNode& l, const OmegaNode& r);
674  };
675 
677  template<class TaskView>
678  class OmegaTree : public TaskTree<TaskView,OmegaNode> {
679  protected:
685  public:
689  void insert(int i);
691  void remove(int i);
693  int ect(void) const;
695  int ect(int i) const;
696  };
697 
699  class OmegaLambdaNode : public OmegaNode {
700  public:
702  static const int undef = -1;
704  int lp;
706  int lect;
708  int resEct;
710  int resLp;
712  void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
714  void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
715  };
716 
718  template<class TaskView>
719  class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
720  protected:
726  public:
729  bool inc=true);
731  void shift(int i);
733  void oinsert(int i);
735  void linsert(int i);
737  void lremove(int i);
739  bool lempty(void) const;
741  int responsible(void) const;
743  int ect(void) const;
745  int lect(void) const;
746  };
747 
748 }}}
749 
750 #include <gecode/int/unary/tree.hpp>
751 
752 namespace Gecode { namespace Int { namespace Unary {
753 
755  template<class ManTask>
758  template<class OptTask, class PL>
760 
762  template<class Task>
764 
766  template<class Task>
768 
770  template<class ManTask>
773  template<class OptTask, class PL>
775 
777  template<class ManTask>
780  template<class OptTask, class PL>
782 
784  template<class Task>
786 
787 
794  template<class ManTask, class PL>
795  class ManProp : public TaskProp<ManTask,PL> {
796  protected:
799  ManProp(Home home, TaskArray<ManTask>& t);
801  ManProp(Space& home, bool shared, ManProp& p);
802  public:
804  virtual Actor* copy(Space& home, bool share);
806  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
808  static ExecStatus post(Home home, TaskArray<ManTask>& t);
809  };
810 
817  template<class OptTask, class PL>
818  class OptProp : public TaskProp<OptTask,PL> {
819  protected:
822  OptProp(Home home, TaskArray<OptTask>& t);
824  OptProp(Space& home, bool shared, OptProp& p);
825  public:
827  virtual Actor* copy(Space& home, bool share);
829  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
831  static ExecStatus post(Home home, TaskArray<OptTask>& t);
832  };
833 
835  template<class ManTask>
836  ExecStatus
838 
840  template<class OptTask>
841  ExecStatus
843 
844 }}}
845 
852 
855 #include <gecode/int/unary/post.hpp>
856 
857 #endif
858 
859 // STATISTICS: int-prop
Omega-lambda trees for computing ect of task sets.
Definition: unary.hh:719
OptFixPTask OptFixPTaskFwd
Forward optional fixed task view.
Definition: unary.hh:416
Unary (mandatory) task with fixed processing, start or end time
Definition: unary.hh:152
int resEct
Node which is responsible for lect.
Definition: unary.hh:708
Node for an omega tree.
Definition: unary.hh:664
NodeType t
Type of node.
Definition: bool-expr.cpp:234
FwdToBwd< ManFixPSETaskFwd > ManFixPSETaskBwd
Backward (dual) mandatory fixed task view.
Definition: unary.hh:413
Task view array.
Definition: task.hh:237
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
TaskType
Type of task for scheduling constraints.
Definition: int.hh:990
int pmin(void) const
Return minimum processing time.
Definition: task.hpp:76
Unary optional task with flexible processing time
Definition: unary.hh:374
Unary::OptFixPTaskBwd TaskViewBwd
The backward task view type.
Definition: unary.hh:620
void init(IntVar s, int p)
Initialize with start time s and processing time p.
Definition: task.hpp:51
int _p
Processing time.
Definition: unary.hh:63
ExecStatus manpost(Home home, TaskArray< ManTask > &t, IntPropLevel ipl)
Post mandatory task propagator according to propagation level.
Definition: post.hpp:42
int lp
Processing times for subtree.
Definition: unary.hh:704
bool optional(void) const
Whether task can still be optional.
Definition: task.hpp:97
ExecStatus timetabling(Space &home, Propagator &p, TaskArray< Task > &t)
Perform time-tabling propagation.
FwdToBwd< OptFixPTaskFwd > OptFixPTaskBwd
Backward (dual) optional fixed task view.
Definition: unary.hh:419
Unary::ManFixPTask Task
The task type.
Definition: unary.hh:509
Unary::ManFixPTask ManTask
The corresponding mandatory task.
Definition: unary.hh:622
Scheduling propagator for unary resource with mandatory tasks
Definition: unary.hh:795
Unary::ManFixPTaskFwd TaskViewFwd
The forward task view type.
Definition: unary.hh:598
Unary (mandatory) task with fixed processing time
Definition: unary.hh:58
int lct(void) const
Return latest completion time.
Definition: task.hpp:72
Unary::OptFixPTask Task
The task type.
Definition: unary.hh:541
bool mandatory(void) const
Whether task is mandatory.
Definition: task.hpp:89
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for propagators.
Definition: core.hpp:1092
Propagator for tasks
Definition: task.hh:428
Handle to region.
Definition: region.hpp:61
Unary::ManFlexTask Task
The task type.
Definition: unary.hh:573
ExecStatus notfirstnotlast(Space &home, TaskArray< ManTask > &t)
Propagate not-first and not-last.
Unary::OptFixPSETaskFwd TaskViewFwd
The forward task view type.
Definition: unary.hh:630
int est(void) const
Return earliest start time.
Definition: task.hpp:60
Computation spaces.
Definition: core.hpp:1748
Unary::OptFixPSETaskBwd TaskViewBwd
The backward task view type.
Definition: unary.hh:632
int ect
Earliest completion time for subtree.
Definition: unary.hh:669
int lect
Earliest completion times for subtree.
Definition: unary.hh:706
Traits class for mapping tasks to task views.
Definition: task.hh:161
Base-class for both propagators and branchers.
Definition: core.hpp:696
Unary::OptFlexTask Task
The task type.
Definition: unary.hh:581
Unary::OptFlexTaskFwd TaskViewFwd
The forward task view type.
Definition: unary.hh:652
Unary::OptFixPTaskFwd TaskViewFwd
The forward task view type.
Definition: unary.hh:618
Unary optional task with fixed processing time
Definition: unary.hh:226
Int::IntView _s
Start time.
Definition: unary.hh:61
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Omega trees for computing ect of task sets.
Definition: unary.hh:678
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Unary::ManFixPTaskBwd TaskViewBwd
The backward task view type.
Definition: unary.hh:600
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: task.hpp:152
Unary::ManFixPTask ManTask
The corresponding mandatory task.
Definition: unary.hh:634
ManFixPTask(void)
Default constructor.
Definition: task.hpp:47
Unary::ManFixPSETaskBwd TaskViewBwd
The backward task view type.
Definition: unary.hh:610
FwdToBwd< OptFixPSETaskFwd > OptFixPSETaskBwd
Backward (dual) optional fixed task view.
Definition: unary.hh:425
void update(Space &home, bool share, ManFixPTask &t)
Update this task to be a clone of task t.
Definition: task.hpp:143
Unary::ManFixPSETaskFwd TaskViewFwd
The forward task view type.
Definition: unary.hh:608
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
Unary::OptFixPSETask Task
The task type.
Definition: unary.hh:549
ExecStatus overload(Space &home, TaskArray< ManTask > &t)
Check mandatory tasks t for overload.
Definition: overload.hpp:43
Unary::ManFixPTask Task
The task type.
Definition: unary.hh:501
Node for an omega lambda tree.
Definition: unary.hh:699
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: task.hpp:123
int lst(void) const
Return latest start time.
Definition: task.hpp:68
Class to define an optional from a mandatory task.
Definition: task.hh:47
ExecStatus detectable(Space &home, TaskViewArray< ManTaskView > &t)
Definition: detectable.hpp:42
FwdToBwd< ManFixPTaskFwd > ManFixPTaskBwd
Backward (dual) mandatory fixed task view.
Definition: unary.hh:407
TaskType _t
Task type.
Definition: unary.hh:155
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: task.hpp:148
FwdToBwd< OptFlexTaskFwd > OptFlexTaskBwd
Backward (dual) optional flexible task view.
Definition: unary.hh:437
ExecStatus optpost(Home home, TaskArray< OptTask > &t, IntPropLevel ipl)
Post optional task propagator according to propagation level.
Definition: post.hpp:57
Int::IntView _e
End time.
Definition: unary.hh:281
Boolean integer variables.
Definition: int.hh:494
Unary::OptFixPTask Task
The task type.
Definition: unary.hh:533
Task mapper: turns a task view into its dual.
Definition: task.hh:106
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
int resLp
Node which is responsible for lp.
Definition: unary.hh:710
Unary::ManFlexTaskFwd TaskViewFwd
The forward task view type.
Definition: unary.hh:642
Int::IntView _p
Processing time.
Definition: unary.hh:279
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:955
Integer view for integer variables.
Definition: view.hpp:129
ExecStatus subsumed(Space &home, Propagator &p, TaskArray< Task > &t)
Check tasks t for subsumption.
Definition: subsumption.hpp:42
Unary::ManFixPSETask Task
The task type.
Definition: unary.hh:517
int ect(void) const
Return earliest completion time.
Definition: task.hpp:64
Unary::OptFlexTaskBwd TaskViewBwd
The backward task view type.
Definition: unary.hh:654
Scheduling propagator for unary resource with optional tasks
Definition: unary.hh:818
ManFlexTask ManFlexTaskFwd
Forward mandatory flexible task view.
Definition: unary.hh:428
ExecStatus
Definition: core.hpp:540
Integer variables.
Definition: int.hh:353
OptFixPSETask OptFixPSETaskFwd
Forward optional fixed task view.
Definition: unary.hh:422
bool excluded(void) const
Whether task is excluded.
Definition: task.hpp:93
Unary::ManFlexTask Task
The task type.
Definition: unary.hh:565
Unary optional task with fixed processing, start or end time.
Definition: unary.hh:250
IntVar st(void) const
Return start time.
Definition: task.hpp:84
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:80
ExecStatus edgefinding(Space &home, TaskViewArray< TaskView > &t)
Traits class for mapping task views to tasks.
Definition: task.hh:152
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:702
Unary::OptFlexTask Task
The task type.
Definition: unary.hh:589
OptFlexTask OptFlexTaskFwd
Forward optional flexible task view.
Definition: unary.hh:434
bool assigned(void) const
Test whether task is assigned.
Definition: task.hpp:102
Gecode toplevel namespace
ManFixPSETask ManFixPSETaskFwd
Forward mandatory fixed task view.
Definition: unary.hh:410
Unary::ManFlexTaskBwd TaskViewBwd
The backward task view type.
Definition: unary.hh:644
Unary (mandatory) task with flexible processing time
Definition: unary.hh:274
Unary::ManFixPSETask Task
The task type.
Definition: unary.hh:525
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Task trees for task views with node type Node.
Definition: task.hh:369
Int::IntView _s
Start time.
Definition: unary.hh:277
ManFixPTask ManFixPTaskFwd
Forward mandatory fixed task view.
Definition: unary.hh:404
FwdToBwd< ManFlexTaskFwd > ManFlexTaskBwd
Backward (dual) mandatory flexible task view.
Definition: unary.hh:431
Unary::OptFixPSETask Task
The task type.
Definition: unary.hh:557
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: task.hpp:156
Unary::ManFlexTask ManTask
The corresponding mandatory task.
Definition: unary.hh:656
int p
Processing time for subtree.
Definition: unary.hh:667
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.