Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
event.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 *
6 * Copyright:
7 * Christian Schulte, 2015
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
34namespace Gecode { namespace Int {
35
36 forceinline void
37 Event::init(Event::Type e0, int t0, int i0) {
38 ei=static_cast<unsigned int>(e0 | (i0 << 3)); t=t0;
39 }
40
42 Event::type(void) const {
43 return static_cast<Type>(ei & 7);
44 }
45 forceinline int
46 Event::time(void) const {
47 return t;
48 }
49 forceinline int
50 Event::idx(void) const {
51 return static_cast<int>(ei >> 3);;
52 }
53
55 Event::operator <(const Event& e) const {
56 if (time() == e.time())
57 return type() < e.type();
58 return time() < e.time();
59 }
60
61
62 template<class Char, class Traits>
63 inline std::basic_ostream<Char,Traits>&
64 operator <<(std::basic_ostream<Char,Traits>& os, const Event& e) {
65 std::basic_ostringstream<Char,Traits> s;
66 s.copyfmt(os); s.width(0);
67 s << '[';
68 switch (e.type()) {
69 case Event::LRT: s << "LRT"; break;
70 case Event::LCT: s << "LCT"; break;
71 case Event::EST: s << "EST"; break;
72 case Event::ZRO: s << "ZRO"; break;
73 case Event::ERT: s << "ERT"; break;
74 default: GECODE_NEVER;
75 }
76 s << ',' << e.time() << ',' << e.idx() << ']';
77 return os << s.str();
78 }
79
80
81 template<class Task>
82 forceinline Event*
83 Event::events(Region& r, const TaskArray<Task>& t, bool& assigned) {
84 Event* e = r.alloc<Event>(4*t.size()+1);
85
86 // Initialize events
87 assigned=true;
88 bool required=false;
89
90 int n=0;
91 for (int i=0; i<t.size(); i++)
92 if (t[i].assigned()) {
93 // Only add required part
94 if (t[i].pmin() > 0) {
95 required = true;
96 e[n++].init(Event::ERT,t[i].lst(),i);
97 e[n++].init(Event::LRT,t[i].ect(),i);
98 } else if (t[i].pmax() == 0) {
99 required = true;
100 e[n++].init(Event::ZRO,t[i].lst(),i);
101 }
102 } else {
103 assigned = false;
104 e[n++].init(Event::EST,t[i].est(),i);
105 e[n++].init(Event::LCT,t[i].lct(),i);
106 // Check whether task has required part
107 if (t[i].lst() < t[i].ect()) {
108 required = true;
109 e[n++].init(Event::ERT,t[i].lst(),i);
110 e[n++].init(Event::LRT,t[i].ect(),i);
111 }
112 }
113
114 if (!required)
115 return NULL;
116
117 // Sort events
119
120 // Write end marker
122
123 return e;
124 }
125
126 template<class Task>
129 Event* e = r.alloc<Event>(2*t.size()+1);
130
131 // Only add assigned and mandatory tasks
132 int n=0;
133 for (int i=0; i<t.size(); i++)
134 if (t[i].assigned() && t[i].mandatory()) {
135 if (t[i].pmin() > 0) {
136 e[n++].init(Event::ERT,t[i].lst(),i);
137 e[n++].init(Event::LRT,t[i].ect(),i);
138 } else if (t[i].pmax() == 0) {
139 e[n++].init(Event::ZRO,t[i].lst(),i);
140 }
141 } else {
142 assert(!t[i].excluded());
143 return NULL;
144 }
145
146 // Sort events
148
149 // Write end marker
151
152 return e;
153 }
154
155}}
156
157// STATISTICS: int-prop
NodeType t
Type of node.
int n
Number of negative literals for node type.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Time-tabling event for task.
Definition task.hh:490
int t
Time of event.
Definition task.hh:505
int idx(void) const
Return event index.
Definition event.hpp:50
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
unsigned int ei
Combines type and number of task.
Definition task.hh:503
void init(Type e, int t, int i)
Initialize event.
Definition event.hpp:37
Type
Event type for task with order in which they are processed.
Definition task.hh:493
@ ZRO
Zero-length task start time.
Definition task.hh:497
@ ERT
Earliest required time of task.
Definition task.hh:498
@ LRT
Latest required time of task.
Definition task.hh:494
@ EST
Earliest start time of task.
Definition task.hh:496
@ END
End marker.
Definition task.hh:499
@ LCT
Latest completion time of task.
Definition task.hh:495
int time(void) const
Return event time.
Definition event.hpp:46
Type type(void) const
Return event type.
Definition event.hpp:42
bool operator<(const Event &e) const
Order among events.
Definition event.hpp:55
Task array.
Definition task.hh:165
Handle to region.
Definition region.hpp:55
const int infinity
Infinity for integers.
Definition int.hh:120
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const IdxViewArray< View > &x)
Definition idx-view.hpp:167
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56