Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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);
181  const TaskArray<Task>& operator =(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);
207  void reschedule(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 
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
Sort by earliest completion times.
Definition: task.hh:284
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Task view array.
Definition: task.hh:233
TaskArray< Task > & t
Access to task array.
Definition: task.hh:238
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
unsigned int ei
Combines type and number of task.
Definition: task.hh:503
Class for defining basic propagation level.
Definition: task.hh:450
bool excluded(void) const
Whether task is excluded.
Definition: man-to-opt.hpp:47
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: man-to-opt.hpp:95
SortTaskOrder
How to sort tasks.
Definition: task.hh:282
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: man-to-opt.hpp:82
int ModEvent
Type for modification events.
Definition: core.hpp:62
Base-class for propagators.
Definition: core.hpp:1023
Propagator for tasks
Definition: task.hh:424
Task array.
Definition: task.hh:165
Handle to region.
Definition: region.hpp:53
Node * node
Task nodes.
Definition: task.hh:371
Computation spaces.
Definition: core.hpp:1701
Traits class for mapping tasks to task views.
Definition: task.hh:157
Sort by earliest start times.
Definition: task.hh:283
Class for defining advanced propagation level.
Definition: task.hh:461
Gecode::FloatVal c(-8, 8)
Class for defining basic and advanced propagation level.
Definition: task.hh:472
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:133
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Time-tabling event for task.
Definition: task.hh:490
TaskViewTraits< TaskView >::Task Task
The underlying task type.
Definition: task.hh:236
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:72
Allows to iterate over task views according to a specified order.
Definition: task.hh:309
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:39
unsigned int size(I &i)
Size of all ranges of range iterator i.
ManToOptTask(void)
Default constructor.
Definition: man-to-opt.hpp:38
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:43
int * _leaf
Map task number to leaf node number in right order.
Definition: task.hh:373
Sort by latest completion times.
Definition: task.hh:286
Task mapper: turns a task view into its dual.
Definition: task.hh:102
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
int * map
Map for iteration order.
Definition: task.hh:312
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
bool mandatory(void) const
Whether task is mandatory.
Definition: man-to-opt.hpp:42
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Propagation cost.
Definition: core.hpp:485
ExecStatus
Definition: core.hpp:471
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: man-to-opt.hpp:88
Allows to iterate over mandatory task views according to a specified order.
Definition: task.hh:339
Post propagator for SetVar x
Definition: set.hh:765
bool optional(void) const
Whether task can still be optional.
Definition: man-to-opt.hpp:52
Traits class for mapping task views to tasks.
Definition: task.hh:148
bool operator<(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:226
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition: task.hh:46
Gecode toplevel namespace
int i
Current position.
Definition: task.hh:314
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:369
TaskArray< Task > t
Tasks.
Definition: task.hh:427
void update(Space &home, ManToOptTask &t)
Update this task to be a clone of task t.
Definition: man-to-opt.hpp:75
int t
Time of event.
Definition: task.hh:505
Sort by latest start times.
Definition: task.hh:285
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
Task trees for task views with node type Node.
Definition: task.hh:365
Type
Event type for task with order in which they are processed.
Definition: task.hh:493
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition: purge.hpp:38
bool assigned(void) const
Test whether task is assigned.
Definition: man-to-opt.hpp:58
Boolean view for Boolean variables.
Definition: view.hpp:1349