Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
time-tabling.hpp
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  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2015
9  * Guido Tack, 2010
10  *
11  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 namespace Gecode { namespace Int { namespace Unary {
37 
38  template<class Task>
41  Region r;
42 
43  bool assigned;
44  if (Event* e = Event::events(r,t,assigned)) {
45  // Whether resource is free
46  bool free = true;
47  // Set of current but not required tasks
48  Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
49 
50  // Process events
51  do {
52  // Current time
53  int time = e->time();
54 
55  // Process events for completion of required part
56  for ( ; (e->type() == Event::LRT) && (e->time() == time); e++)
57  if (t[e->idx()].mandatory()) {
58  tasks.set(static_cast<unsigned int>(e->idx()));
59  free = true;
60  }
61 
62  // Process events for completion of task
63  for ( ; (e->type() == Event::LCT) && (e->time() == time); e++)
64  tasks.clear(static_cast<unsigned int>(e->idx()));
65 
66  // Process events for start of task
67  for ( ; (e->type() == Event::EST) && (e->time() == time); e++)
68  tasks.set(static_cast<unsigned int>(e->idx()));
69 
70  // Process events for zero-length task
71  for ( ; (e->type() == Event::ZRO) && (e->time() == time); e++)
72  if (!free)
73  return ES_FAILED;
74 
75  // Norun start time
76  int nrstime = time;
77  // Process events for start of required part
78  for ( ; (e->type() == Event::ERT) && (e->time() == time); e++)
79  if (t[e->idx()].mandatory()) {
80  tasks.clear(static_cast<unsigned int>(e->idx()));
81  if (!free)
82  return ES_FAILED;
83  free = false;
84  nrstime = time+1;
85  } else if (t[e->idx()].optional() && !free) {
86  GECODE_ME_CHECK(t[e->idx()].excluded(home));
87  }
88 
89  if (!free)
91  j(); ++j)
92  // Task j cannot run from time to next time - 1
93  if (t[j.val()].mandatory())
94  GECODE_ME_CHECK(t[j.val()].norun(home, nrstime, e->time() - 1));
95 
96  } while (e->type() != Event::END);
97  }
98 
99  if (assigned)
100  return home.ES_SUBSUMED(p);
101 
102  return ES_NOFIX;
103  }
104 
105 }}}
106 
107 // STATISTICS: int-prop
@ ERT
Earliest required time of task.
Definition: task.hh:498
void set(unsigned int i)
Set bit i.
Value iterator for values in a bitset.
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
@ EST
Earliest start time of task.
Definition: task.hh:496
ExecStatus timetabling(Space &home, Propagator &p, TaskArray< Task > &t)
Perform time-tabling propagation.
Time-tabling event for task.
Definition: task.hh:490
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Computation spaces.
Definition: core.hpp:1742
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
void clear(unsigned int i)
Clear bit i.
Handle to region.
Definition: region.hpp:55
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
@ LCT
Latest completion time of task.
Definition: task.hh:495
@ END
End marker.
Definition: task.hh:499
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
Task array.
Definition: task.hh:165
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
@ ZRO
Zero-length task start time.
Definition: task.hh:497
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
@ LRT
Latest required time of task.
Definition: task.hh:494
ExecStatus
Definition: core.hpp:472