Generated on Sat Jul 28 2018 17:16:14 for Gecode by doxygen 1.8.14
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  * Last modified:
10  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_INT_TASK_HH__
39 #define __GECODE_INT_TASK_HH__
40 
41 #include <gecode/int.hh>
42 
43 namespace Gecode { namespace Int {
44 
46  template<class ManTask>
47  class ManToOptTask : public ManTask {
48  protected:
51  public:
53 
54  ManToOptTask(void);
57 
59 
60  bool mandatory(void) const;
63  bool excluded(void) const;
65  bool optional(void) const;
67 
69  bool assigned(void) const;
72 
74 
75  ModEvent mandatory(Space& home);
78  ModEvent excluded(Space& home);
80 
82 
83  void update(Space& home, bool share, ManToOptTask& t);
86 
88 
89  void subscribe(Space& home, Propagator& p, PropCond pc);
92  void cancel(Space& home, Propagator& p, PropCond pc);
94  void reschedule(Space& home, Propagator& p, PropCond pc);
96  };
97 
98 }}
99 
101 
102 namespace Gecode { namespace Int {
103 
105  template<class TaskView>
106  class FwdToBwd : public TaskView {
107  public:
109 
110  int est(void) const;
113  int ect(void) const;
115  int lst(void) const;
117  int lct(void) const;
119  int pmin(void) const;
121  int pmax(void) const;
123 
125 
126  ModEvent est(Space& home, int n);
129  ModEvent ect(Space& home, int n);
131  ModEvent lst(Space& home, int n);
133  ModEvent lct(Space& home, int n);
135  ModEvent norun(Space& home, int e, int l);
137  };
138 
139 }}
140 
142 
143 namespace Gecode { namespace Int {
144 
151  template<class TaskView>
152  class TaskViewTraits {};
153 
160  template<class Task>
161  class TaskTraits {};
162 
163 }}
164 
165 namespace Gecode { namespace Int {
166 
168  template<class Task>
169  class TaskArray {
170  private:
172  int n;
174  Task* t;
175  public:
177 
178  TaskArray(void);
181  TaskArray(Space& home, int n);
183  TaskArray(const TaskArray<Task>& a);
187 
189 
190  int size(void) const;
193  void size(int n);
195 
197 
198  Task& operator [](int i);
201  const Task& operator [](int i) const;
203 
205 
209  void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
213 
215 
216  void update(Space&, bool share, TaskArray& a);
219 
220  private:
221  static void* operator new(size_t);
222  static void operator delete(void*,size_t);
223  };
224 
229  template<class Char, class Traits, class Task>
230  std::basic_ostream<Char,Traits>&
231  operator <<(std::basic_ostream<Char,Traits>& os,
232  const TaskArray<Task>& t);
233 
234 
236  template<class TaskView>
238  protected:
243  public:
245 
249 
251 
252  int size(void) const;
255  void size(int n);
257 
259 
260  TaskView& operator [](int i);
263  const TaskView& operator [](int i) const;
265  private:
266  static void* operator new(size_t);
267  static void operator delete(void*,size_t);
268  };
269 
274  template<class Char, class Traits, class TaskView>
275  std::basic_ostream<Char,Traits>&
276  operator <<(std::basic_ostream<Char,Traits>& os,
277  const TaskViewArray<TaskView>& t);
278 
279 }}
280 
281 #include <gecode/int/task/array.hpp>
282 
283 namespace Gecode { namespace Int {
284 
291  };
292 
294  template<class TaskView, SortTaskOrder sto, bool inc>
296 
298  template<class TaskView, SortTaskOrder sto, bool inc>
299  void sort(int* map, const TaskViewArray<TaskView>& t);
300 
302  template<class TaskView, SortTaskOrder sto, bool inc>
303  void sort(int* map, int n, const TaskViewArray<TaskView>& t);
304 
305 }}
306 
307 #include <gecode/int/task/sort.hpp>
308 
309 namespace Gecode { namespace Int {
310 
312  template<class TaskView, SortTaskOrder sto, bool inc>
313  class TaskViewIter {
314  protected:
316  int* map;
318  int i;
320  TaskViewIter(void);
321  public:
325 
326  bool operator ()(void) const;
329  int left(void) const;
331  void operator ++(void);
333 
335 
336  int task(void) const;
339  };
340 
342  template<class OptTaskView, SortTaskOrder sto, bool inc>
343  class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
344  protected:
347  public:
350  };
351 
352 }}
353 
354 #include <gecode/int/task/iter.hpp>
355 
356 namespace Gecode { namespace Int {
357 
359  int plus(int x, int y);
360 
362  long long int plus(long long int x, long long int y);
363 
365  double plus(double x, double y);
366 
368  template<class TaskView, class Node>
369  class TaskTree {
370  template<class,class> friend class TaskTree;
371  protected:
375  Node* node;
377  int* _leaf;
378 
380  int n_inner(void) const;
382  int n_nodes(void) const;
384  static bool n_root(int i);
386  bool n_leaf(int i) const;
388  static int n_left(int i);
390  static bool left(int i);
392  static int n_right(int i);
394  static bool right(int i);
396  static int n_parent(int i);
397  protected:
399  Node& leaf(int i);
401  const Node& root(void) const;
403  void update(int i, bool l=true);
405  void init(void);
407  void update(void);
411  template<class Node2> TaskTree(Region& r,
412  const TaskTree<TaskView,Node2>& t);
413  };
414 
415 }}
416 
417 #include <gecode/int/task/tree.hpp>
418 
419 namespace Gecode { namespace Int {
420 
427  template<class Task, class PL>
428  class TaskProp : public Propagator {
429  protected:
433  TaskProp(Home home, TaskArray<Task>& t);
435  TaskProp(Space& home, bool shared, TaskProp<Task,PL>& p);
436  public:
438  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
440  virtual void reschedule(Space& home);
442  virtual size_t dispose(Space& home);
443  };
444 
446  template<class OptTask, class PL>
448 
450  template<class OptTask, class PL, class Cap>
452 
454  class PLB {
455  public:
457  static const bool basic = true;
459  static const bool advanced = false;
461  static const PropCond pc = PC_INT_DOM;
462  };
463 
465  class PLA {
466  public:
468  static const bool basic = false;
470  static const bool advanced = true;
472  static const PropCond pc = PC_INT_BND;
473  };
474 
476  class PLBA {
477  public:
479  static const bool basic = true;
481  static const bool advanced = true;
483  static const PropCond pc = PC_INT_DOM;
484  };
485 
486 }}
487 
488 #include <gecode/int/task/prop.hpp>
489 #include <gecode/int/task/purge.hpp>
490 
491 namespace Gecode { namespace Int {
492 
494  class Event {
495  public:
497  enum Type {
498  LRT = 0,
499  LCT = 1,
500  EST = 2,
501  ZRO = 3,
502  ERT = 4,
503  END = 5
504  };
505  protected:
507  unsigned int ei;
509  int t;
510  public:
512  void init(Type e, int t, int i);
514  Type type(void) const;
516  int time(void) const;
518  int idx(void) const;
520  bool operator <(const Event& e) const;
522  template<class Task>
523  static Event* events(Region& r, const TaskArray<Task>& t, bool& assigned);
525  template<class Task>
526  static Event* events(Region& r, const TaskArray<Task>& t);
527  };
528 
530  template<class Char, class Traits>
531  std::basic_ostream<Char,Traits>&
532  operator <<(std::basic_ostream<Char,Traits>& os, const Event& e);
533 
534 }}
535 
536 #include <gecode/int/task/event.hpp>
537 
538 #endif
539 
540 // STATISTICS: int-prop
Sort by earliest completion times.
Definition: task.hh:288
Zero-length task start time.
Definition: task.hh:501
TaskProp(Home home, TaskArray< Task > &t)
Constructor for creation.
Definition: prop.hpp:42
int pmax(void) const
Return maximum processing time.
Definition: fwd-to-bwd.hpp:70
static int n_right(int i)
Return index of right child of node i.
Definition: tree.hpp:89
ManTaskViewIter(Region &r, const TaskViewArray< OptTaskView > &t)
Initialize iterator with mandatory tasks.
Definition: iter.hpp:80
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Task view array.
Definition: task.hh:237
static int n_left(int i)
Return index of left child of node i.
Definition: tree.hpp:77
TaskArray< Task > & t
Access to task array.
Definition: task.hh:242
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Type type(void) const
Return event type.
Definition: event.hpp:46
unsigned int ei
Combines type and number of task.
Definition: task.hh:507
void operator++(void)
Move iterator to next task.
Definition: iter.hpp:66
Class for defining basic propagation level.
Definition: task.hh:454
int time(void) const
Return event time.
Definition: event.hpp:50
bool excluded(void) const
Whether task is excluded.
Definition: man-to-opt.hpp:51
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: man-to-opt.hpp:100
int idx(void) const
Return event index.
Definition: event.hpp:54
SortTaskOrder
How to sort tasks.
Definition: task.hh:286
int ect(void) const
Return earliest completion time.
Definition: fwd-to-bwd.hpp:50
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:146
static const bool basic
Perform basic propagation.
Definition: task.hh:479
static bool right(int i)
Test whether node i is a right child.
Definition: tree.hpp:94
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition: fwd-to-bwd.hpp:96
void init(Type e, int t, int i)
Initialize event.
Definition: event.hpp:41
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: man-to-opt.hpp:87
static const PropCond pc
For basic propagation, domain operations are needed.
Definition: task.hh:472
static const bool basic
Perform basic propagation.
Definition: task.hh:468
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for propagators.
Definition: core.hpp:1092
TaskArray(void)
Default constructor (array of size 0)
Definition: array.hpp:46
Earliest required time of task.
Definition: task.hh:502
void reschedule(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Schedule propagator p.
Definition: array.hpp:105
Propagator for tasks
Definition: task.hh:428
static const bool basic
Perform basic propagation.
Definition: task.hh:457
int lct(void) const
Return latest completion time.
Definition: fwd-to-bwd.hpp:60
Task array.
Definition: task.hh:169
Handle to region.
Definition: region.hpp:61
Node * node
Task nodes.
Definition: task.hh:375
virtual void reschedule(Space &home)
Schedule function.
Definition: prop.hpp:62
Computation spaces.
Definition: core.hpp:1748
TaskViewArray(TaskArray< Task > &t)
Initialize from task array a.
Definition: array.hpp:141
Traits class for mapping tasks to task views.
Definition: task.hh:161
Sort by earliest start times.
Definition: task.hh:287
Class for defining advanced propagation level.
Definition: task.hh:465
TaskViewIter(void)
Default constructor (no initialization)
Definition: iter.hpp:44
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
Class for defining basic and advanced propagation level.
Definition: task.hh:476
End marker.
Definition: task.hh:503
Task & operator[](int i)
Return task at position i.
Definition: array.hpp:78
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
void update(Space &, bool share, TaskArray &a)
Update array to be a clone of array a.
Definition: array.hpp:112
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
static int n_parent(int i)
Return index of parent of node i.
Definition: tree.hpp:101
Time-tabling event for task.
Definition: task.hh:494
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition: tree.hpp:126
TaskViewTraits< TaskView >::Task Task
The underlying task type.
Definition: task.hh:240
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:119
int task(void) const
Return current task position.
Definition: iter.hpp:72
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
static const bool advanced
Do not perform advanced propagation.
Definition: task.hh:459
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
Allows to iterate over task views according to a specified order.
Definition: task.hh:313
int lst(void) const
Return latest start time.
Definition: fwd-to-bwd.hpp:55
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:43
friend class TaskTree
Definition: task.hh:370
ManToOptTask(void)
Default constructor.
Definition: man-to-opt.hpp:42
TaskView & operator[](int i)
Return task view at position i.
Definition: array.hpp:158
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
Class to define an optional from a mandatory task.
Definition: task.hh:47
int * _leaf
Map task number to leaf node number in right order.
Definition: task.hh:377
int est(void) const
Return earliest start time.
Definition: fwd-to-bwd.hpp:45
bool n_leaf(int i) const
Whether node i is leaf.
Definition: tree.hpp:72
Sort by latest completion times.
Definition: task.hh:290
bool operator<(const Event &e) const
Order among events.
Definition: event.hpp:59
bool operator()(void) const
Test whether iterator is still at a task.
Definition: iter.hpp:56
Latest completion time of task.
Definition: task.hh:499
static const PropCond pc
For basic propagation, domain operations are needed.
Definition: task.hh:461
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
void subscribe(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Subscribe propagator p to all tasks.
Definition: array.hpp:91
int * map
Map for iteration order.
Definition: task.hh:316
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
bool mandatory(void) const
Whether task is mandatory.
Definition: man-to-opt.hpp:46
int n_inner(void) const
Return number of inner nodes.
Definition: tree.hpp:56
const Node & root(void) const
Return root node.
Definition: tree.hpp:113
Propagation cost.
Definition: core.hpp:554
static bool left(int i)
Test whether node i is a left child.
Definition: tree.hpp:82
ExecStatus
Definition: core.hpp:540
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
int pmin(void) const
Return minimum processing time.
Definition: fwd-to-bwd.hpp:65
void cancel(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Cancel subscription of propagator p for all tasks.
Definition: array.hpp:98
Node & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:107
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: man-to-opt.hpp:93
Allows to iterate over mandatory task views according to a specified order.
Definition: task.hh:343
Post propagator for SetVar x
Definition: set.hh:784
static bool n_root(int i)
Whether node i is index of root.
Definition: tree.hpp:67
Latest required time of task.
Definition: task.hh:498
static Event * events(Region &r, const TaskArray< Task > &t, bool &assigned)
Allocate from r and initialize event array with tasks t.
Definition: event.hpp:87
bool optional(void) const
Whether task can still be optional.
Definition: man-to-opt.hpp:56
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
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition: task.hh:50
Gecode toplevel namespace
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
Definition: prop.hpp:56
int i
Current position.
Definition: task.hh:318
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:373
static const PropCond pc
For basic propagation, domain operations are needed.
Definition: task.hh:483
static const bool advanced
Do not perform advanced propagation.
Definition: task.hh:470
void update(Space &home, bool share, ManToOptTask &t)
Update this task to be a clone of task t.
Definition: man-to-opt.hpp:79
TaskArray< Task > t
Tasks.
Definition: task.hh:431
const TaskArray< Task > & operator=(const TaskArray< Task > &a)
Initialize from task array a (share elements)
Definition: array.hpp:60
int t
Time of event.
Definition: task.hh:509
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: prop.hpp:68
Sort by latest start times.
Definition: task.hh:289
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
int left(void) const
How many tasks are left to be iterated.
Definition: iter.hpp:61
Home class for posting propagators
Definition: core.hpp:922
int n_nodes(void) const
Return number of nodes for balanced binary tree.
Definition: tree.hpp:61
Task trees for task views with node type Node.
Definition: task.hh:369
Type
Event type for task with order in which they are processed.
Definition: task.hh:497
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition: purge.hpp:42
static const bool advanced
Do not perform advanced propagation.
Definition: task.hh:481
bool assigned(void) const
Test whether task is assigned.
Definition: man-to-opt.hpp:62
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:67
Boolean view for Boolean variables.
Definition: view.hpp:1315
Earliest start time of task.
Definition: task.hh:500