task.hh
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2009
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#ifndef __GECODE_INT_TASK_HH__
#define __GECODE_INT_TASK_HH__
#include <gecode/int.hh>
namespace Gecode { namespace Int {
template<class ManTask>
class ManToOptTask : public ManTask {
protected:
Int::BoolView _m;
public:
ManToOptTask(void);
bool mandatory(void) const;
bool excluded(void) const;
bool optional(void) const;
bool assigned(void) const;
ModEvent mandatory(Space& home);
ModEvent excluded(Space& home);
void update(Space& home, ManToOptTask& t);
void subscribe(Space& home, Propagator& p, PropCond pc);
void cancel(Space& home, Propagator& p, PropCond pc);
void reschedule(Space& home, Propagator& p, PropCond pc);
};
}}
#include <gecode/int/task/man-to-opt.hpp>
namespace Gecode { namespace Int {
template<class TaskView>
class FwdToBwd : public TaskView {
public:
int est(void) const;
int ect(void) const;
int lst(void) const;
int lct(void) const;
int pmin(void) const;
int pmax(void) const;
ModEvent est(Space& home, int n);
ModEvent ect(Space& home, int n);
ModEvent lst(Space& home, int n);
ModEvent lct(Space& home, int n);
ModEvent norun(Space& home, int e, int l);
};
}}
#include <gecode/int/task/fwd-to-bwd.hpp>
namespace Gecode { namespace Int {
template<class TaskView>
class TaskViewTraits {};
template<class Task>
class TaskTraits {};
}}
namespace Gecode { namespace Int {
template<class Task>
class TaskArray {
private:
int n;
Task* t;
public:
TaskArray(void);
TaskArray(Space& home, int n);
TaskArray(const TaskArray<Task>& a);
const TaskArray<Task>& operator =(const TaskArray<Task>& a);
int size(void) const;
void size(int n);
Task& operator [](int i);
const Task& operator [](int i) const;
void subscribe(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
void cancel(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
void reschedule(Space& home, Propagator& p, PropCond pc=Int::PC_INT_BND);
void update(Space&, TaskArray& a);
private:
static void* operator new(size_t);
static void operator delete(void*,size_t);
};
template<class Char, class Traits, class Task>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os,
const TaskArray<Task>& t);
template<class TaskView>
class TaskViewArray {
protected:
typedef typename TaskViewTraits<TaskView>::Task Task;
TaskArray<Task>& t;
public:
TaskViewArray(TaskArray<Task>& t);
int size(void) const;
void size(int n);
TaskView& operator [](int i);
const TaskView& operator [](int i) const;
private:
static void* operator new(size_t);
static void operator delete(void*,size_t);
};
template<class Char, class Traits, class TaskView>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os,
const TaskViewArray<TaskView>& t);
}}
#include <gecode/int/task/array.hpp>
namespace Gecode { namespace Int {
enum SortTaskOrder {
STO_EST,
STO_ECT,
STO_LST,
STO_LCT
};
template<class TaskView, SortTaskOrder sto, bool inc>
void sort(TaskViewArray<TaskView>& t);
template<class TaskView, SortTaskOrder sto, bool inc>
void sort(int* map, const TaskViewArray<TaskView>& t);
template<class TaskView, SortTaskOrder sto, bool inc>
void sort(int* map, int n, const TaskViewArray<TaskView>& t);
}}
#include <gecode/int/task/sort.hpp>
namespace Gecode { namespace Int {
template<class TaskView, SortTaskOrder sto, bool inc>
class TaskViewIter {
protected:
int* map;
int i;
TaskViewIter(void);
public:
TaskViewIter(Region& r, const TaskViewArray<TaskView>& t);
bool operator ()(void) const;
int left(void) const;
void operator ++(void);
int task(void) const;
};
template<class OptTaskView, SortTaskOrder sto, bool inc>
class ManTaskViewIter : public TaskViewIter<OptTaskView,sto,inc> {
protected:
using TaskViewIter<OptTaskView,sto,inc>::map;
using TaskViewIter<OptTaskView,sto,inc>::i;
public:
ManTaskViewIter(Region& r, const TaskViewArray<OptTaskView>& t);
};
}}
#include <gecode/int/task/iter.hpp>
namespace Gecode { namespace Int {
int plus(int x, int y);
long long int plus(long long int x, long long int y);
double plus(double x, double y);
template<class TaskView, class Node>
class TaskTree {
template<class,class> friend class TaskTree;
protected:
const TaskViewArray<TaskView>& tasks;
Node* node;
int* _leaf;
int n_inner(void) const;
int n_nodes(void) const;
static bool n_root(int i);
bool n_leaf(int i) const;
static int n_left(int i);
static bool left(int i);
static int n_right(int i);
static bool right(int i);
static int n_parent(int i);
protected:
Node& leaf(int i);
const Node& root(void) const;
void update(int i, bool l=true);
void init(void);
void update(void);
TaskTree(Region& r, const TaskViewArray<TaskView>& t);
template<class Node2> TaskTree(Region& r,
const TaskTree<TaskView,Node2>& t);
};
}}
#include <gecode/int/task/tree.hpp>
namespace Gecode { namespace Int {
template<class Task, class PL>
class TaskProp : public Propagator {
protected:
TaskArray<Task> t;
TaskProp(Home home, TaskArray<Task>& t);
TaskProp(Space& home, TaskProp<Task,PL>& p);
public:
virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
virtual void reschedule(Space& home);
virtual size_t dispose(Space& home);
};
template<class OptTask, class PL>
ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t);
template<class OptTask, class PL, class Cap>
ExecStatus purge(Space& home, Propagator& p, TaskArray<OptTask>& t, Cap c);
class PLB {
public:
static const bool basic = true;
static const bool advanced = false;
static const PropCond pc = PC_INT_DOM;
};
class PLA {
public:
static const bool basic = false;
static const bool advanced = true;
static const PropCond pc = PC_INT_BND;
};
class PLBA {
public:
static const bool basic = true;
static const bool advanced = true;
static const PropCond pc = PC_INT_DOM;
};
}}
#include <gecode/int/task/prop.hpp>
#include <gecode/int/task/purge.hpp>
namespace Gecode { namespace Int {
class Event {
public:
enum Type {
LRT = 0,
LCT = 1,
EST = 2,
ZRO = 3,
ERT = 4,
END = 5
};
protected:
unsigned int ei;
int t;
public:
void init(Type e, int t, int i);
Type type(void) const;
int time(void) const;
int idx(void) const;
bool operator <(const Event& e) const;
template<class Task>
static Event* events(Region& r, const TaskArray<Task>& t, bool& assigned);
template<class Task>
static Event* events(Region& r, const TaskArray<Task>& t);
};
template<class Char, class Traits>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os, const Event& e);
}}
#include <gecode/int/task/event.hpp>
#endif
// STATISTICS: int-prop
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::BoolView
Boolean view for Boolean variables.
Definition view.hpp:1380
Gecode::Int::Event
Time-tabling event for task.
Definition task.hh:490
Gecode::Int::Event::t
int t
Time of event.
Definition task.hh:505
Gecode::Int::Event::idx
int idx(void) const
Return event index.
Definition event.hpp:50
Gecode::Int::Event::events
static Event * events(Region &r, const TaskArray< Task > &t, bool &assigned)
Allocate from r and initialize event array with tasks t.
Definition event.hpp:83
Gecode::Int::Event::ei
unsigned int ei
Combines type and number of task.
Definition task.hh:503
Gecode::Int::Event::init
void init(Type e, int t, int i)
Initialize event.
Definition event.hpp:37
Gecode::Int::Event::Type
Type
Event type for task with order in which they are processed.
Definition task.hh:493
Gecode::Int::Event::ZRO
@ ZRO
Zero-length task start time.
Definition task.hh:497
Gecode::Int::Event::ERT
@ ERT
Earliest required time of task.
Definition task.hh:498
Gecode::Int::Event::LRT
@ LRT
Latest required time of task.
Definition task.hh:494
Gecode::Int::Event::EST
@ EST
Earliest start time of task.
Definition task.hh:496
Gecode::Int::Event::END
@ END
End marker.
Definition task.hh:499
Gecode::Int::Event::LCT
@ LCT
Latest completion time of task.
Definition task.hh:495
Gecode::Int::Event::time
int time(void) const
Return event time.
Definition event.hpp:46
Gecode::Int::Event::type
Type type(void) const
Return event type.
Definition event.hpp:42
Gecode::Int::Event::operator<
bool operator<(const Event &e) const
Order among events.
Definition event.hpp:55
Gecode::Int::FwdToBwd
Task mapper: turns a task view into its dual.
Definition task.hh:102
Gecode::Int::FwdToBwd::lct
ModEvent lct(Space &home, int n)
Update latest completion time to n.
Definition fwd-to-bwd.hpp:87
Gecode::Int::FwdToBwd::lst
ModEvent lst(Space &home, int n)
Update latest start time to n.
Definition fwd-to-bwd.hpp:82
Gecode::Int::FwdToBwd::ect
int ect(void) const
Return earliest completion time.
Definition fwd-to-bwd.hpp:46
Gecode::Int::FwdToBwd::lst
int lst(void) const
Return latest start time.
Definition fwd-to-bwd.hpp:51
Gecode::Int::FwdToBwd::ect
ModEvent ect(Space &home, int n)
Update earliest completion time to n.
Definition fwd-to-bwd.hpp:77
Gecode::Int::FwdToBwd::lct
int lct(void) const
Return latest completion time.
Definition fwd-to-bwd.hpp:56
Gecode::Int::FwdToBwd::norun
ModEvent norun(Space &home, int e, int l)
Update such that task cannot run from e to l.
Definition fwd-to-bwd.hpp:92
Gecode::Int::FwdToBwd::est
int est(void) const
Return earliest start time.
Definition fwd-to-bwd.hpp:41
Gecode::Int::FwdToBwd::pmin
int pmin(void) const
Return minimum processing time.
Definition fwd-to-bwd.hpp:61
Gecode::Int::FwdToBwd::est
ModEvent est(Space &home, int n)
Update earliest start time to n.
Definition fwd-to-bwd.hpp:72
Gecode::Int::FwdToBwd::pmax
int pmax(void) const
Return maximum processing time.
Definition fwd-to-bwd.hpp:66
Gecode::Int::ManTaskViewIter::ManTaskViewIter
ManTaskViewIter(Region &r, const TaskViewArray< OptTaskView > &t)
Initialize iterator with mandatory tasks.
Definition iter.hpp:76
Gecode::Int::ManToOptTask::_m
Int::BoolView _m
Boolean view whether task is mandatory (= 1) or not.
Definition task.hh:46
Gecode::Int::ManToOptTask::assigned
bool assigned(void) const
Test whether task is assigned.
Definition man-to-opt.hpp:58
Gecode::Int::ManToOptTask::mandatory
bool mandatory(void) const
Whether task is mandatory.
Definition man-to-opt.hpp:42
Gecode::Int::ManToOptTask::ManToOptTask
ManToOptTask(void)
Default constructor.
Definition man-to-opt.hpp:38
Gecode::Int::ManToOptTask::cancel
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p for task.
Definition man-to-opt.hpp:88
Gecode::Int::ManToOptTask::update
void update(Space &home, ManToOptTask &t)
Update this task to be a clone of task t.
Definition man-to-opt.hpp:75
Gecode::Int::ManToOptTask::optional
bool optional(void) const
Whether task can still be optional.
Definition man-to-opt.hpp:52
Gecode::Int::ManToOptTask::excluded
bool excluded(void) const
Whether task is excluded.
Definition man-to-opt.hpp:47
Gecode::Int::ManToOptTask::subscribe
void subscribe(Space &home, Propagator &p, PropCond pc)
Subscribe propagator p to task.
Definition man-to-opt.hpp:82
Gecode::Int::ManToOptTask::reschedule
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition man-to-opt.hpp:95
Gecode::Int::PLA
Class for defining advanced propagation level.
Definition task.hh:461
Gecode::Int::PLA::pc
static const PropCond pc
For basic propagation, domain operations are needed.
Definition task.hh:468
Gecode::Int::PLA::advanced
static const bool advanced
Do not perform advanced propagation.
Definition task.hh:466
Gecode::Int::PLA::basic
static const bool basic
Perform basic propagation.
Definition task.hh:464
Gecode::Int::PLBA
Class for defining basic and advanced propagation level.
Definition task.hh:472
Gecode::Int::PLBA::advanced
static const bool advanced
Do not perform advanced propagation.
Definition task.hh:477
Gecode::Int::PLBA::basic
static const bool basic
Perform basic propagation.
Definition task.hh:475
Gecode::Int::PLBA::pc
static const PropCond pc
For basic propagation, domain operations are needed.
Definition task.hh:479
Gecode::Int::PLB
Class for defining basic propagation level.
Definition task.hh:450
Gecode::Int::PLB::pc
static const PropCond pc
For basic propagation, domain operations are needed.
Definition task.hh:457
Gecode::Int::PLB::advanced
static const bool advanced
Do not perform advanced propagation.
Definition task.hh:455
Gecode::Int::PLB::basic
static const bool basic
Perform basic propagation.
Definition task.hh:453
Gecode::Int::TaskArray
Task array.
Definition task.hh:165
Gecode::Int::TaskArray::operator[]
Task & operator[](int i)
Return task at position i.
Definition array.hpp:74
Gecode::Int::TaskArray::update
void update(Space &, TaskArray &a)
Update array to be a clone of array a.
Definition array.hpp:108
Gecode::Int::TaskArray::TaskArray
TaskArray(void)
Default constructor (array of size 0).
Definition array.hpp:42
Gecode::Int::TaskArray::subscribe
void subscribe(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Subscribe propagator p to all tasks.
Definition array.hpp:87
Gecode::Int::TaskArray::cancel
void cancel(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Cancel subscription of propagator p for all tasks.
Definition array.hpp:94
Gecode::Int::TaskArray::reschedule
void reschedule(Space &home, Propagator &p, PropCond pc=Int::PC_INT_BND)
Schedule propagator p.
Definition array.hpp:101
Gecode::Int::TaskArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:63
Gecode::Int::TaskArray::operator=
const TaskArray< Task > & operator=(const TaskArray< Task > &a)
Initialize from task array a (share elements).
Definition array.hpp:56
Gecode::Int::TaskProp::t
TaskArray< Task > t
Tasks.
Definition task.hh:427
Gecode::Int::TaskProp::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition prop.hpp:64
Gecode::Int::TaskProp::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition prop.hpp:58
Gecode::Int::TaskProp::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear).
Definition prop.hpp:52
Gecode::Int::TaskProp::TaskProp
TaskProp(Home home, TaskArray< Task > &t)
Constructor for creation.
Definition prop.hpp:38
Gecode::Int::TaskTraits
Traits class for mapping tasks to task views.
Definition task.hh:157
Gecode::Int::TaskTree::n_nodes
int n_nodes(void) const
Return number of nodes for balanced binary tree.
Definition tree.hpp:57
Gecode::Int::TaskTree::tasks
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition task.hh:369
Gecode::Int::TaskTree::n_right
static int n_right(int i)
Return index of right child of node i.
Definition tree.hpp:85
Gecode::Int::TaskTree::n_inner
int n_inner(void) const
Return number of inner nodes.
Definition tree.hpp:52
Gecode::Int::TaskTree::right
static bool right(int i)
Test whether node i is a right child.
Definition tree.hpp:90
Gecode::Int::TaskTree::n_left
static int n_left(int i)
Return index of left child of node i.
Definition tree.hpp:73
Gecode::Int::TaskTree::left
static bool left(int i)
Test whether node i is a left child.
Definition tree.hpp:78
Gecode::Int::TaskTree::init
void init(void)
Initialize tree after leaves have been initialized.
Definition tree.hpp:115
Gecode::Int::TaskTree::node
Node * node
Task nodes.
Definition task.hh:371
Gecode::Int::TaskTree::TaskTree
friend class TaskTree
Definition task.hh:366
Gecode::Int::TaskTree::n_leaf
bool n_leaf(int i) const
Whether node i is leaf.
Definition tree.hpp:68
Gecode::Int::TaskTree::root
const Node & root(void) const
Return root node.
Definition tree.hpp:109
Gecode::Int::TaskTree::n_parent
static int n_parent(int i)
Return index of parent of node i.
Definition tree.hpp:97
Gecode::Int::TaskTree::_leaf
int * _leaf
Map task number to leaf node number in right order.
Definition task.hh:373
Gecode::Int::TaskTree::leaf
Node & leaf(int i)
Return leaf for task i.
Definition tree.hpp:103
Gecode::Int::TaskTree::update
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition tree.hpp:122
Gecode::Int::TaskTree::n_root
static bool n_root(int i)
Whether node i is index of root.
Definition tree.hpp:63
Gecode::Int::TaskViewArray
Task view array.
Definition task.hh:233
Gecode::Int::TaskViewArray::t
TaskArray< Task > & t
Access to task array.
Definition task.hh:238
Gecode::Int::TaskViewArray::Task
TaskViewTraits< TaskView >::Task Task
The underlying task type.
Definition task.hh:236
Gecode::Int::TaskViewArray::TaskViewArray
TaskViewArray(TaskArray< Task > &t)
Initialize from task array a.
Definition array.hpp:137
Gecode::Int::TaskViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:142
Gecode::Int::TaskViewArray::operator[]
TaskView & operator[](int i)
Return task view at position i.
Definition array.hpp:154
Gecode::Int::TaskViewIter::operator++
void operator++(void)
Move iterator to next task.
Definition iter.hpp:62
Gecode::Int::TaskViewIter::operator()
bool operator()(void) const
Test whether iterator is still at a task.
Definition iter.hpp:52
Gecode::Int::TaskViewIter::map
int * map
Map for iteration order.
Definition task.hh:312
Gecode::Int::TaskViewIter::task
int task(void) const
Return current task position.
Definition iter.hpp:68
Gecode::Int::TaskViewIter::left
int left(void) const
How many tasks are left to be iterated.
Definition iter.hpp:57
Gecode::Int::TaskViewIter::i
int i
Current position.
Definition task.hh:314
Gecode::Int::TaskViewIter::TaskViewIter
TaskViewIter(void)
Default constructor (no initialization).
Definition iter.hpp:40
Gecode::Int::TaskViewTraits
Traits class for mapping task views to tasks.
Definition task.hh:148
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
event.hpp
fwd-to-bwd.hpp
int.hh
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
array.hpp
iter.hpp
sort.hpp
man-to-opt.hpp
Gecode::Int
Finite domain integers.
Gecode::Int::sort
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing).
Definition sort.hpp:133
Gecode::Int::purge
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition purge.hpp:38
Gecode::Int::SortTaskOrder
SortTaskOrder
How to sort tasks.
Definition task.hh:282
Gecode::Int::STO_ECT
@ STO_ECT
Sort by earliest completion times.
Definition task.hh:284
Gecode::Int::STO_EST
@ STO_EST
Sort by earliest start times.
Definition task.hh:283
Gecode::Int::STO_LST
@ STO_LST
Sort by latest start times.
Definition task.hh:285
Gecode::Int::STO_LCT
@ STO_LCT
Sort by latest completion times.
Definition task.hh:286
Gecode::Int::PC_INT_BND
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Gecode::Int::plus
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition tree.hpp:39
Gecode::Int::operator<<
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const IdxViewArray< View > &x)
Definition idx-view.hpp:167
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::PropCond
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
purge.hpp
prop.hpp
tree.hpp