Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
39namespace Gecode { namespace Int {
40
42 template<class ManTask>
43 class ManToOptTask : public ManTask {
44 protected:
47 public:
49
50
51 ManToOptTask(void);
53
55
56
57 bool mandatory(void) const;
59 bool excluded(void) const;
61 bool optional(void) const;
63
65
66 bool assigned(void) const;
68
70
71
74 ModEvent excluded(Space& home);
76
78
79
80 void update(Space& home, ManToOptTask& t);
82
84
85
86 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
98namespace Gecode { namespace Int {
99
101 template<class TaskView>
102 class FwdToBwd : public TaskView {
103 public:
105
106
107 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
123 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
139namespace Gecode { namespace Int {
140
147 template<class TaskView>
149
156 template<class Task>
157 class TaskTraits {};
158
159}}
160
161namespace Gecode { namespace Int {
162
164 template<class Task>
165 class TaskArray {
166 private:
168 int n;
170 Task* t;
171 public:
173
174
175 TaskArray(void);
177 TaskArray(Space& home, int n);
183
185
186
187 int size(void) const;
189 void size(int n);
191
193
194
195 Task& operator [](int i);
197 const Task& operator [](int i) const;
199
201
202
209
211
212
213 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
242
245
247
248
249 int size(void) const;
251 void size(int n);
253
255
256
257 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,
274
275}}
276
278
279namespace Gecode { namespace Int {
280
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
304
305namespace Gecode { namespace Int {
306
308 template<class TaskView, SortTaskOrder sto, bool inc>
310 protected:
312 int* map;
314 int i;
316 TaskViewIter(void);
317 public:
321
322
323 bool operator ()(void) const;
325 int left(void) const;
327 void operator ++(void);
329
331
332
333 int task(void) const;
335 };
336
338 template<class OptTaskView, SortTaskOrder sto, bool inc>
339 class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
340 protected:
341 using TaskViewIter<OptTaskView,sto,inc>::map;
342 using TaskViewIter<OptTaskView,sto,inc>::i;
343 public:
346 };
347
348}}
349
351
352namespace 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,
409 };
410
411}}
412
414
415namespace Gecode { namespace Int {
416
423 template<class Task, class PL>
424 class TaskProp : public Propagator {
425 protected:
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
486
487namespace 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
533
534#endif
535
536// STATISTICS: int-prop
NNF * l
Left subtree.
NodeType t
Type of node.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
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.
int lst(void) const
Return latest start time.
int lct(void) const
Return latest completion time.
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
int est(void) const
Return earliest start time.
int pmin(void) const
Return minimum processing time.
int pmax(void) const
Return maximum processing time.
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.
bool mandatory(void) const
Whether task is mandatory.
ManToOptTask(void)
Default constructor.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
void update(Space &home, ManToOptTask &t)
Update this task to be a clone of task t.
bool optional(void) const
Whether task can still be optional.
bool excluded(void) const
Whether task is excluded.
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
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
TaskViewTraits< TaskView >::Task Task
The underlying task type.
Definition task.hh:236
TaskArray< Task > & t
Access to task array.
Definition task.hh:238
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
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
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
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const IdxViewArray< View > &x)
Definition idx-view.hpp:167
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62