this repo has no description
dekker.one
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
46 OmegaNode::init(const OmegaNode&, const OmegaNode&) {
47 e = 0; env = -Limits::llinfinity;
48 }
49
50 forceinline void
51 OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
52 e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
53 }
54
55 template<class TaskView>
56 OmegaTree<TaskView>::OmegaTree(Region& r, int c0,
57 const TaskViewArray<TaskView>& t)
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
67 OmegaTree<TaskView>::insert(int i) {
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
76 OmegaTree<TaskView>::remove(int i) {
77 leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
78 update(i);
79 }
80
81 template<class TaskView>
82 forceinline long long int
83 OmegaTree<TaskView>::env(void) const {
84 return root().env;
85 }
86
87 /*
88 * Extended Omega tree
89 */
90
91 forceinline void
92 ExtOmegaNode::init(const ExtOmegaNode& l, const ExtOmegaNode& r) {
93 OmegaNode::init(l,r);
94 cenv = -Limits::llinfinity;
95 }
96
97 forceinline void
98 ExtOmegaNode::update(const ExtOmegaNode& l, const ExtOmegaNode& r) {
99 OmegaNode::update(l,r);
100 cenv = std::max(plus(l.cenv,r.e), r.cenv);
101 }
102
103 template<class TaskView> void
104 ExtOmegaTree<TaskView>::init(int ci0) {
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>
114 ExtOmegaTree<TaskView>::ExtOmegaTree(Region& r, int c0,
115 const TaskTree<TaskView,Node>& t)
116 : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
117
118 template<class TaskView>
119 forceinline long long int
120 ExtOmegaTree<TaskView>::env(int i) {
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();
127 TaskTree<TaskView,ExtOmegaNode>::update(i);
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
174 OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
175 OmegaNode::init(l,r);
176 le = 0; lenv = -Limits::llinfinity;
177 resLe = undef; resLenv = undef;
178 }
179
180 forceinline void
181 OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
182 OmegaNode::update(l,r);
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>
204 OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r, int c0,
205 const TaskViewArray<TaskView>& t)
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
221 OmegaLambdaTree<TaskView>::shift(int i) {
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
235 OmegaLambdaTree<TaskView>::lremove(int i) {
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
248 OmegaLambdaTree<TaskView>::lempty(void) const {
249 return root().resLenv < 0;
250 }
251
252 template<class TaskView>
253 forceinline int
254 OmegaLambdaTree<TaskView>::responsible(void) const {
255 return root().resLenv;
256 }
257
258 template<class TaskView>
259 forceinline long long int
260 OmegaLambdaTree<TaskView>::env(void) const {
261 return root().env;
262 }
263
264 template<class TaskView>
265 forceinline long long int
266 OmegaLambdaTree<TaskView>::lenv(void) const {
267 return root().lenv;
268 }
269
270}}}
271
272// STATISTICS: int-prop