Generated on Tue Jul 18 2017 18:41:42 for Gecode by doxygen 1.8.13
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  * 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 namespace Gecode { namespace Int { namespace Unary {
41 
42  /*
43  * Mandatory fixed task
44  */
45 
49  ManFixPTask::ManFixPTask(IntVar s, int p) : _s(s), _p(p) {}
50  forceinline void
52  _s=s; _p=p;
53  }
54  forceinline void
56  _s=t._s; _p=t._p;
57  }
58 
59  forceinline int
60  ManFixPTask::est(void) const {
61  return _s.min();
62  }
63  forceinline int
64  ManFixPTask::ect(void) const {
65  return _s.min()+_p;
66  }
67  forceinline int
68  ManFixPTask::lst(void) const {
69  return _s.max();
70  }
71  forceinline int
72  ManFixPTask::lct(void) const {
73  return _s.max()+_p;
74  }
75  forceinline int
76  ManFixPTask::pmin(void) const {
77  return _p;
78  }
79  forceinline int
80  ManFixPTask::pmax(void) const {
81  return _p;
82  }
84  ManFixPTask::st(void) const {
85  return _s;
86  }
87 
88  forceinline bool
89  ManFixPTask::mandatory(void) const {
90  return true;
91  }
92  forceinline bool
93  ManFixPTask::excluded(void) const {
94  return false;
95  }
96  forceinline bool
97  ManFixPTask::optional(void) const {
98  return false;
99  }
100 
101  forceinline bool
102  ManFixPTask::assigned(void) const {
103  return _s.assigned();
104  }
105 
107  ManFixPTask::est(Space& home, int n) {
108  return _s.gq(home,n);
109  }
111  ManFixPTask::ect(Space& home, int n) {
112  return _s.gq(home,n-_p);
113  }
115  ManFixPTask::lst(Space& home, int n) {
116  return _s.lq(home,n);
117  }
119  ManFixPTask::lct(Space& home, int n) {
120  return _s.lq(home,n-_p);
121  }
123  ManFixPTask::norun(Space& home, int e, int l) {
124  if (e <= l) {
126  return _s.minus_r(home,r,false);
127  } else {
128  return ME_INT_NONE;
129  }
130  }
131 
132 
135  return ME_INT_NONE;
136  }
139  return ME_INT_FAILED;
140  }
141 
142  forceinline void
143  ManFixPTask::update(Space& home, bool share, ManFixPTask& t) {
144  _s.update(home,share,t._s); _p=t._p;
145  }
146 
147  forceinline void
149  _s.subscribe(home, p, pc);
150  }
151  forceinline void
153  _s.cancel(home, p, pc);
154  }
155  forceinline void
157  _s.reschedule(home, p, pc);
158  }
159 
160  template<class Char, class Traits>
161  std::basic_ostream<Char,Traits>&
162  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t) {
163  std::basic_ostringstream<Char,Traits> s;
164  s.copyfmt(os); s.width(0);
165  s << t.est() << ':' << t.pmin() << ':' << t.lct();
166  return os << s.str();
167  }
168 
169  /*
170  * Mandatory fixed task with fixed processing, start or end time
171  */
172 
177  : ManFixPTask(s,p), _t(t) {}
178  forceinline void
180  ManFixPTask::init(s,p); _t=t;
181  }
182  forceinline void
184  ManFixPTask::init(t0); _t = t0._t;
185  }
186 
187  forceinline int
188  ManFixPSETask::est(void) const {
189  return (_t == TT_FIXS) ? _p : _s.min();
190  }
191  forceinline int
192  ManFixPSETask::ect(void) const {
193  switch (_t) {
194  case TT_FIXP: return _s.min()+_p;
195  case TT_FIXS: return _s.min();
196  case TT_FIXE: return _p;
197  default: GECODE_NEVER;
198  }
199  return 0;
200  }
201  forceinline int
202  ManFixPSETask::lst(void) const {
203  return (_t == TT_FIXS) ? _p : _s.max();
204  }
205  forceinline int
206  ManFixPSETask::lct(void) const {
207  switch (_t) {
208  case TT_FIXP: return _s.max()+_p;
209  case TT_FIXS: return _s.max();
210  case TT_FIXE: return _p;
211  default: GECODE_NEVER;
212  }
213  return 0;
214  }
215  forceinline int
216  ManFixPSETask::pmin(void) const {
217  switch (_t) {
218  case TT_FIXP: return _p;
219  case TT_FIXS: return _s.min()-_p;
220  case TT_FIXE: return _p-_s.max();
221  default: GECODE_NEVER;
222  }
223  return 0;
224  }
225  forceinline int
226  ManFixPSETask::pmax(void) const {
227  switch (_t) {
228  case TT_FIXP: return _p;
229  case TT_FIXS: return _s.max()-_p;
230  case TT_FIXE: return _p-_s.min();
231  default: GECODE_NEVER;
232  }
233  return 0;
234  }
235 
237  ManFixPSETask::est(Space& home, int n) {
238  switch (_t) {
239  case TT_FIXE: // fall through
240  case TT_FIXP: return _s.gq(home,n);
241  case TT_FIXS: return (n <= _p) ? ME_INT_NONE : ME_INT_FAILED;
242  default: GECODE_NEVER;
243  }
244  return ME_INT_NONE;
245  }
247  ManFixPSETask::ect(Space& home, int n) {
248  switch (_t) {
249  case TT_FIXE: return (n <= _p) ? ME_INT_NONE : ME_INT_FAILED;
250  case TT_FIXP: return _s.gq(home,n-_p);
251  case TT_FIXS: return _s.gq(home,n);
252  default: GECODE_NEVER;
253  }
254  return ME_INT_NONE;
255  }
257  ManFixPSETask::lst(Space& home, int n) {
258  switch (_t) {
259  case TT_FIXE: // fall through
260  case TT_FIXP: return _s.lq(home,n);
261  case TT_FIXS: return (n >= _p) ? ME_INT_NONE : ME_INT_FAILED;
262  default: GECODE_NEVER;
263  }
264  return ME_INT_NONE;
265  }
267  ManFixPSETask::lct(Space& home, int n) {
268  switch (_t) {
269  case TT_FIXE: return (n >= _p) ? ME_INT_NONE : ME_INT_FAILED;
270  case TT_FIXP: return _s.lq(home,n-_p);
271  case TT_FIXS: return _s.lq(home,n);
272  default: GECODE_NEVER;
273  }
274  return ME_INT_NONE;
275  }
277  ManFixPSETask::norun(Space& home, int e, int l) {
278  if (e <= l) {
279  switch (_t) {
280  case TT_FIXP:
281  {
283  return _s.minus_r(home,r,false);
284  }
285  case TT_FIXE:
286  if (e <= _p)
287  return _s.gr(home,l);
288  break;
289  case TT_FIXS:
290  if (l >= _p)
291  return _s.lq(home,e);
292  break;
293  default:
294  GECODE_NEVER;
295  }
296  return ME_INT_NONE;
297  } else {
298  return ME_INT_NONE;
299  }
300  }
301 
302  forceinline void
304  ManFixPTask::update(home,share,t); _t=t._t;
305  }
306 
307  template<class Char, class Traits>
308  std::basic_ostream<Char,Traits>&
309  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t) {
310  std::basic_ostringstream<Char,Traits> s;
311  s.copyfmt(os); s.width(0);
312  s << t.est() << ':' << t.pmin() << ':' << t.lct();
313  return os << s.str();
314  }
315 
316  /*
317  * Mandatory flexible task
318  */
319 
324  : _s(s), _p(p), _e(e) {}
325  forceinline void
327  _s=s; _p=p; _e=e;
328  }
329  forceinline void
331  _s=t._s; _p=t._p; _e=t._e;
332  }
333 
334  forceinline int
335  ManFlexTask::est(void) const {
336  return _s.min();
337  }
338  forceinline int
339  ManFlexTask::ect(void) const {
340  return _e.min();
341  }
342  forceinline int
343  ManFlexTask::lst(void) const {
344  return _s.max();
345  }
346  forceinline int
347  ManFlexTask::lct(void) const {
348  return _e.max();
349  }
350  forceinline int
351  ManFlexTask::pmin(void) const {
352  return _p.min();
353  }
354  forceinline int
355  ManFlexTask::pmax(void) const {
356  return _p.max();
357  }
359  ManFlexTask::st(void) const {
360  return _s;
361  }
363  ManFlexTask::p(void) const {
364  return _p;
365  }
367  ManFlexTask::e(void) const {
368  return _e;
369  }
370 
371  forceinline bool
373  return true;
374  }
375  forceinline bool
376  ManFlexTask::excluded(void) const {
377  return false;
378  }
379  forceinline bool
380  ManFlexTask::optional(void) const {
381  return false;
382  }
383 
384  forceinline bool
385  ManFlexTask::assigned(void) const {
386  return _s.assigned() && _p.assigned() && _e.assigned();
387  }
388 
390  ManFlexTask::est(Space& home, int n) {
391  return _s.gq(home,n);
392  }
394  ManFlexTask::ect(Space& home, int n) {
395  return _e.gq(home,n);
396  }
398  ManFlexTask::lst(Space& home, int n) {
399  return _s.lq(home,n);
400  }
402  ManFlexTask::lct(Space& home, int n) {
403  return _e.lq(home,n);
404  }
406  ManFlexTask::norun(Space& home, int e, int l) {
407  if (e <= l) {
408  Iter::Ranges::Singleton sr(e-_p.min()+1,l);
409  if (me_failed(_s.minus_r(home,sr,false)))
410  return ME_INT_FAILED;
411  Iter::Ranges::Singleton er(e+1,_p.min()+l);
412  return _e.minus_r(home,er,false);
413  } else {
414  return ME_INT_NONE;
415  }
416  }
417 
418 
421  return ME_INT_NONE;
422  }
425  return ME_INT_FAILED;
426  }
427 
428  forceinline void
429  ManFlexTask::update(Space& home, bool share, ManFlexTask& t) {
430  _s.update(home,share,t._s);
431  _p.update(home,share,t._p);
432  _e.update(home,share,t._e);
433  }
434 
435  forceinline void
437  _s.subscribe(home, p, pc);
438  _p.subscribe(home, p, pc);
439  _e.subscribe(home, p, pc);
440  }
441  forceinline void
443  _s.cancel(home, p, pc);
444  _p.cancel(home, p, pc);
445  _e.cancel(home, p, pc);
446  }
447  forceinline void
449  _s.reschedule(home, p, pc);
450  _p.reschedule(home, p, pc);
451  _e.reschedule(home, p, pc);
452  }
453 
454  template<class Char, class Traits>
455  std::basic_ostream<Char,Traits>&
456  operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t) {
457  std::basic_ostringstream<Char,Traits> s;
458  s.copyfmt(os); s.width(0);
459  s << t.est() << ':' << t.lst() << ':' << t.pmin() << ':'
460  << t.pmax() << ':' << t.ect() << ':' << t.lct();
461  return os << s.str();
462  }
463 
464  /*
465  * Optional fixed task
466  */
467 
472  ManFixPTask::init(s,p); _m=m;
473  }
474  forceinline void
476  ManFixPTask::init(s,p); _m=m;
477  }
478 
479  template<class Char, class Traits>
480  std::basic_ostream<Char,Traits>&
481  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t) {
482  std::basic_ostringstream<Char,Traits> s;
483  s.copyfmt(os); s.width(0);
484  s << t.est() << ':' << t.pmin() << ':' << t.lct() << ':'
485  << (t.mandatory() ? '1' : (t.optional() ? '?' : '0'));
486  return os << s.str();
487  }
488 
489  /*
490  * Optional fixed task
491  */
492 
497  ManFixPSETask::init(t,s,p); _m=m;
498  }
499  forceinline void
501  ManFixPSETask::init(t,s,p); _m=m;
502  }
503 
504  template<class Char, class Traits>
505  std::basic_ostream<Char,Traits>&
506  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t) {
507  std::basic_ostringstream<Char,Traits> s;
508  s.copyfmt(os); s.width(0);
509  s << t.est() << ':' << t.pmin() << ':' << t.lct() << ':'
510  << (t.mandatory() ? '1' : (t.optional() ? '?' : '0'));
511  return os << s.str();
512  }
513 
514  /*
515  * Optional flexible task
516  */
517 
522  ManFlexTask::init(s,p,e); _m=m;
523  }
524  forceinline void
526  ManFlexTask::init(s,p,e); _m=m;
527  }
528 
529  template<class Char, class Traits>
530  std::basic_ostream<Char,Traits>&
531  operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t) {
532  std::basic_ostringstream<Char,Traits> s;
533  s.copyfmt(os); s.width(0);
534  s << t.est() << ':' << t.lst() << ':' << t.pmin() << ':'
535  << t.pmax() << ':' << t.ect() << ':' << t.lct() << ':'
536  << (t.mandatory() ? '1' : (t.optional() ? '?' : '0'));
537  return os << s.str();
538  }
539 
540 }}}
541 
542 // STATISTICS: int-var
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:142
Unary (mandatory) task with fixed processing, start or end time
Definition: unary.hh:152
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:489
void update(Space &home, bool share, ManFixPSETask &t)
Update this task to be a clone of task t.
Definition: task.hpp:303
NodeType t
Type of node.
Definition: bool-expr.cpp:234
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
Range iterator for singleton range.
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
bool optional(void) const
Whether task can still be optional.
Definition: task.hpp:380
bool optional(void) const
Whether task can still be optional.
Definition: task.hpp:97
bool excluded(void) const
Whether task is excluded.
Definition: task.hpp:376
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: task.hpp:436
IntVar st(void) const
Return start time.
Definition: task.hpp:359
OptFlexTask(void)
Default constructor.
Definition: task.hpp:519
Unary (mandatory) task with fixed processing time
Definition: unary.hh:58
int lct(void) const
Return latest completion time.
Definition: task.hpp:72
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:525
bool mandatory(void) const
Whether task is mandatory.
Definition: task.hpp:89
ManFlexTask(void)
Default constructor.
Definition: task.hpp:321
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:500
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for propagators.
Definition: core.hpp:1092
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: view.hpp:494
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:355
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:185
int est(void) const
Return earliest start time.
Definition: task.hpp:60
Computation spaces.
Definition: core.hpp:1748
OptFixPSETask(void)
Default constructor.
Definition: task.hpp:494
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: task.hpp:277
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
int pmin(void) const
Return minimum processing time.
Definition: task.hpp:351
Unary optional task with fixed processing time
Definition: unary.hh:226
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:483
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: task.hpp:448
Int::IntView _s
Start time.
Definition: unary.hh:61
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: task.hpp:152
ManFixPTask(void)
Default constructor.
Definition: task.hpp:47
void update(Space &home, bool share, ManFixPTask &t)
Update this task to be a clone of task t.
Definition: task.hpp:143
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
int lct(void) const
Return latest completion time.
Definition: task.hpp:347
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: task.hpp:406
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
void init(IntVar s, IntVar p, IntVar e)
Initialize with start time s, processing time p, end time e.
Definition: task.hpp:326
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
bool assigned(void) const
Test whether task is assigned.
Definition: task.hpp:385
int est(void) const
Return earliest start time.
Definition: task.hpp:188
TaskType _t
Task type.
Definition: unary.hh:155
void update(Space &home, bool share, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:529
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: task.hpp:148
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:226
int lst(void) const
Return latest start time.
Definition: task.hpp:202
int lst(void) const
Return latest start time.
Definition: task.hpp:343
Int::IntView _e
End time.
Definition: unary.hh:281
Boolean integer variables.
Definition: int.hh:494
int ect(void) const
Return earliest completion time.
Definition: task.hpp:192
int lct(void) const
Return latest completion time.
Definition: task.hpp:206
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void init(TaskType t, IntVar s, int p)
Initialize task.
Definition: task.hpp:179
Int::IntView _p
Processing time.
Definition: unary.hh:279
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:478
int ect(void) const
Return earliest completion time.
Definition: task.hpp:64
void update(Space &home, bool share, ManFlexTask &t)
Update this task to be a clone of task t.
Definition: task.hpp:429
OptFixPTask(void)
Default constructor.
Definition: task.hpp:469
Integer variables.
Definition: int.hh:353
#define forceinline
Definition: config.hpp:173
bool excluded(void) const
Whether task is excluded.
Definition: task.hpp:93
Unary optional task with fixed processing, start or end time.
Definition: unary.hh:250
bool mandatory(void) const
Whether task is mandatory.
Definition: task.hpp:372
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
IntVar st(void) const
Return start time.
Definition: task.hpp:84
int pmax(void) const
Return maximum processing time.
Definition: task.hpp:80
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: task.hpp:442
int est(void) const
Return earliest start time.
Definition: task.hpp:335
ManFixPSETask(void)
Default constructor.
Definition: task.hpp:174
bool assigned(void) const
Test whether task is assigned.
Definition: task.hpp:102
IntVar e(void) const
Return end time.
Definition: task.hpp:367
IntVar p(void) const
Return processing time.
Definition: task.hpp:363
Gecode toplevel namespace
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
Multi _e(Gecode::IntArgs(4, 4, 2, 3, 1))
Unary (mandatory) task with flexible processing time
Definition: unary.hh:274
void init(IntVar s, int p, BoolVar m)
Initialize with start time s, processing time p, and mandatory flag m.
Definition: task.hpp:475
int ect(void) const
Return earliest completion time.
Definition: task.hpp:339
Int::IntView _s
Start time.
Definition: unary.hh:277
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: task.hpp:156
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
int pmin(void) const
Return minimum processing time.
Definition: task.hpp:216