Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2013-03-11 06:26:07 +0100 (Mon, 11 Mar 2013) $ by $Author: tack $
11  * $Revision: 13487 $
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  };
95 
96 }}
97 
99 
100 namespace Gecode { namespace Int {
101 
103  template<class TaskView>
104  class FwdToBwd : public TaskView {
105  public:
107 
108  int est(void) const;
111  int ect(void) const;
113  int lst(void) const;
115  int lct(void) const;
117  int pmin(void) const;
119  int pmax(void) const;
121 
123 
124  ModEvent est(Space& home, int n);
127  ModEvent ect(Space& home, int n);
129  ModEvent lst(Space& home, int n);
131  ModEvent lct(Space& home, int n);
133  ModEvent norun(Space& home, int e, int l);
135  };
136 
137 }}
138 
140 
141 namespace Gecode { namespace Int {
142 
149  template<class TaskView>
150  class TaskViewTraits {};
151 
158  template<class Task>
159  class TaskTraits {};
160 
161 }}
162 
163 namespace Gecode { namespace Int {
164 
166  template<class Task>
167  class TaskArray {
168  private:
170  int n;
172  Task* t;
173  public:
175 
176  TaskArray(void);
179  TaskArray(Space& home, int n);
181  TaskArray(const TaskArray<Task>& a);
183  const TaskArray<Task>& operator =(const TaskArray<Task>& a);
185 
187 
188  int size(void) const;
191  void size(int n);
193 
195 
196  Task& operator [](int i);
199  const Task& operator [](int i) const;
201 
203 
207  void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
209 
211 
212  void update(Space&, bool share, 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, PropCond pc>
424  class TaskProp : public Propagator {
425  protected:
429  TaskProp(Home home, TaskArray<Task>& t);
431  TaskProp(Space& home, bool shared, TaskProp<Task,pc>& p);
432  public:
434  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
436  virtual size_t dispose(Space& home);
437  };
438 
440  template<class OptTask,PropCond pc>
442 
444  template<class OptTask,PropCond pc,class Cap>
446 
447 }}
448 
449 #include <gecode/int/task/prop.hpp>
450 #include <gecode/int/task/purge.hpp>
451 
452 #endif
453 
454 // STATISTICS: int-prop
Sort by earliest completion times.
Definition: task.hh:284
int left(void) const
How many tasks are left to be iterated.
Definition: iter.hpp:61
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:233
static int n_left(int i)
Return index of left child of node i.
Definition: tree.hpp:77
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
Definition: prop.hpp:56
TaskArray< Task > & t
Access to task array.
Definition: task.hh:238
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void operator++(void)
Move iterator to next task.
Definition: iter.hpp:66
SortTaskOrder
How to sort tasks.
Definition: task.hh:282
bool operator()(void) const
Test whether iterator is still at a task.
Definition: iter.hpp:56
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 subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition: man-to-opt.hpp:87
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
TaskArray(void)
Default constructor (array of size 0)
Definition: array.hpp:46
Propagator for tasks
Definition: task.hh:424
Task array.
Definition: task.hh:167
Handle to region.
Definition: region.hpp:61
Node * node
Task nodes.
Definition: task.hh:371
Computation spaces.
Definition: core.hpp:1362
TaskViewArray(TaskArray< Task > &t)
Initialize from task array a.
Definition: array.hpp:134
Traits class for mapping tasks to task views.
Definition: task.hh:159
Sort by earliest start times.
Definition: task.hh:283
TaskViewIter(void)
Default constructor (no initialization)
Definition: iter.hpp:44
Gecode::FloatVal c(-8, 8)
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:105
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
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:236
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
bool assigned(void) const
Test whether task is assigned.
Definition: man-to-opt.hpp:62
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:119
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:156
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
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:43
friend class TaskTree
Definition: task.hh:366
bool optional(void) const
Whether task can still be optional.
Definition: man-to-opt.hpp:56
ManToOptTask(void)
Default constructor.
Definition: man-to-opt.hpp:42
TaskView & operator[](int i)
Return task view at position i.
Definition: array.hpp:151
Class to define an optional from a mandatory task.
Definition: task.hh:47
TaskArray< Task > t
Tasks.
Definition: task.hh:427
int * _leaf
Map task number to leaf node number in right order.
Definition: task.hh:373
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:139
int n_inner(void) const
Return number of inner nodes.
Definition: tree.hpp:56
Sort by latest completion times.
Definition: task.hh:286
int ect(void) const
Return earliest completion time.
Definition: fwd-to-bwd.hpp:50
Task mapper: turns a task view into its dual.
Definition: task.hh:104
void subscribe(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Subscribe propagator p to all tasks.
Definition: array.hpp:91
int est(void) const
Return earliest start time.
Definition: fwd-to-bwd.hpp:45
int * map
Map for iteration order.
Definition: task.hh:312
bool n_leaf(int i) const
Whether node i is leaf.
Definition: tree.hpp:72
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
int task(void) const
Return current task position.
Definition: iter.hpp:72
Propagation cost.
Definition: core.hpp:537
static bool left(int i)
Test whether node i is a left child.
Definition: tree.hpp:82
ExecStatus
Definition: core.hpp:523
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: prop.hpp:62
void cancel(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Cancel subscription of propagator p for all tasks.
Definition: array.hpp:98
bool excluded(void) const
Whether task is excluded.
Definition: man-to-opt.hpp:51
Node & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:107
int lct(void) const
Return latest completion time.
Definition: fwd-to-bwd.hpp:60
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition: man-to-opt.hpp:93
int pmin(void) const
Return minimum processing time.
Definition: fwd-to-bwd.hpp:65
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:67
Allows to iterate over mandatory task views according to a specified order.
Definition: task.hh:339
static bool n_root(int i)
Whether node i is index of root.
Definition: tree.hpp:67
Traits class for mapping task views to tasks.
Definition: task.hh:150
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition: task.hh:50
Gecode toplevel namespace
const Node & root(void) const
Return root node.
Definition: tree.hpp:113
int i
Current position.
Definition: task.hh:314
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:369
void update(Space &home, bool share, ManToOptTask &t)
Update this task to be a clone of task t.
Definition: man-to-opt.hpp:79
int lst(void) const
Return latest start time.
Definition: fwd-to-bwd.hpp:55
const TaskArray< Task > & operator=(const TaskArray< Task > &a)
Initialize from task array a (share elements)
Definition: array.hpp:60
int pmax(void) const
Return maximum processing time.
Definition: fwd-to-bwd.hpp:70
Sort by latest start times.
Definition: task.hh:285
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
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:365
TaskProp(Home home, TaskArray< Task > &t)
Constructor for creation.
Definition: prop.hpp:42
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition: purge.hpp:42
Boolean view for Boolean variables.
Definition: view.hpp:1315
bool mandatory(void) const
Whether task is mandatory.
Definition: man-to-opt.hpp:46