Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
tree.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, 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#include <algorithm>
35
36namespace Gecode { namespace Int { namespace Unary {
37
38 /*
39 * Omega tree
40 */
41
42 forceinline void
44 p = 0; ect = -Limits::infinity;
45 }
46
47 forceinline void
49 p = l.p + r.p;
50 ect = std::max(plus(l.ect,r.p), r.ect);
51 }
52
53 template<class TaskView>
56 : TaskTree<TaskView,OmegaNode>(r,t) {
57 for (int i=0; i<tasks.size(); i++) {
58 leaf(i).p = 0; leaf(i).ect = -Limits::infinity;
59 }
60 init();
61 }
62
63 template<class TaskView>
64 forceinline void
66 leaf(i).p = tasks[i].pmin();
67 leaf(i).ect = tasks[i].est()+tasks[i].pmin();
68 update(i);
69 }
70
71 template<class TaskView>
72 forceinline void
74 leaf(i).p = 0; leaf(i).ect = -Limits::infinity;
75 update(i);
76 }
77
78 template<class TaskView>
79 forceinline int
81 return root().ect;
82 }
83
84 template<class TaskView>
85 forceinline int
87 // Check whether task i is in?
88 OmegaTree<TaskView>& o = const_cast<OmegaTree<TaskView>&>(*this);
89 if (o.leaf(i).ect != -Limits::infinity) {
90 o.remove(i);
91 int ect = o.root().ect;
92 o.insert(i);
93 return ect;
94 } else {
95 return root().ect;
96 }
97 }
98
99
100
101 /*
102 * Omega lambda tree
103 */
104
105 forceinline void
110
111 forceinline void
114 if (l.lp + r.p > l.p + r.lp) {
115 resLp = l.resLp;
116 lp = l.lp + r.p;
117 } else {
118 resLp = r.resLp;
119 lp = l.p + r.lp;
120 }
121 if ((r.lect >= plus(l.ect,r.lp)) && (r.lect >= plus(l.lect,r.p))) {
122 lect = r.lect; resEct = r.resEct;
123 } else if (plus(l.ect,r.lp) >= plus(l.lect,r.p)) {
124 assert(plus(l.ect,r.lp) > r.lect);
125 lect = plus(l.ect,r.lp); resEct = r.resLp;
126 } else {
127 assert((plus(l.lect,r.p) > r.lect) &&
128 (plus(l.lect,r.p) > plus(l.ect,r.lp)));
129 lect = plus(l.lect,r.p); resEct = l.resEct;
130 }
131 }
132
133
134 template<class TaskView>
138 bool inc)
139 : TaskTree<TaskView,OmegaLambdaNode>(r,t) {
140 if (inc) {
141 // Enter all tasks into tree (omega = all tasks, lambda = empty)
142 for (int i=0; i<tasks.size(); i++) {
143 leaf(i).p = leaf(i).lp = tasks[i].pmin();
144 leaf(i).ect = leaf(i).lect = tasks[i].est()+tasks[i].pmin();
145 leaf(i).resEct = OmegaLambdaNode::undef;
146 leaf(i).resLp = OmegaLambdaNode::undef;
147 }
148 update();
149 } else {
150 // Enter no tasks into tree (omega = empty, lambda = empty)
151 for (int i=0; i<tasks.size(); i++) {
152 leaf(i).p = leaf(i).lp = 0;
153 leaf(i).ect = leaf(i).lect = -Limits::infinity;
154 leaf(i).resEct = OmegaLambdaNode::undef;
155 leaf(i).resLp = OmegaLambdaNode::undef;
156 }
157 init();
158 }
159 }
160
161 template<class TaskView>
162 forceinline void
164 // That means that i is in omega
165 assert(leaf(i).ect > -Limits::infinity);
166 leaf(i).p = 0;
167 leaf(i).ect = -Limits::infinity;
168 leaf(i).resEct = i;
169 leaf(i).resLp = i;
170 update(i);
171 }
172
173 template<class TaskView>
174 forceinline void
176 leaf(i).p = tasks[i].pmin();
177 leaf(i).ect = tasks[i].est()+tasks[i].pmin();
178 update(i);
179 }
180
181 template<class TaskView>
182 forceinline void
184 leaf(i).lp = tasks[i].pmin();
185 leaf(i).lect = tasks[i].est()+tasks[i].pmin();
186 leaf(i).resEct = i;
187 leaf(i).resLp = i;
188 update(i);
189 }
190
191 template<class TaskView>
192 forceinline void
194 leaf(i).lp = 0;
195 leaf(i).lect = -Limits::infinity;
196 leaf(i).resEct = OmegaLambdaNode::undef;
197 leaf(i).resLp = OmegaLambdaNode::undef;
198 update(i);
199 }
200
201 template<class TaskView>
202 forceinline bool
204 return root().resEct < 0;
205 }
206
207 template<class TaskView>
208 forceinline int
210 return root().resEct;
211 }
212
213 template<class TaskView>
214 forceinline int
216 return root().ect;
217 }
218
219 template<class TaskView>
220 forceinline int
222 return root().lect;
223 }
224
225}}}
226
227// STATISTICS: int-prop
NNF * l
Left subtree.
NodeType t
Type of node.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Task trees for task views with node type Node.
Definition task.hh:365
const TaskViewArray< TaskView > & tasks
Definition task.hh:369
const Node & root(void) const
Return root node.
Definition tree.hpp:109
Task view array.
Definition task.hh:233
Node for an omega lambda tree.
Definition unary.hh:695
void update(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Update node from left child l and right child r.
Definition tree.hpp:112
void init(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Initialize node from left child l and right child r.
Definition tree.hpp:106
int lp
Processing times for subtree.
Definition unary.hh:700
static const int undef
Undefined task.
Definition unary.hh:698
int resEct
Node which is responsible for lect.
Definition unary.hh:704
int resLp
Node which is responsible for lp.
Definition unary.hh:706
int lect
Earliest completion times for subtree.
Definition unary.hh:702
int responsible(void) const
Return responsible task.
Definition tree.hpp:209
OmegaLambdaTree(Region &r, const TaskViewArray< TaskView > &t, bool inc=true)
Initialize tree for tasks t with all tasks included, if inc is true.
Definition tree.hpp:136
void shift(int i)
Shift task with index i from omega to lambda.
Definition tree.hpp:163
void lremove(int i)
Remove task with index i from lambda.
Definition tree.hpp:193
bool lempty(void) const
Whether has responsible task.
Definition tree.hpp:203
void oinsert(int i)
Insert task with index i to omega.
Definition tree.hpp:175
int lect(void) const
Return earliest completion time of all tasks excluding lambda tasks.
Definition tree.hpp:221
void linsert(int i)
Insert task with index i to lambda.
Definition tree.hpp:183
int ect(void) const
Return earliest completion time of all tasks.
Definition tree.hpp:215
Node for an omega tree.
Definition unary.hh:660
int ect
Earliest completion time for subtree.
Definition unary.hh:665
void init(const OmegaNode &l, const OmegaNode &r)
Initialize node from left child l and right child r.
Definition tree.hpp:43
int p
Processing time for subtree.
Definition unary.hh:663
void update(const OmegaNode &l, const OmegaNode &r)
Update node from left child l and right child r.
Definition tree.hpp:48
Omega trees for computing ect of task sets.
Definition unary.hh:674
void insert(int i)
Insert task with index i.
Definition tree.hpp:65
int ect(void) const
Return earliest completion time of all tasks.
Definition tree.hpp:80
void remove(int i)
Remove task with index i.
Definition tree.hpp:73
OmegaTree(Region &r, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t.
Definition tree.hpp:55
Handle to region.
Definition region.hpp:55
void update(const NoOffset &)
Integer-precision integer scale view.
Definition view.hpp:638
const int infinity
Infinity for integers.
Definition int.hh:120
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition tree.hpp:39
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
#define forceinline
Definition config.hpp:187