Generated on Thu Jul 21 2022 00:00:00 for Gecode by doxygen 1.9.4
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
95 }
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>
116 : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
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
176 le = 0; lenv = -Limits::llinfinity;
178 }
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;
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.
Definition: bool-expr.cpp:240
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Node for an extended omega tree.
Definition: cumulative.hh:582
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.
Definition: cumulative.hh:585
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.
Definition: cumulative.hh:625
long long int le
Energy for subtree.
Definition: cumulative.hh:630
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.
Definition: cumulative.hh:632
int resLe
Node which is responsible for le.
Definition: cumulative.hh:634
static const int undef
Undefined task.
Definition: cumulative.hh:628
int resLenv
Node which is responsible for lenv.
Definition: cumulative.hh:636
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.
Definition: cumulative.hh:547
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.
Definition: cumulative.hh:550
long long int env
Energy envelope for subtree.
Definition: cumulative.hh:552
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
The tasks from which the tree is computed.
Definition: task.hh:369
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:115
OmegaNode & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:103
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
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void update(VY &y, Space &home, bool shared, VY py)
Update view y from py.
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
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:194