Generated on Thu Mar 16 2017 03:24:21 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  * 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);
185  const TaskArray<Task>& operator =(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);
211  void reschedule(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
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Task view array.
Definition: task.hh:237
TaskArray< Task > & t
Access to task array.
Definition: task.hh:242
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
unsigned int ei
Combines type and number of task.
Definition: task.hh:507
Class for defining basic propagation level.
Definition: task.hh:454
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
SortTaskOrder
How to sort tasks.
Definition: task.hh:286
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:142
Base-class for propagators.
Definition: core.hpp:1012
Propagator for tasks
Definition: task.hh:428
Task array.
Definition: task.hh:169
Handle to region.
Definition: region.hpp:61
Node * node
Task nodes.
Definition: task.hh:375
Computation spaces.
Definition: core.hpp:1672
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
Gecode::FloatVal c(-8, 8)
Class for defining basic and advanced propagation level.
Definition: task.hh:476
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Time-tabling event for task.
Definition: task.hh:494
TaskViewTraits< TaskView >::Task Task
The underlying task type.
Definition: task.hh:240
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
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
Allows to iterate over task views according to a specified order.
Definition: task.hh:313
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:43
unsigned int size(I &i)
Size of all ranges of range iterator i.
ManToOptTask(void)
Default constructor.
Definition: man-to-opt.hpp:42
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
Sort by latest completion times.
Definition: task.hh:290
Task mapper: turns a task view into its dual.
Definition: task.hh:106
int * map
Map for iteration order.
Definition: task.hh:316
bool mandatory(void) const
Whether task is mandatory.
Definition: man-to-opt.hpp:46
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:550
ExecStatus
Definition: core.hpp:536
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
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:690
bool operator<(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:230
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition: task.hh:50
Gecode toplevel namespace
int i
Current position.
Definition: task.hh:318
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:373
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
int t
Time of event.
Definition: task.hh:509
Sort by latest start times.
Definition: task.hh:289
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:905
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
bool assigned(void) const
Test whether task is assigned.
Definition: man-to-opt.hpp:62
Boolean view for Boolean variables.
Definition: view.hpp:1315