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 * Guido Tack <tack@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2009
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#include <algorithm>
37#include <cmath>
38
39namespace Gecode { namespace Int { namespace Cumulative {
40
41 /*
42 * Omega tree
43 */
44
45 forceinline void
47 e = 0; env = -Limits::llinfinity;
48 }
49
50 forceinline void
52 e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
53 }
54
55 template<class TaskView>
58 : TaskTree<TaskView,OmegaNode>(r,t), c(c0) {
59 for (int i=0; i<tasks.size(); i++) {
60 leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
61 }
62 init();
63 }
64
65 template<class TaskView>
66 forceinline void
68 leaf(i).e = tasks[i].e();
69 leaf(i).env =
70 static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
71 update(i);
72 }
73
74 template<class TaskView>
75 forceinline void
77 leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
78 update(i);
79 }
80
81 template<class TaskView>
82 forceinline long long int
84 return root().env;
85 }
86
87 /*
88 * Extended Omega tree
89 */
90
91 forceinline void
96
97 forceinline void
100 cenv = std::max(plus(l.cenv,r.e), r.cenv);
101 }
102
103 template<class TaskView> void
105 ci = ci0;
106 for (int i=0; i<tasks.size(); i++) {
107 leaf(i).e = 0;
108 leaf(i).env = leaf(i).cenv = -Limits::llinfinity;
109 }
110 init();
111 }
112
113 template<class TaskView> template<class Node>
117
118 template<class TaskView>
119 forceinline long long int
121 // Enter task i
122 leaf(i).e = tasks[i].e();
123 leaf(i).env =
124 static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
125 leaf(i).cenv =
126 static_cast<long long int>(c-ci)*tasks[i].est()+tasks[i].e();
128
129 // Perform computation of node for task with minest
130 int met = 0;
131 {
132 long long int e = 0;
133 while (!n_leaf(met)) {
134 if (plus(node[n_right(met)].cenv,e) >
135 static_cast<long long int>(c-ci) * tasks[i].lct()) {
136 met = n_right(met);
137 } else {
138 e += node[n_right(met)].e; met = n_left(met);
139 }
140 }
141 }
142
143 /*
144 * The following idea to compute the cut in one go is taken from:
145 * Joseph Scott, Filtering Algorithms for Discrete Resources,
146 * Master Thesis, Uppsala University, 2010 (in preparation).
147 */
148
149 // Now perform split from leaf met upwards
150 long long int a_e = node[met].e;
151 long long int a_env = node[met].env;
152 long long int b_e = 0;
153
154 while (!n_root(met)) {
155 if (left(met)) {
156 b_e += node[n_right(n_parent(met))].e;
157 } else {
158 a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e));
159 a_e += node[n_left(n_parent(met))].e;
160 }
161 met = n_parent(met);
162 }
163
164 return plus(a_env,b_e);
165 }
166
167
168
169 /*
170 * Omega lambda tree
171 */
172
173 forceinline void
179
180 forceinline void
183 if (l.le + r.e > l.e + r.le) {
184 le = l.le + r.e;
185 resLe = l.resLe;
186 } else {
187 le = l.e + r.le;
188 resLe = r.resLe;
189 }
190 if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) {
191 lenv = r.lenv; resLenv = r.resLenv;
192 } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) {
193 assert(plus(l.env,r.le) > r.lenv);
194 lenv = plus(l.env,r.le); resLenv = r.resLe;
195 } else {
196 assert((plus(l.lenv,r.e) > r.lenv) &&
197 (plus(l.lenv,r.e) > plus(l.env,r.le)));
198 lenv = plus(l.lenv,r.e); resLenv = l.resLenv;
199 }
200 }
201
202
203 template<class TaskView>
206 : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) {
207 // Enter all tasks into tree (omega = all tasks, lambda = empty)
208 for (int i=0; i<tasks.size(); i++) {
209 leaf(i).e = tasks[i].e();
210 leaf(i).le = 0;
211 leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
212 leaf(i).lenv = -Limits::llinfinity;
213 leaf(i).resLe = OmegaLambdaNode::undef;
214 leaf(i).resLenv = OmegaLambdaNode::undef;
215 }
216 update();
217 }
218
219 template<class TaskView>
220 forceinline void
222 // i is in omega
223 assert(leaf(i).env > -Limits::llinfinity);
224 leaf(i).le = leaf(i).e;
225 leaf(i).e = 0;
226 leaf(i).lenv = leaf(i).env;
227 leaf(i).env = -Limits::llinfinity;
228 leaf(i).resLe = i;
229 leaf(i).resLenv = i;
230 update(i);
231 }
232
233 template<class TaskView>
234 forceinline void
236 // i not in omega but in lambda
237 assert(leaf(i).env == -Limits::llinfinity);
238 assert(leaf(i).lenv > -Limits::llinfinity);
239 leaf(i).le = 0;
240 leaf(i).lenv = -Limits::llinfinity;
241 leaf(i).resLe = OmegaLambdaNode::undef;
242 leaf(i).resLenv = OmegaLambdaNode::undef;
243 update(i);
244 }
245
246 template<class TaskView>
247 forceinline bool
249 return root().resLenv < 0;
250 }
251
252 template<class TaskView>
253 forceinline int
255 return root().resLenv;
256 }
257
258 template<class TaskView>
259 forceinline long long int
261 return root().env;
262 }
263
264 template<class TaskView>
265 forceinline long long int
267 return root().lenv;
268 }
269
270}}}
271
272// 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
Node for an extended omega tree.
void update(const ExtOmegaNode &l, const ExtOmegaNode &r)
Update node from left child l and right child r.
Definition tree.hpp:98
void init(const ExtOmegaNode &l, const ExtOmegaNode &r)
Initialize node from left child l and right child r.
Definition tree.hpp:92
long long int cenv
Energy envelope for subtree.
long long int env(int i)
Compute update for task with index i.
Definition tree.hpp:120
ExtOmegaTree(Region &r, int c, const TaskTree< TaskView, Node > &t)
Initialize tree for tasks t and capacity c.
Definition tree.hpp:114
Node for an omega lambda tree.
long long int le
Energy for subtree.
void init(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Initialize node from left child l and right child r.
Definition tree.hpp:174
void update(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Update node from left child l and right child r.
Definition tree.hpp:181
long long int lenv
Energy envelope for subtree.
int resLe
Node which is responsible for le.
static const int undef
Undefined task.
int resLenv
Node which is responsible for lenv.
int responsible(void) const
Return responsible task.
Definition tree.hpp:254
long long int lenv(void) const
Return energy envelope of all tasks excluding lambda tasks.
Definition tree.hpp:266
void shift(int i)
Shift task with index i from omega to lambda.
Definition tree.hpp:221
OmegaLambdaTree(Region &r, int c, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t and capcity c with all tasks included in omega.
Definition tree.hpp:204
void lremove(int i)
Remove task with index i from lambda.
Definition tree.hpp:235
long long int env(void) const
Return energy envelope of all tasks.
Definition tree.hpp:260
bool lempty(void) const
Whether has responsible task.
Definition tree.hpp:248
Node for an omega tree.
void init(const OmegaNode &l, const OmegaNode &r)
Initialize node from left child l and right child r.
Definition tree.hpp:46
void update(const OmegaNode &l, const OmegaNode &r)
Update node from left child l and right child r.
Definition tree.hpp:51
long long int e
Energy for subtree.
long long int env
Energy envelope for subtree.
void remove(int i)
Remove task with index i.
Definition tree.hpp:76
OmegaTree(Region &r, int c, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t and capacity c.
Definition tree.hpp:56
long long int env(void) const
Return energy envelope of all tasks.
Definition tree.hpp:83
void insert(int i)
Insert task with index i.
Definition tree.hpp:67
Task trees for task views with node type Node.
Definition task.hh:365
const TaskViewArray< TaskView > & tasks
Definition task.hh:369
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition tree.hpp:122
Task view array.
Definition task.hh:233
Handle to region.
Definition region.hpp:55
void update(const NoOffset &)
Integer-precision integer scale view.
Definition view.hpp:638
const long long int llinfinity
Infinity for long long integers.
Definition int.hh:126
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