Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
task.hpp
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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 namespace Gecode { namespace Int { namespace Unary {
37 
38  /*
39  * Mandatory fixed task
40  */
41 
45  ManFixPTask::ManFixPTask(IntVar s, int p) : _s(s), _p(p) {}
46  forceinline void
48  _s=s; _p=p;
49  }
50  forceinline void
52  _s=t._s; _p=t._p;
53  }
54 
55  forceinline int
56  ManFixPTask::est(void) const {
57  return _s.min();
58  }
59  forceinline int
60  ManFixPTask::ect(void) const {
61  return _s.min()+_p;
62  }
63  forceinline int
64  ManFixPTask::lst(void) const {
65  return _s.max();
66  }
67  forceinline int
68  ManFixPTask::lct(void) const {
69  return _s.max()+_p;
70  }
71  forceinline int
72  ManFixPTask::pmin(void) const {
73  return _p;
74  }
75  forceinline int
76  ManFixPTask::pmax(void) const {
77  return _p;
78  }
80  ManFixPTask::st(void) const {
81  return _s;
82  }
83 
84  forceinline bool
85  ManFixPTask::mandatory(void) const {
86  return true;
87  }
88  forceinline bool
89  ManFixPTask::excluded(void) const {
90  return false;
91  }
92  forceinline bool
93  ManFixPTask::optional(void) const {
94  return false;
95  }
96 
97  forceinline bool
98  ManFixPTask::assigned(void) const {
99  return _s.assigned();
100  }
101 
103  ManFixPTask::est(Space& home, int n) {
104  return _s.gq(home,n);
105  }
107  ManFixPTask::ect(Space& home, int n) {
108  return _s.gq(home,n-_p);
109  }
111  ManFixPTask::lst(Space& home, int n) {
112  return _s.lq(home,n);
113  }
115  ManFixPTask::lct(Space& home, int n) {
116  return _s.lq(home,n-_p);
117  }
119  ManFixPTask::norun(Space& home, int e, int l) {
120  if (e <= l) {
122  return _s.minus_r(home,r,false);
123  } else {
124  return ME_INT_NONE;
125  }
126  }
127 
128 
131  return ME_INT_NONE;
132  }
135  return ME_INT_FAILED;
136  }
137 
138  forceinline void
140  _s.update(home,t._s); _p=t._p;
141  }
142 
143  forceinline void
145  _s.subscribe(home, p, pc);
146  }
147  forceinline void
149  _s.cancel(home, p, pc);
150  }
151  forceinline void
153  _s.reschedule(home, p, pc);
154  }
155 
156  template<class Char, class Traits>
157  std::basic_ostream<Char,Traits>&
158  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t) {
159  std::basic_ostringstream<Char,Traits> s;
160  s.copyfmt(os); s.width(0);
161  s << t.est() << ':' << t.pmin() << ':' << t.lct();
162  return os << s.str();
163  }
164 
165  /*
166  * Mandatory fixed task with fixed processing, start or end time
167  */
168 
173  : ManFixPTask(s,p), _t(t) {}
174  forceinline void
176  ManFixPTask::init(s,p); _t=t;
177  }
178  forceinline void
180  ManFixPTask::init(t0); _t = t0._t;
181  }
182 
183  forceinline int
184  ManFixPSETask::est(void) const {
185  return (_t == TT_FIXS) ? _p : _s.min();
186  }
187  forceinline int
188  ManFixPSETask::ect(void) const {
189  switch (_t) {
190  case TT_FIXP: return _s.min()+_p;
191  case TT_FIXS: return _s.min();
192  case TT_FIXE: return _p;
193  default: GECODE_NEVER;
194  }
195  return 0;
196  }
197  forceinline int
198  ManFixPSETask::lst(void) const {
199  return (_t == TT_FIXS) ? _p : _s.max();
200  }
201  forceinline int
202  ManFixPSETask::lct(void) const {
203  switch (_t) {
204  case TT_FIXP: return _s.max()+_p;
205  case TT_FIXS: return _s.max();
206  case TT_FIXE: return _p;
207  default: GECODE_NEVER;
208  }
209  return 0;
210  }
211  forceinline int
212  ManFixPSETask::pmin(void) const {
213  switch (_t) {
214  case TT_FIXP: return _p;
215  case TT_FIXS: return _s.min()-_p;
216  case TT_FIXE: return _p-_s.max();
217  default: GECODE_NEVER;
218  }
219  return 0;
220  }
221  forceinline int
222  ManFixPSETask::pmax(void) const {
223  switch (_t) {
224  case TT_FIXP: return _p;
225  case TT_FIXS: return _s.max()-_p;
226  case TT_FIXE: return _p-_s.min();
227  default: GECODE_NEVER;
228  }
229  return 0;
230  }
231 
233  ManFixPSETask::est(Space& home, int n) {
234  switch (_t) {
235  case TT_FIXE: // fall through
236  case TT_FIXP: return _s.gq(home,n);
237  case TT_FIXS: return (n <= _p) ? ME_INT_NONE : ME_INT_FAILED;
238  default: GECODE_NEVER;
239  }
240  return ME_INT_NONE;
241  }
243  ManFixPSETask::ect(Space& home, int n) {
244  switch (_t) {
245  case TT_FIXE: return (n <= _p) ? ME_INT_NONE : ME_INT_FAILED;
246  case TT_FIXP: return _s.gq(home,n-_p);
247  case TT_FIXS: return _s.gq(home,n);
248  default: GECODE_NEVER;
249  }
250  return ME_INT_NONE;
251  }
253  ManFixPSETask::lst(Space& home, int n) {
254  switch (_t) {
255  case TT_FIXE: // fall through
256  case TT_FIXP: return _s.lq(home,n);
257  case TT_FIXS: return (n >= _p) ? ME_INT_NONE : ME_INT_FAILED;
258  default: GECODE_NEVER;
259  }
260  return ME_INT_NONE;
261  }
263  ManFixPSETask::lct(Space& home, int n) {
264  switch (_t) {
265  case TT_FIXE: return (n >= _p) ? ME_INT_NONE : ME_INT_FAILED;
266  case TT_FIXP: return _s.lq(home,n-_p);
267  case TT_FIXS: return _s.lq(home,n);
268  default: GECODE_NEVER;
269  }
270  return ME_INT_NONE;
271  }
273  ManFixPSETask::norun(Space& home, int e, int l) {
274  if (e <= l) {
275  switch (_t) {
276  case TT_FIXP:
277  {
279  return _s.minus_r(home,r,false);
280  }
281  case TT_FIXE:
282  if (e <= _p)
283  return _s.gr(home,l);
284  break;
285  case TT_FIXS:
286  if (l >= _p)
287  return _s.lq(home,e);
288  break;
289  default:
290  GECODE_NEVER;
291  }
292  return ME_INT_NONE;
293  } else {
294  return ME_INT_NONE;
295  }
296  }
297 
298  forceinline void
300  ManFixPTask::update(home,t); _t=t._t;
301  }
302 
303  template<class Char, class Traits>
304  std::basic_ostream<Char,Traits>&
305  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t) {
306  std::basic_ostringstream<Char,Traits> s;
307  s.copyfmt(os); s.width(0);
308  s << t.est() << ':' << t.pmin() << ':' << t.lct();
309  return os << s.str();
310  }
311 
312  /*
313  * Mandatory flexible task
314  */
315 
320  : _s(s), _p(p), _e(e) {}
321  forceinline void
323  _s=s; _p=p; _e=e;
324  }
325  forceinline void
327  _s=t._s; _p=t._p; _e=t._e;
328  }
329 
330  forceinline int
331  ManFlexTask::est(void) const {
332  return _s.min();
333  }
334  forceinline int
335  ManFlexTask::ect(void) const {
336  return _e.min();
337  }
338  forceinline int
339  ManFlexTask::lst(void) const {
340  return _s.max();
341  }
342  forceinline int
343  ManFlexTask::lct(void) const {
344  return _e.max();
345  }
346  forceinline int
347  ManFlexTask::pmin(void) const {
348  return _p.min();
349  }
350  forceinline int
351  ManFlexTask::pmax(void) const {
352  return _p.max();
353  }
355  ManFlexTask::st(void) const {
356  return _s;
357  }
359  ManFlexTask::p(void) const {
360  return _p;
361  }
363  ManFlexTask::e(void) const {
364  return _e;
365  }
366 
367  forceinline bool
369  return true;
370  }
371  forceinline bool
372  ManFlexTask::excluded(void) const {
373  return false;
374  }
375  forceinline bool
376  ManFlexTask::optional(void) const {
377  return false;
378  }
379 
380  forceinline bool
381  ManFlexTask::assigned(void) const {
382  return _s.assigned() && _p.assigned() && _e.assigned();
383  }
384 
386  ManFlexTask::est(Space& home, int n) {
387  return _s.gq(home,n);
388  }
390  ManFlexTask::ect(Space& home, int n) {
391  return _e.gq(home,n);
392  }
394  ManFlexTask::lst(Space& home, int n) {
395  return _s.lq(home,n);
396  }
398  ManFlexTask::lct(Space& home, int n) {
399  return _e.lq(home,n);
400  }
402  ManFlexTask::norun(Space& home, int e, int l) {
403  if (e <= l) {
404  Iter::Ranges::Singleton sr(e-_p.min()+1,l);
405  if (me_failed(_s.minus_r(home,sr,false)))
406  return ME_INT_FAILED;
407  Iter::Ranges::Singleton er(e+1,_p.min()+l);
408  return _e.minus_r(home,er,false);
409  } else {
410  return ME_INT_NONE;
411  }
412  }
413 
414 
417  return ME_INT_NONE;
418  }
421  return ME_INT_FAILED;
422  }
423 
424  forceinline void
426  _s.update(home,t._s);
427  _p.update(home,t._p);
428  _e.update(home,t._e);
429  }
430 
431  forceinline void
433  _s.subscribe(home, p, pc);
434  _p.subscribe(home, p, pc);
435  _e.subscribe(home, p, pc);
436  }
437  forceinline void
439  _s.cancel(home, p, pc);
440  _p.cancel(home, p, pc);
441  _e.cancel(home, p, pc);
442  }
443  forceinline void
445  _s.reschedule(home, p, pc);
446  _p.reschedule(home, p, pc);
447  _e.reschedule(home, p, pc);
448  }
449 
450  template<class Char, class Traits>
451  std::basic_ostream<Char,Traits>&
452  operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t) {
453  std::basic_ostringstream<Char,Traits> s;
454  s.copyfmt(os); s.width(0);
455  s << t.est() << ':' << t.lst() << ':' << t.pmin() << ':'
456  << t.pmax() << ':' << t.ect() << ':' << t.lct();
457  return os << s.str();
458  }
459 
460  /*
461  * Optional fixed task
462  */
463 
468  ManFixPTask::init(s,p); _m=m;
469  }
470  forceinline void
472  ManFixPTask::init(s,p); _m=m;
473  }
474 
475  template<class Char, class Traits>
476  std::basic_ostream<Char,Traits>&
477  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t) {
478  std::basic_ostringstream<Char,Traits> s;
479  s.copyfmt(os); s.width(0);
480  s << t.est() << ':' << t.pmin() << ':' << t.lct() << ':'
481  << (t.mandatory() ? '1' : (t.optional() ? '?' : '0'));
482  return os << s.str();
483  }
484 
485  /*
486  * Optional fixed task
487  */
488 
493  ManFixPSETask::init(t,s,p); _m=m;
494  }
495  forceinline void
497  ManFixPSETask::init(t,s,p); _m=m;
498  }
499 
500  template<class Char, class Traits>
501  std::basic_ostream<Char,Traits>&
502  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t) {
503  std::basic_ostringstream<Char,Traits> s;
504  s.copyfmt(os); s.width(0);
505  s << t.est() << ':' << t.pmin() << ':' << t.lct() << ':'
506  << (t.mandatory() ? '1' : (t.optional() ? '?' : '0'));
507  return os << s.str();
508  }
509 
510  /*
511  * Optional flexible task
512  */
513 
518  ManFlexTask::init(s,p,e); _m=m;
519  }
520  forceinline void
522  ManFlexTask::init(s,p,e); _m=m;
523  }
524 
525  template<class Char, class Traits>
526  std::basic_ostream<Char,Traits>&
527  operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t) {
528  std::basic_ostringstream<Char,Traits> s;
529  s.copyfmt(os); s.width(0);
530  s << t.est() << ':' << t.lst() << ':' << t.pmin() << ':'
531  << t.pmax() << ':' << t.ect() << ':' << t.lct() << ':'
532  << (t.mandatory() ? '1' : (t.optional() ? '?' : '0'));
533  return os << s.str();
534  }
535 
536 }}}
537 
538 // STATISTICS: int-var
void init(TaskType t, IntVar s, int p)
Initialize task.
Definition: task.hpp:175
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: task.hpp:119
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:516
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: task.hpp:148
int est(void) const
Return earliest start time.
Definition: task.hpp:56
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:222
void update(Space &home, ManFixPTask &t)
Update this task to be a clone of task t.
Definition: task.hpp:139
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
ManFlexTask(void)
Default constructor.
Definition: task.hpp:317
IntVar p(void) const
Return processing time.
Definition: task.hpp:359
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:76
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
Unary (mandatory) task with fixed processing, start or end time
Definition: unary.hh:148
int lst(void) const
Return latest start time.
Definition: task.hpp:64
OptFixPTask(void)
Default constructor.
Definition: task.hpp:465
Unary (mandatory) task with flexible processing time
Definition: unary.hh:270
void init(IntVar s, IntVar p, IntVar e)
Initialize with start time s, processing time p, end time e.
Definition: task.hpp:322
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:521
NodeType t
Type of node.
Definition: bool-expr.cpp:230
bool assigned(void) const
Test whether task is assigned.
Definition: task.hpp:381
int lct(void) const
Return latest completion time.
Definition: task.hpp:68
void init(IntVar s, int p)
Initialize with start time s and processing time p.
Definition: task.hpp:47
OptFixPSETask(void)
Default constructor.
Definition: task.hpp:490
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: task.hpp:432
ManFixPTask(void)
Default constructor.
Definition: task.hpp:43
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:527
Int::IntView _s
Start time.
Definition: unary.hh:273
Computation spaces.
Definition: core.hpp:1742
OptFlexTask(void)
Default constructor.
Definition: task.hpp:515
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:567
void init(IntVar s, IntVar p, IntVar e, BoolVar m)
Initialize with start time s, processing time p, end time e, and mandatory flag m.
Definition: task.hpp:521
TaskType _t
Task type.
Definition: unary.hh:151
Unary (mandatory) task with fixed processing time
Definition: unary.hh:54
Int::IntView _e
End time.
Definition: unary.hh:277
void update(Space &home, ManFixPSETask &t)
Update this task to be a clone of task t.
Definition: task.hpp:299
Gecode toplevel namespace
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
Base-class for propagators.
Definition: core.hpp:1064
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: task.hpp:402
int ect(void) const
Return earliest completion time.
Definition: task.hpp:335
@ TT_FIXS
Definition: int.hh:1006
bool optional(void) const
Whether task can still be optional.
Definition: task.hpp:93
bool excluded(void) const
Whether task is excluded.
Definition: task.hpp:89
int lst(void) const
Return latest start time.
Definition: task.hpp:339
int pmin(void) const
Return minimum processing time.
Definition: task.hpp:212
bool mandatory(void) const
Whether task is mandatory.
Definition: task.hpp:368
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Boolean integer variables.
Definition: int.hh:512
bool assigned(void) const
Test whether task is assigned.
Definition: task.hpp:98
int lct(void) const
Return latest completion time.
Definition: task.hpp:202
int lct(void) const
Return latest completion time.
Definition: task.hpp:343
int ect(void) const
Return earliest completion time.
Definition: task.hpp:188
Integer variables.
Definition: int.hh:371
bool optional(void) const
Whether task can still be optional.
Definition: task.hpp:376
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
Multi _e(Gecode::IntArgs({4, 2, 3, 1}))
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: task.hpp:144
IntVar st(void) const
Return start time.
Definition: task.hpp:80
int ModEvent
Type for modification events.
Definition: core.hpp:62
Int::IntView _s
Start time.
Definition: unary.hh:57
IntVar st(void) const
Return start time.
Definition: task.hpp:355
void init(TaskType t, IntVar s, int p, BoolVar m)
Initialize with start time s, processing time p, and mandatory flag m.
Definition: task.hpp:496
bool mandatory(void) const
Whether task is mandatory.
Definition: task.hpp:85
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: task.hpp:273
void init(IntVar s, int p, BoolVar m)
Initialize with start time s, processing time p, and mandatory flag m.
Definition: task.hpp:471
int pmin(void) const
Return minimum processing time.
Definition: task.hpp:347
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
TaskType
Type of task for scheduling constraints.
Definition: int.hh:1004
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: view.hpp:532
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int _p
Processing time.
Definition: unary.hh:59
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:148
ManFixPSETask(void)
Default constructor.
Definition: task.hpp:170
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:351
int lst(void) const
Return latest start time.
Definition: task.hpp:198
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition: task.hh:46
#define forceinline
Definition: config.hpp:185
@ TT_FIXE
Definition: int.hh:1007
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const ManFixPTaskBwd &t)
Definition: task-view.hpp:40
Range iterator for singleton range.
bool excluded(void) const
Whether task is excluded.
Definition: task.hpp:372
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
@ TT_FIXP
Definition: int.hh:1005
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: task.hpp:444
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: task.hpp:438
int est(void) const
Return earliest start time.
Definition: task.hpp:184
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:191
int ect(void) const
Return earliest completion time.
Definition: task.hpp:60
int est(void) const
Return earliest start time.
Definition: task.hpp:331
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Int::IntView _p
Processing time.
Definition: unary.hh:275
IntVar e(void) const
Return end time.
Definition: task.hpp:363
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: task.hpp:152
int pmin(void) const
Return minimum processing time.
Definition: task.hpp:72
void update(Space &home, ManFlexTask &t)
Update this task to be a clone of task t.
Definition: task.hpp:425