this repo has no description
dekker.one
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
41 /// Class to define an optional from a mandatory task
42 template<class ManTask>
43 class ManToOptTask : public ManTask {
44 protected:
45 /// Boolean view whether task is mandatory (= 1) or not
46 Int::BoolView _m;
47 public:
48 /// \name Constructors and initialization
49 //@{
50 /// Default constructor
51 ManToOptTask(void);
52 //@}
53
54 /// \name Value access
55 //@{
56 /// Whether task is mandatory
57 bool mandatory(void) const;
58 /// Whether task is excluded
59 bool excluded(void) const;
60 /// Whether task can still be optional
61 bool optional(void) const;
62 //@}
63
64 //@{
65 /// Test whether task is assigned
66 bool assigned(void) const;
67 //@}
68
69 /// \name Value update
70 //@{
71 /// Mark task as mandatory
72 ModEvent mandatory(Space& home);
73 /// Mark task as excluded
74 ModEvent excluded(Space& home);
75 //@}
76
77 /// \name Cloning
78 //@{
79 /// Update this task to be a clone of task \a t
80 void update(Space& home, ManToOptTask& t);
81 //@}
82
83 /// \name Dependencies
84 //@{
85 /// Subscribe propagator \a p to task
86 void subscribe(Space& home, Propagator& p, PropCond pc);
87 /// Cancel subscription of propagator \a p for task
88 void cancel(Space& home, Propagator& p, PropCond pc);
89 /// Schedule propagator \a p
90 void reschedule(Space& home, Propagator& p, PropCond pc);
91 //@}
92 };
93
94}}
95
96#include <gecode/int/task/man-to-opt.hpp>
97
98namespace Gecode { namespace Int {
99
100 /// Task mapper: turns a task view into its dual
101 template<class TaskView>
102 class FwdToBwd : public TaskView {
103 public:
104 /// \name Value access
105 //@{
106 /// Return earliest start time
107 int est(void) const;
108 /// Return earliest completion time
109 int ect(void) const;
110 /// Return latest start time
111 int lst(void) const;
112 /// Return latest completion time
113 int lct(void) const;
114 /// Return minimum processing time
115 int pmin(void) const;
116 /// Return maximum processing time
117 int pmax(void) const;
118 //@}
119
120 /// \name Value update
121 //@{
122 /// Update earliest start time to \a n
123 ModEvent est(Space& home, int n);
124 /// Update earliest completion time to \a n
125 ModEvent ect(Space& home, int n);
126 /// Update latest start time to \a n
127 ModEvent lst(Space& home, int n);
128 /// Update latest completion time to \a n
129 ModEvent lct(Space& home, int n);
130 /// Update such that task cannot run from \a e to \a l
131 ModEvent norun(Space& home, int e, int l);
132 //@}
133 };
134
135}}
136
137#include <gecode/int/task/fwd-to-bwd.hpp>
138
139namespace Gecode { namespace Int {
140
141 /**
142 * \brief Traits class for mapping task views to tasks
143 *
144 * Each task view must specialize this traits class and add a \code
145 * typedef \endcode for the task corresponding to this task view.
146 */
147 template<class TaskView>
148 class TaskViewTraits {};
149
150 /**
151 * \brief Traits class for mapping tasks to task views
152 *
153 * Each task must specialize this traits class and add \code
154 * typedef \endcode for the task views corresponding to this task.
155 */
156 template<class Task>
157 class TaskTraits {};
158
159}}
160
161namespace Gecode { namespace Int {
162
163 /// Task array
164 template<class Task>
165 class TaskArray {
166 private:
167 /// Number of tasks (size)
168 int n;
169 /// Tasks
170 Task* t;
171 public:
172 /// \name Constructors and initialization
173 //@{
174 /// Default constructor (array of size 0)
175 TaskArray(void);
176 /// Allocate memory for \a n tasks (no initialization)
177 TaskArray(Space& home, int n);
178 /// Initialize from task array \a a (share elements)
179 TaskArray(const TaskArray<Task>& a);
180 /// Initialize from task array \a a (share elements)
181 const TaskArray<Task>& operator =(const TaskArray<Task>& a);
182 //@}
183
184 /// \name Array size
185 //@{
186 /// Return size of array (number of elements)
187 int size(void) const;
188 /// Set size of array (number of elements) to \a n, must not be larger
189 void size(int n);
190 //@}
191
192 /// \name Array elements
193 //@{
194 /// Return task at position \a i
195 Task& operator [](int i);
196 /// Return task at position \a i
197 const Task& operator [](int i) const;
198 //@}
199
200 /// \name Dependencies
201 //@{
202 /// Subscribe propagator \a p to all tasks
203 void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
204 /// Cancel subscription of propagator \a p for all tasks
205 void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
206 /// Schedule propagator \a p
207 void reschedule(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
208 //@}
209
210 /// \name Cloning
211 //@{
212 /// Update array to be a clone of array \a a
213 void update(Space&, TaskArray& a);
214 //@}
215
216 private:
217 static void* operator new(size_t);
218 static void operator delete(void*,size_t);
219 };
220
221 /**
222 * \brief Print array elements enclosed in curly brackets
223 * \relates TaskArray
224 */
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
231 /// Task view array
232 template<class TaskView>
233 class TaskViewArray {
234 protected:
235 /// The underlying task type
236 typedef typename TaskViewTraits<TaskView>::Task Task;
237 /// Access to task array
238 TaskArray<Task>& t;
239 public:
240 /// \name Constructors and initialization
241 //@{
242 /// Initialize from task array \a a
243 TaskViewArray(TaskArray<Task>& t);
244 //@}
245
246 /// \name Array information
247 //@{
248 /// Return size of array (number of elements)
249 int size(void) const;
250 /// Set size of array (number of elements) to \a n, must not be larger
251 void size(int n);
252 //@}
253
254 /// \name Array elements
255 //@{
256 /// Return task view at position \a i
257 TaskView& operator [](int i);
258 /// Return task view at position \a i
259 const TaskView& operator [](int i) const;
260 //@}
261 private:
262 static void* operator new(size_t);
263 static void operator delete(void*,size_t);
264 };
265
266 /**
267 * \brief Print array elements enclosed in curly brackets
268 * \relates TaskViewArray
269 */
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
279namespace Gecode { namespace Int {
280
281 /// How to sort tasks
282 enum SortTaskOrder {
283 STO_EST, ///< Sort by earliest start times
284 STO_ECT, ///< Sort by earliest completion times
285 STO_LST, ///< Sort by latest start times
286 STO_LCT ///< Sort by latest completion times
287 };
288
289 /// Sort task view array \a t according to \a sto and \a inc (increasing or decreasing)
290 template<class TaskView, SortTaskOrder sto, bool inc>
291 void sort(TaskViewArray<TaskView>& t);
292
293 /// Initialize and sort \a map for task view array \a t according to \a sto and \a inc (increasing or decreasing)
294 template<class TaskView, SortTaskOrder sto, bool inc>
295 void sort(int* map, const TaskViewArray<TaskView>& t);
296
297 /// Sort \a map with size \a n for task view array \a t according to \a sto and \a inc (increasing or decreasing)
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
305namespace Gecode { namespace Int {
306
307 /// Allows to iterate over task views according to a specified order
308 template<class TaskView, SortTaskOrder sto, bool inc>
309 class TaskViewIter {
310 protected:
311 /// Map for iteration order
312 int* map;
313 /// Current position
314 int i;
315 /// Default constructor (no initialization)
316 TaskViewIter(void);
317 public:
318 /// Initialize iterator
319 TaskViewIter(Region& r, const TaskViewArray<TaskView>& t);
320 /// \name Iteration control
321 //@{
322 /// Test whether iterator is still at a task
323 bool operator ()(void) const;
324 /// How many tasks are left to be iterated
325 int left(void) const;
326 /// Move iterator to next task
327 void operator ++(void);
328 //@}
329
330 /// \name %Task access
331 //@{
332 /// Return current task position
333 int task(void) const;
334 //@}
335 };
336
337 /// Allows to iterate over mandatory task views according to a specified order
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:
344 /// Initialize iterator with mandatory tasks
345 ManTaskViewIter(Region& r, const TaskViewArray<OptTaskView>& t);
346 };
347
348}}
349
350#include <gecode/int/task/iter.hpp>
351
352namespace Gecode { namespace Int {
353
354 /// Safe addition in case \a x is -Int::Limits::infinity
355 int plus(int x, int y);
356
357 /// Safe addition in case \a x is -Int::Limits::llinfinity
358 long long int plus(long long int x, long long int y);
359
360 /// Safe addition in case \a x is -Int::Limits::double_infinity
361 double plus(double x, double y);
362
363 /// Task trees for task views with node type \a Node
364 template<class TaskView, class Node>
365 class TaskTree {
366 template<class,class> friend class TaskTree;
367 protected:
368 /// The tasks from which the tree is computed
369 const TaskViewArray<TaskView>& tasks;
370 /// Task nodes
371 Node* node;
372 /// Map task number to leaf node number in right order
373 int* _leaf;
374
375 /// Return number of inner nodes
376 int n_inner(void) const;
377 /// Return number of nodes for balanced binary tree
378 int n_nodes(void) const;
379 /// Whether node \a i is index of root
380 static bool n_root(int i);
381 /// Whether node \a i is leaf
382 bool n_leaf(int i) const;
383 /// Return index of left child of node \a i
384 static int n_left(int i);
385 /// Test whether node \a i is a left child
386 static bool left(int i);
387 /// Return index of right child of node \a i
388 static int n_right(int i);
389 /// Test whether node \a i is a right child
390 static bool right(int i);
391 /// Return index of parent of node \a i
392 static int n_parent(int i);
393 protected:
394 /// Return leaf for task \a i
395 Node& leaf(int i);
396 /// Return root node
397 const Node& root(void) const;
398 /// Update tree after leaf for task \a i has changed (\a l whether i refers to a leaf)
399 void update(int i, bool l=true);
400 /// Initialize tree after leaves have been initialized
401 void init(void);
402 /// Update all inner nodes of tree after leaves have been initialized
403 void update(void);
404 /// Initialize tree for tasks \a t
405 TaskTree(Region& r, const TaskViewArray<TaskView>& t);
406 /// Initialize tree using tree \a t
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
415namespace Gecode { namespace Int {
416
417 /**
418 * \brief %Propagator for tasks
419 *
420 * Requires \code #include <gecode/int/task.hh> \endcode
421 * \ingroup FuncIntProp
422 */
423 template<class Task, class PL>
424 class TaskProp : public Propagator {
425 protected:
426 /// Tasks
427 TaskArray<Task> t;
428 /// Constructor for creation
429 TaskProp(Home home, TaskArray<Task>& t);
430 /// Constructor for cloning \a p
431 TaskProp(Space& home, TaskProp<Task,PL>& p);
432 public:
433 /// Cost function (defined as high linear)
434 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
435 /// Schedule function
436 virtual void reschedule(Space& home);
437 /// Delete propagator and return its size
438 virtual size_t dispose(Space& home);
439 };
440
441 /// Purge optional tasks that are excluded and possibly rewrite propagator
442 template<class OptTask, class PL>
443 ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t);
444
445 /// Purge optional tasks that are excluded and possibly rewrite propagator
446 template<class OptTask, class PL, class Cap>
447 ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t, Cap c);
448
449 /// Class for defining basic propagation level
450 class PLB {
451 public:
452 /// Perform basic propagation
453 static const bool basic = true;
454 /// Do not perform advanced propagation
455 static const bool advanced = false;
456 /// For basic propagation, domain operations are needed
457 static const PropCond pc = PC_INT_DOM;
458 };
459
460 /// Class for defining advanced propagation level
461 class PLA {
462 public:
463 /// Perform basic propagation
464 static const bool basic = false;
465 /// Do not perform advanced propagation
466 static const bool advanced = true;
467 /// For basic propagation, domain operations are needed
468 static const PropCond pc = PC_INT_BND;
469 };
470
471 /// Class for defining basic and advanced propagation level
472 class PLBA {
473 public:
474 /// Perform basic propagation
475 static const bool basic = true;
476 /// Do not perform advanced propagation
477 static const bool advanced = true;
478 /// For basic propagation, domain operations are needed
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
487namespace Gecode { namespace Int {
488
489 /// Time-tabling event for task
490 class Event {
491 public:
492 /// Event type for task with order in which they are processed
493 enum Type {
494 LRT = 0, ///< Latest required time of task
495 LCT = 1, ///< Latest completion time of task
496 EST = 2, ///< Earliest start time of task
497 ZRO = 3, ///< Zero-length task start time
498 ERT = 4, ///< Earliest required time of task
499 END = 5 ///< End marker
500 };
501 protected:
502 /// Combines type and number of task
503 unsigned int ei;
504 /// Time of event
505 int t;
506 public:
507 /// Initialize event
508 void init(Type e, int t, int i);
509 /// Return event type
510 Type type(void) const;
511 /// Return event time
512 int time(void) const;
513 /// Return event index
514 int idx(void) const;
515 /// Order among events
516 bool operator <(const Event& e) const;
517 /// Allocate from \a r and initialize event array with tasks \a t
518 template<class Task>
519 static Event* events(Region& r, const TaskArray<Task>& t, bool& assigned);
520 /// Allocate from \a r and initialize event array with assigned tasks \a t only
521 template<class Task>
522 static Event* events(Region& r, const TaskArray<Task>& t);
523 };
524
525 /// Print event \a e on stream \a os
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