Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
task.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  *
6  * Copyright:
7  * Christian Schulte, 2009
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #ifndef __GECODE_INT_TASK_HH__
35 #define __GECODE_INT_TASK_HH__
36 
37 #include <gecode/int.hh>
38 
39 namespace Gecode { namespace Int {
40 
42  template<class ManTask>
43  class ManToOptTask : public ManTask {
44  protected:
47  public:
49 
50  ManToOptTask(void);
53 
55 
56  bool mandatory(void) const;
59  bool excluded(void) const;
61  bool optional(void) const;
63 
65  bool assigned(void) const;
68 
70 
71  ModEvent mandatory(Space& home);
74  ModEvent excluded(Space& home);
76 
78 
79  void update(Space& home, ManToOptTask& t);
82 
84 
85  void subscribe(Space& home, Propagator& p, PropCond pc);
88  void cancel(Space& home, Propagator& p, PropCond pc);
90  void reschedule(Space& home, Propagator& p, PropCond pc);
92  };
93 
94 }}
95 
97 
98 namespace Gecode { namespace Int {
99 
101  template<class TaskView>
102  class FwdToBwd : public TaskView {
103  public:
105 
106  int est(void) const;
109  int ect(void) const;
111  int lst(void) const;
113  int lct(void) const;
115  int pmin(void) const;
117  int pmax(void) const;
119 
121 
122  ModEvent est(Space& home, int n);
125  ModEvent ect(Space& home, int n);
127  ModEvent lst(Space& home, int n);
129  ModEvent lct(Space& home, int n);
131  ModEvent norun(Space& home, int e, int l);
133  };
134 
135 }}
136 
138 
139 namespace Gecode { namespace Int {
140 
147  template<class TaskView>
148  class TaskViewTraits {};
149 
156  template<class Task>
157  class TaskTraits {};
158 
159 }}
160 
161 namespace Gecode { namespace Int {
162 
164  template<class Task>
165  class TaskArray {
166  private:
168  int n;
170  Task* t;
171  public:
173 
174  TaskArray(void);
177  TaskArray(Space& home, int n);
179  TaskArray(const TaskArray<Task>& a);
183 
185 
186  int size(void) const;
189  void size(int n);
191 
193 
194  Task& operator [](int i);
197  const Task& operator [](int i) const;
199 
201 
205  void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
209 
211 
212  void update(Space&, TaskArray& a);
215 
216  private:
217  static void* operator new(size_t);
218  static void operator delete(void*,size_t);
219  };
220 
225  template<class Char, class Traits, class Task>
226  std::basic_ostream<Char,Traits>&
227  operator <<(std::basic_ostream<Char,Traits>& os,
228  const TaskArray<Task>& t);
229 
230 
232  template<class TaskView>
234  protected:
239  public:
241 
245 
247 
248  int size(void) const;
251  void size(int n);
253 
255 
256  TaskView& operator [](int i);
259  const TaskView& operator [](int i) const;
261  private:
262  static void* operator new(size_t);
263  static void operator delete(void*,size_t);
264  };
265 
270  template<class Char, class Traits, class TaskView>
271  std::basic_ostream<Char,Traits>&
272  operator <<(std::basic_ostream<Char,Traits>& os,
273  const TaskViewArray<TaskView>& t);
274 
275 }}
276 
277 #include <gecode/int/task/array.hpp>
278 
279 namespace Gecode { namespace Int {
280 
286  STO_LCT
287  };
288 
290  template<class TaskView, SortTaskOrder sto, bool inc>
292 
294  template<class TaskView, SortTaskOrder sto, bool inc>
295  void sort(int* map, const TaskViewArray<TaskView>& t);
296 
298  template<class TaskView, SortTaskOrder sto, bool inc>
299  void sort(int* map, int n, const TaskViewArray<TaskView>& t);
300 
301 }}
302 
303 #include <gecode/int/task/sort.hpp>
304 
305 namespace Gecode { namespace Int {
306 
308  template<class TaskView, SortTaskOrder sto, bool inc>
309  class TaskViewIter {
310  protected:
312  int* map;
314  int i;
316  TaskViewIter(void);
317  public:
321 
322  bool operator ()(void) const;
325  int left(void) const;
327  void operator ++(void);
329 
331 
332  int task(void) const;
335  };
336 
338  template<class OptTaskView, SortTaskOrder sto, bool inc>
339  class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
340  protected:
343  public:
346  };
347 
348 }}
349 
350 #include <gecode/int/task/iter.hpp>
351 
352 namespace Gecode { namespace Int {
353 
355  int plus(int x, int y);
356 
358  long long int plus(long long int x, long long int y);
359 
361  double plus(double x, double y);
362 
364  template<class TaskView, class Node>
365  class TaskTree {
366  template<class,class> friend class TaskTree;
367  protected:
371  Node* node;
373  int* _leaf;
374 
376  int n_inner(void) const;
378  int n_nodes(void) const;
380  static bool n_root(int i);
382  bool n_leaf(int i) const;
384  static int n_left(int i);
386  static bool left(int i);
388  static int n_right(int i);
390  static bool right(int i);
392  static int n_parent(int i);
393  protected:
395  Node& leaf(int i);
397  const Node& root(void) const;
399  void update(int i, bool l=true);
401  void init(void);
403  void update(void);
407  template<class Node2> TaskTree(Region& r,
408  const TaskTree<TaskView,Node2>& t);
409  };
410 
411 }}
412 
413 #include <gecode/int/task/tree.hpp>
414 
415 namespace Gecode { namespace Int {
416 
423  template<class Task, class PL>
424  class TaskProp : public Propagator {
425  protected:
429  TaskProp(Home home, TaskArray<Task>& t);
432  public:
434  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
436  virtual void reschedule(Space& home);
438  virtual size_t dispose(Space& home);
439  };
440 
442  template<class OptTask, class PL>
444 
446  template<class OptTask, class PL, class Cap>
448 
450  class PLB {
451  public:
453  static const bool basic = true;
455  static const bool advanced = false;
457  static const PropCond pc = PC_INT_DOM;
458  };
459 
461  class PLA {
462  public:
464  static const bool basic = false;
466  static const bool advanced = true;
468  static const PropCond pc = PC_INT_BND;
469  };
470 
472  class PLBA {
473  public:
475  static const bool basic = true;
477  static const bool advanced = true;
479  static const PropCond pc = PC_INT_DOM;
480  };
481 
482 }}
483 
484 #include <gecode/int/task/prop.hpp>
485 #include <gecode/int/task/purge.hpp>
486 
487 namespace Gecode { namespace Int {
488 
490  class Event {
491  public:
493  enum Type {
494  LRT = 0,
495  LCT = 1,
496  EST = 2,
497  ZRO = 3,
498  ERT = 4,
499  END = 5
500  };
501  protected:
503  unsigned int ei;
505  int t;
506  public:
508  void init(Type e, int t, int i);
510  Type type(void) const;
512  int time(void) const;
514  int idx(void) const;
516  bool operator <(const Event& e) const;
518  template<class Task>
519  static Event* events(Region& r, const TaskArray<Task>& t, bool& assigned);
521  template<class Task>
522  static Event* events(Region& r, const TaskArray<Task>& t);
523  };
524 
526  template<class Char, class Traits>
527  std::basic_ostream<Char,Traits>&
528  operator <<(std::basic_ostream<Char,Traits>& os, const Event& e);
529 
530 }}
531 
532 #include <gecode/int/task/event.hpp>
533 
534 #endif
535 
536 // STATISTICS: int-prop
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Home class for posting propagators
Definition: core.hpp:856
Boolean view for Boolean variables.
Definition: view.hpp:1380
Time-tabling event for task.
Definition: task.hh:490
int t
Time of event.
Definition: task.hh:505
int idx(void) const
Return event index.
Definition: event.hpp:50
static Event * events(Region &r, const TaskArray< Task > &t, bool &assigned)
Allocate from r and initialize event array with tasks t.
Definition: event.hpp:83
unsigned int ei
Combines type and number of task.
Definition: task.hh:503
void init(Type e, int t, int i)
Initialize event.
Definition: event.hpp:37
Type
Event type for task with order in which they are processed.
Definition: task.hh:493
@ ZRO
Zero-length task start time.
Definition: task.hh:497
@ ERT
Earliest required time of task.
Definition: task.hh:498
@ LRT
Latest required time of task.
Definition: task.hh:494
@ EST
Earliest start time of task.
Definition: task.hh:496
@ END
End marker.
Definition: task.hh:499
@ LCT
Latest completion time of task.
Definition: task.hh:495
int time(void) const
Return event time.
Definition: event.hpp:46
Type type(void) const
Return event type.
Definition: event.hpp:42
bool operator<(const Event &e) const
Order among events.
Definition: event.hpp:55
Task mapper: turns a task view into its dual.
Definition: task.hh:102
int ect(void) const
Return earliest completion time.
Definition: fwd-to-bwd.hpp:46
int lst(void) const
Return latest start time.
Definition: fwd-to-bwd.hpp:51
int lct(void) const
Return latest completion time.
Definition: fwd-to-bwd.hpp:56
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: fwd-to-bwd.hpp:92
int est(void) const
Return earliest start time.
Definition: fwd-to-bwd.hpp:41
int pmin(void) const
Return minimum processing time.
Definition: fwd-to-bwd.hpp:61
int pmax(void) const
Return maximum processing time.
Definition: fwd-to-bwd.hpp:66
Allows to iterate over mandatory task views according to a specified order.
Definition: task.hh:339
ManTaskViewIter(Region &r, const TaskViewArray< OptTaskView > &t)
Initialize iterator with mandatory tasks.
Definition: iter.hpp:76
Class to define an optional from a mandatory task.
Definition: task.hh:43
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition: task.hh:46
bool assigned(void) const
Test whether task is assigned.
Definition: man-to-opt.hpp:58
bool mandatory(void) const
Whether task is mandatory.
Definition: man-to-opt.hpp:42
ManToOptTask(void)
Default constructor.
Definition: man-to-opt.hpp:38
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: man-to-opt.hpp:88
void update(Space &home, ManToOptTask &t)
Update this task to be a clone of task t.
Definition: man-to-opt.hpp:75
bool optional(void) const
Whether task can still be optional.
Definition: man-to-opt.hpp:52
bool excluded(void) const
Whether task is excluded.
Definition: man-to-opt.hpp:47
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: man-to-opt.hpp:82
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: man-to-opt.hpp:95
Class for defining advanced propagation level.
Definition: task.hh:461
static const PropCond pc
For basic propagation, domain operations are needed.
Definition: task.hh:468
static const bool advanced
Do not perform advanced propagation.
Definition: task.hh:466
static const bool basic
Perform basic propagation.
Definition: task.hh:464
Class for defining basic and advanced propagation level.
Definition: task.hh:472
static const bool advanced
Do not perform advanced propagation.
Definition: task.hh:477
static const bool basic
Perform basic propagation.
Definition: task.hh:475
static const PropCond pc
For basic propagation, domain operations are needed.
Definition: task.hh:479
Class for defining basic propagation level.
Definition: task.hh:450
static const PropCond pc
For basic propagation, domain operations are needed.
Definition: task.hh:457
static const bool advanced
Do not perform advanced propagation.
Definition: task.hh:455
static const bool basic
Perform basic propagation.
Definition: task.hh:453
Task array.
Definition: task.hh:165
Task & operator[](int i)
Return task at position i.
Definition: array.hpp:74
void update(Space &, TaskArray &a)
Update array to be a clone of array a.
Definition: array.hpp:108
TaskArray(void)
Default constructor (array of size 0)
Definition: array.hpp:42
void subscribe(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Subscribe propagator p to all tasks.
Definition: array.hpp:87
void cancel(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Cancel subscription of propagator p for all tasks.
Definition: array.hpp:94
void reschedule(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Schedule propagator p.
Definition: array.hpp:101
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:63
const TaskArray< Task > & operator=(const TaskArray< Task > &a)
Initialize from task array a (share elements)
Definition: array.hpp:56
Propagator for tasks
Definition: task.hh:424
TaskArray< Task > t
Tasks.
Definition: task.hh:427
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: prop.hpp:64
virtual void reschedule(Space &home)
Schedule function.
Definition: prop.hpp:58
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
Definition: prop.hpp:52
TaskProp(Home home, TaskArray< Task > &t)
Constructor for creation.
Definition: prop.hpp:38
Traits class for mapping tasks to task views.
Definition: task.hh:157
Task trees for task views with node type Node.
Definition: task.hh:365
int n_nodes(void) const
Return number of nodes for balanced binary tree.
Definition: tree.hpp:57
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:369
static int n_right(int i)
Return index of right child of node i.
Definition: tree.hpp:85
int n_inner(void) const
Return number of inner nodes.
Definition: tree.hpp:52
static bool right(int i)
Test whether node i is a right child.
Definition: tree.hpp:90
static int n_left(int i)
Return index of left child of node i.
Definition: tree.hpp:73
static bool left(int i)
Test whether node i is a left child.
Definition: tree.hpp:78
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:115
Node * node
Task nodes.
Definition: task.hh:371
friend class TaskTree
Definition: task.hh:366
bool n_leaf(int i) const
Whether node i is leaf.
Definition: tree.hpp:68
const Node & root(void) const
Return root node.
Definition: tree.hpp:109
static int n_parent(int i)
Return index of parent of node i.
Definition: tree.hpp:97
int * _leaf
Map task number to leaf node number in right order.
Definition: task.hh:373
Node & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:103
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition: tree.hpp:122
static bool n_root(int i)
Whether node i is index of root.
Definition: tree.hpp:63
Task view array.
Definition: task.hh:233
TaskArray< Task > & t
Access to task array.
Definition: task.hh:238
TaskViewTraits< TaskView >::Task Task
The underlying task type.
Definition: task.hh:236
TaskViewArray(TaskArray< Task > &t)
Initialize from task array a.
Definition: array.hpp:137
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:142
TaskView & operator[](int i)
Return task view at position i.
Definition: array.hpp:154
Allows to iterate over task views according to a specified order.
Definition: task.hh:309
void operator++(void)
Move iterator to next task.
Definition: iter.hpp:62
bool operator()(void) const
Test whether iterator is still at a task.
Definition: iter.hpp:52
int * map
Map for iteration order.
Definition: task.hh:312
int task(void) const
Return current task position.
Definition: iter.hpp:68
int left(void) const
How many tasks are left to be iterated.
Definition: iter.hpp:57
int i
Current position.
Definition: task.hh:314
TaskViewIter(void)
Default constructor (no initialization)
Definition: iter.hpp:40
Traits class for mapping task views to tasks.
Definition: task.hh:148
Propagation cost.
Definition: core.hpp:486
Base-class for propagators.
Definition: core.hpp:1064
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
ExecStatus
Definition: core.hpp:472
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
int ModEvent
Type for modification events.
Definition: core.hpp:62
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:133
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition: purge.hpp:38
SortTaskOrder
How to sort tasks.
Definition: task.hh:282
@ STO_ECT
Sort by earliest completion times.
Definition: task.hh:284
@ STO_EST
Sort by earliest start times.
Definition: task.hh:283
@ STO_LST
Sort by latest start times.
Definition: task.hh:285
@ STO_LCT
Sort by latest completion times.
Definition: task.hh:286
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition: tree.hpp:39
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const IdxViewArray< View > &x)
Definition: idx-view.hpp:167
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})