Generated on Thu Feb 21 2013 23:11:42 for Gecode by doxygen 1.8.3.1
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  * Last modified:
12  * $Date: 2011-05-26 00:56:41 +1000 (Thu, 26 May 2011) $ by $Author: schulte $
13  * $Revision: 12022 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <algorithm>
41 #include <cmath>
42 
43 namespace Gecode { namespace Int { namespace Cumulative {
44 
45  /*
46  * Omega tree
47  */
48 
49  forceinline void
52  }
53 
54  forceinline void
55  OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
56  e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
57  }
58 
59  template<class TaskView>
61  const TaskViewArray<TaskView>& t)
62  : TaskTree<TaskView,OmegaNode>(r,t), c(c0) {
63  for (int i=tasks.size(); i--; ) {
64  leaf(i).e = 0.0; leaf(i).env = -Int::Limits::double_infinity;
65  }
66  init();
67  }
68 
69  template<class TaskView>
70  forceinline void
72  leaf(i).e = tasks[i].e();
73  leaf(i).env = static_cast<double>(c)*tasks[i].est()+tasks[i].e();
74  update(i);
75  }
76 
77  template<class TaskView>
78  forceinline void
80  leaf(i).e = 0.0; leaf(i).env = -Int::Limits::double_infinity;
81  update(i);
82  }
83 
84  template<class TaskView>
85  forceinline double
87  return root().env;
88  }
89 
90  /*
91  * Extended Omega tree
92  */
93 
94  forceinline void
96  OmegaNode::init(l,r);
98  }
99 
100  forceinline void
102  OmegaNode::update(l,r);
103  cenv = std::max(plus(l.cenv,r.e), r.cenv);
104  }
105 
106  template<class TaskView> void
108  ci = ci0;
109  for (int i=tasks.size(); i--; ) {
110  leaf(i).e = 0.0;
111  leaf(i).env = leaf(i).cenv = -Int::Limits::double_infinity;
112  }
113  init();
114  }
115 
116  template<class TaskView> template<class Node>
118  const TaskTree<TaskView,Node>& t)
119  : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
120 
121  template<class TaskView>
122  forceinline double
124  // Enter task i
125  leaf(i).e = tasks[i].e();
126  leaf(i).env = static_cast<double>(c)*tasks[i].est()+tasks[i].e();
127  leaf(i).cenv = static_cast<double>(c-ci)*tasks[i].est()+tasks[i].e();
129 
130  // Perform computation of node for task with minest
131  int met = 0;
132  {
133  double e = 0.0;
134  while (!n_leaf(met)) {
135  if (plus(node[n_right(met)].cenv,e) >
136  static_cast<double>(c-ci) * tasks[i].lct()) {
137  met = n_right(met);
138  } else {
139  e += node[n_right(met)].e; met = n_left(met);
140  }
141  }
142  }
143 
144  /*
145  * The following idea to compute the cut in one go is taken from:
146  * Joseph Scott, Filtering Algorithms for Discrete Resources,
147  * Master Thesis, Uppsala University, 2010 (in preparation).
148  */
149 
150  // Now perform split from leaf met upwards
151  double a_e = node[met].e;
152  double a_env = node[met].env;
153  double b_e = 0.0;
154 
155  while (!n_root(met)) {
156  if (left(met)) {
157  b_e += node[n_right(n_parent(met))].e;
158  } else {
159  a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e));
160  a_e += node[n_left(n_parent(met))].e;
161  }
162  met = n_parent(met);
163  }
164  return b_e + a_env;
165  }
166 
167 
168 
169  /*
170  * Omega lambda tree
171  */
172 
173  forceinline void
175  OmegaNode::init(l,r);
177  resLe = undef; resLenv = undef;
178  }
179 
180  forceinline void
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>
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=tasks.size(); i--; ) {
209  leaf(i).e = tasks[i].e();
210  leaf(i).le = 0.0;
211  leaf(i).env = static_cast<double>(c)*tasks[i].est()+tasks[i].e();
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 > -Int::Limits::double_infinity);
224  leaf(i).le = leaf(i).e;
225  leaf(i).e = 0.0;
226  leaf(i).lenv = leaf(i).env;
227  leaf(i).env = -Int::Limits::double_infinity;
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 == -Int::Limits::double_infinity);
238  assert(leaf(i).lenv > -Int::Limits::double_infinity);
239  leaf(i).le = 0.0;
240  leaf(i).lenv = -Int::Limits::double_infinity;
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 double
261  return root().env;
262  }
263 
264  template<class TaskView>
265  forceinline double
267  return root().lenv;
268  }
269 
270 }}}
271 
272 // STATISTICS: int-prop